Memory-sample tradeoffs for linear regression with small error

We consider the problem of performing linear regression over a stream of d-dimensional examples, and show that any algorithm that uses a subquadratic amount of memory exhibits a slower rate of convergence than can be achieved without memory constraints. Specifically, consider a sequence of labeled examples (a₁,b₁), (a₂,b₂)…, with a_i drawn independently from a d-dimensional isotropic Gaussian, and where b_i = ⟨ a_i, x⟩ + η_i, for a fixed x ∈ ℝ^d with ||x||₂ = 1 and with independent noise η_i drawn uniformly from the interval [−2^−d/5,2^−d/5]. We show that any algorithm with at most d²/4 bits of memory requires at least Ω(d loglog1/є) samples to approximate x to ℓ₂ error є with probability of success at least 2/3, for є sufficiently small as a function of d. In contrast, for such є, x can be recovered to error є with probability 1−o(1) with memory O(d² log(1/є)) using d examples. This represents the first nontrivial lower bounds for regression with super-linear memory, and may open the door for strong memory/sample tradeoffs for continuous optimization.