A time-space lower bound for a large class of learning problems

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. As a special case, this gives a new proof for the time-space lower bound for parity learning [R16]. Our result is stated in terms of the norm of the matrix that corresponds to the learning problem. Let X, A be two finite sets. Let M: A X \rightarrow \{-1,1\} be a matrix. The matrix M corresponds to the following learning problem: An unknown element x X was chosen uniformly at random. A learner tries to learn x from a stream of samples, (a-1, b-1), (a-2, b-2)..., where for every i, a-i A is chosen uniformly at random and b-i = M(a-i,x). Let \sigma be the largest singular value of M and note that always \sigma ≤ |A|^{1/2} |X|^{1/2}. We show that if \sigma ≤ |A|^{1/2} |X|^{1/2 - ∈, then any learning algorithm for the corresponding learning problem requires either a memory of size quadratic in ∈ n or number of samples exponential in ∈ n, where n = \log-2 |X|.As a special case, this gives a new proof for the memorysamples lower bound for parity learning [14].