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. hypotheses), H := H 1 , H 2 , . . . , H n . The goal is to design an algorithm that outputs a distribution ˆ H ∈ 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 hypotheses at the domain point x (i.e., is H i ( x ) < H j ( x ) ?). This model allows us to study how much needs to be stored, at any point in time, about the portion of the stream seen so far. Our main result is an algorithm that achieves a nearly optimal tradeoff between memory usage and sample complexity. In particular, given b bits of memory (for b roughly between log n and n ), our algorithm solves the hypothesis selection problem with s samples, where b · s = O ( n log n ) . This result is optimal up to an O (log n ) factor, for all b .