A Time-Space Lower Bound for a Large Class of Learning Problems
Ran Raz · 2017
We prove a general memory-samples 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. 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. A matrix M : A × X → {-1, 1} 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, (a1, b1), (a2, b2) ..., where for every i, ai∈ A is chosen uniformly at random and bi= M(ai, x). Let σmaxbe the largest singular value of M and note that always σmax≤ |A|1/2· |X|1/2. We show that if σmax≤ |A|1/2· |X|1/2-ε, then any learning algorithm for the corresponding learning problem requires either a memory of size at least Ω ((εn)2) or at least 2Ω(εn)samples, where n = log2|X|. As a special case, this gives a new proof for the memory-samples lower bound for parity learning [14].