2017/08/08 by Garg, Sumegha, Raz, Ran, Tal, Avishay
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.1708.02639
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, b1), (a2, b2) …, where for every i, ai ∈ A is chosen uniformly at random and bi = 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|)2,(log |A|)2\) 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.