Memory-Sample Lower Bounds for Learning Parity with Noise

In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn x=(x1,ldots,xn) ∈ 0,1n from a stream of random linear equations over F2 that are correct with probability frac12+varepsilon and flipped with probability frac12-varepsilon, that any learning algorithm requires either a memory of size Omega(n2/varepsilon) or an exponential number of samples. In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [GRT'18], when the samples are noisy. A matrix M: A × X rightarrow -1,1 corresponds to the following learning problem with error parameter varepsilon: 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) with probability 1/2+varepsilon and bi = -M(ai,x) with probability 1/2-varepsilon (0<varepsilon< frac12). 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, with error, requires either a memory of size at least Omegaleft(frack · ℓvarepsilon right), or at least 2Omega(r) samples. In particular, this shows that for a large class of learning problems, same as those in [GRT'18], any learning algorithm requires either a memory of size at least Omegaleft(frac(log |X|) · (log |A|)varepsilonright) or an exponential number of noisy samples. Our proof is based on adapting the arguments in [Raz'17,GRT'18] to the noisy case.