Space lower bounds for linear prediction in the streaming model
  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.
