Hypothesis Selection with Computational Constraints
Explore the fundamental problem of hypothesis selection in learning theory and statistics through this 32-minute lecture by Maryam Aliakbarpour from Rice University. Delve into the challenge of selecting a distribution that best matches given data from a finite set of candidate distributions. Learn about the goal of designing algorithms that output a distribution with minimal total variation distance from an unknown distribution. Examine the study of hypothesis selection under memory and time constraints, focusing on achieving optimal tradeoffs between memory usage and sample complexity. Discover methods for obtaining optimal accuracy using algorithms with nearly optimal time complexity in this Simons Institute presentation on extroverted sublinear algorithms.