Abstract

A recent line of works has focused on the following question: Can one prove strong unconditional lower bounds on the number of samples needed for learning under memory constraints? We study an extractor-based approach to proving such bounds for a large class of learning problems as follows. A matrix M: A x X -> {-1,1} corresponds to the following learning problem. An unknown function f in X is chosen uniformly at random. A learner tries to learn f from a stream of samples, (a_1, b_1), (a_2, b_2) ..., where for every i, a_i in A is chosen uniformly at random and b_i = M(a_i,f). We show that whenever M satisfies an extractor-based property, then a memory-bounded algorithm for the corresponding learning problem requires exponentially many samples to learn. We extend such lower bounds to distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. Under the distinguishing task, an algorithm is either given a stream of uniformly random samples (where for every i, a_i in A and b_i in {-1,1} are chosen uniformly at random) or a stream of samples generated using a uniformly random function f in X, and the goal of the algorithm is to distinguish between the two cases. In particular, we show memory-sample tradeoffs for refuting constraint satisfaction problems with a t-resilient predicate.

Attachment

Video Recording