Extractor-Based Time-Space Lower Bounds for Learning

A matrix $M:A\times X\to \{-1,1\}$ corresponds to the following learning problem: An unknown element $x\in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$,whereforevery$i$,$a_i \in A$ischosenuniformlyatrandomand$b_i = M(a_i,x)$. Assume that $k,\mathrm{\ell },r$ are such that any submatrix of $M$ of at least $2^{-k}\cdot \mathrm{\mid }A\mathrm{\mid }$ rows and at least $2^{-\mathrm{\ell }}\cdot \mathrm{\mid }X\mathrm{\mid }$ 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 $\mathrm{\Omega }(k\cdot \mathrm{\ell })$, or at least $2^{\mathrm{\Omega }(r)}$ samples. The result holds even if the learner has an exponentially small success probability (of $2^{-\mathrm{\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 $\Omega\left((\log |X|) \cdot (\log |A|)\right)$ or an exponential number of samples, achieving a tight $\mathrm{\Omega }((\log \mathrm{\mid }X\mathrm{\mid })\cdot (\log \mathrm{\mid }A\mathrm{\mid }))$ lower bound on the size of the memory, rather than a bound of $\Omega\left(\min\left{(\log |X|)^2,(\log |A|)^2\right}\right)$ 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.