Time-Space Lower Bounds for Two-Pass Learning

摘要

A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size n requires either a memory of size ( n 2 ) or an exponential number of samples [Raz16].All these works modeled the learner as a one-pass branching program, allowing only one pass over the stream of samples. In this work, we prove the first memory-samples lower bounds (with a super-linear lower bound on the memory size and super-polynomial lower bound on the number of samples) when the learner is allowed two passes over the stream of samples. For example, we prove that any two-pass algorithm for learning parities of size n requires either a memory of size ( n 1 5 ) or at least 2 ( n ) samples.More generally, 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, ( 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 ) .Assume that k l r are such that any submatrix of M of at least 2 ? k A rows and at least 2 ? l X columns, has a bias of at most 2 ? r . We show that any two-pass learning algorithm for the learning problem corresponding to M requires either a memory of size at least k min k l , or at least 2 ( min k l r ) samples.