Extractor-Based Time-Space Lower Bounds for Learning

A matrix M: A × X rightarrow -1,1 corresponds to the following learning problem: An unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a1, b1), (a2, b2) ldots, where for every i, ai ∈ A is chosen uniformly at random and bi = M(ai,x). Assume that k,ℓ, r are such that any submatrix of M of at least 2-k · |A| rows and at least 2-ℓ · |X| columns, has a bias of at most 2-r. We show that any learning algorithm for the learning problem corresponding to M requires either a memory of size at least Omegaleft(k · ℓ right), or at least 2Omega(r) samples. The result holds even if the learner has an exponentially small success probability (of 2-Omega(r)). In particular, this shows that for a large class of learning problems, any learning algorithm requires either a memory of size at least Omegaleft((log |X|) · (log |A|)right) or an exponential number of samples, achieving a tight Omegaleft((log |X|) · (log |A|)right) lower bound on the size of the memory, rather than a bound of Omegaleft(minleft(log |X|)2,(log |A|)2rightright) obtained in previous works [R17,MM17b]. Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications. Our proof builds on [R17] that gave a general technique for proving memory-samples lower bounds.