Space lower bounds for linear prediction in the streaming model
This addresses the limitations of streaming algorithms for machine learning practitioners, providing a theoretical lower bound that is foundational rather than incremental.
The paper tackles the problem of determining memory requirements for fundamental learning tasks like linear separation and regression in a streaming model, showing that at least quadratic memory in dimension is necessary, which precludes scalable memory-efficient algorithms.
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 orthogonal vectors -- and utilize the estimates on the packing of the Grassmannian, the manifold of all linear subspaces of fixed dimension.