Hypothesis Selection with Memory Constraints

Hypothesis selection is a fundamental problem in learning theory and statistics. Given a dataset and a finite set of candidate distributions, the goal is to select a distribution that matches the data as well as possible. More specifically, suppose that we have sample access to an unknown distribution P over a domain X that we know is well-approximated by one of a class of n distributions (a.k.a.