Extractor-Based time-Space lower bounds for learning

A matrix M : A× X → {−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,b₁), (a2,b₂) . . ., where for every i, a_i ∈ A is chosen uniformly at random and b_i = 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 Ω (k · ℓ), or at least 2^Ω(r) samples. The result holds even if the learner has an exponentially small success probability (of 2^−Ω(r)). In particular, this shows that for a large class of learning problems, any learning algorithm requires either a memory of size at least Ω ((log |X|) · (log |A|)) or an exponential number of samples, achieving a tight Ω ((log |X|) · (log |A|)) lower bound on the size of the memory, rather than a bound of Ω min (log |X|)², (log |A|)² obtained in previous works by Raz [FOCS’17] and Moshkovitz and Moshkovitz [ITCS’18]. Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications. Our proof builds on the work of Raz [FOCS’17] that gave a general technique for proving memory-samples lower bounds.