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 we have sample access to an unknown distribution P over a domain \mathcal{X} that we know is well-approximated by one of a a class of n distributions (a.k.a. The goal is to design an algorithm that outputs a distribution \hat{H} \in \mathcal{H} whose total variation distance from P is nearly minimal.In this work, we study the hypothesis selection problem under memory constraints. We consider a model where samples from P are presented in a stream and we access each sample x via PDF-comparison'' queries that allow us to compare the probability densities of any pair of hypothesesat the domain point x (i.e., is H_i(x) H_j(x)?).