2019/04/18 by Vatsal Sharan, Aaron Sidford, Sharan, Vatsal +3 · 2 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1904.08544
A few minor edits over previous version
arxiv created 2020/10/10 · arxiv updated 2020/10/13
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 (a1,b1), (a2,b2)…, with ai drawn independently from a d-dimensional isotropic Gaussian, and where bi = ⟨ ai, x⟩ + ηi, for a fixed x ∈ ℝd with ‖x‖2 = 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 d2/4 bits of memory requires at least Ω(d log log \frac1ε) samples to approximate x to ℓ2 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(d2 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.