Hypothesis selection with computational constraints

Abstract: With the ever-growing volume of data, understanding the computational aspects of statistical inference is increasingly critical. A key question arises: Can we develop algorithms that are both fast and memory-efficient to tackle these challenges? In this talk, we focus on the computational aspects of Hypothesis Selection, a fundamental problem in learning theory and statistics. The task is to select a distribution from a finite set of candidate distributions that best matches the underlying distribution of the given dataset. This talk will delve into the hypothesis selection problem under constraints of memory and time. We will explore how to achieve a nearly optimal tradeoff between memory usage and sample complexity, as well as methods to attain optimal accuracy using algorithms with near-optimal time complexity.
This talk is based on joint work with Mark Bun and Adam Smith.