Strong Memory Lower Bounds for Learning Natural Models

We give lower bounds on the amount of memory required by one-pass streaming algorithms for solving several natural learning problems. In a setting where examples lie in 0,1d and the optimal classifier can be encoded using kappa bits, we show that algorithms which learn using a near-minimal number of examples, tilde O(kappa), must use tilde Omega( dkappa) bits of space. Our space bounds match the dimension of the ambient space of the problem's natural parametrization, even when it is quadratic in the size of examples and the final classifier. For instance, in the setting of d-sparse linear classifiers over degree-2 polynomial features, for which kappa=Theta(dlog d), our space lower bound is tildeOmega(d2). Our bounds degrade gracefully with the stream length N, generally having the form tildeOmegaleft(dkappa · frackappaNright). Bounds of the form Omega(dkappa) were known for learning parity and other problems defined over finite fields. Bounds that apply in a narrow range of sample sizes are also known for linear regression. Ours are the first such bounds for problems of the type commonly seen in recent learning applications that apply for a large range of input sizes.