Space lower bounds for linear prediction in the streaming model


Yuval Dagan, Gil Kur, Ohad Shamir ;
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:929-954, 2019.


We show that fundamental learning tasks, such as finding an approximate linear separator or linear regression, require memory at least \emph{quadratic} in the dimension, in a natural streaming setting. This implies that such problems cannot be solved (at least in this setting) by scalable memory-efficient streaming algorithms. Our results build on a memory lower bound for a simple linear-algebraic problem – finding approximate null vectors – and utilize the estimates on the packing of the Grassmannian, the manifold of all linear subspaces of fixed dimension.

Related Material