Memory-sample tradeoffs for linear regression with small error

DOI10.1145/3313276.3316403MaRDI QIDQ5212830zbMATH OpenOpenAlexWikidataFDO

Authors Vatsal Sharan, Aaron Sidford, Gregory Valiant

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.08544

zbMATH Keywords

lower bounds for optimizationmemory-bounded learning

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Linear regression; mixed models (62J05) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: 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_1,b_1),(a_2,b_2)ldots,$ with $a_i$ drawn independently from a $d$-dimensional isotropic Gaussian, and where $b_i=langle{a}_i,xangle+et{a}_i,$ for a fixed $xinmathbb{R}^d$ with $|x{|}_2=1$ and with independent noise $et{a}_i$ drawn uniformly from the interval $[-2^{-d/5},2^{-d/5}].$ We show that any algorithm with at most $d^2/4$ bits of memory requires at least $Omega(dloglogfrac1epsilon)$ samples to approximate $x$ to $el{l}_2$ error $epsilon$ with probability of success at least $2/3$, for $epsilon$ sufficiently small as a function of $d$. In contrast, for such $epsilon$, $x$ can be recovered to error $epsilon$ with probability $1-o(1)$ with memory $Oleft(d^{2}log(1/epsilon)ight)$ 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.

Recommendations

• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
• Numerical linear algebra in the streaming model
• Narrow big data in a stream: computational limitations and regression
• Adaptive and optimal online linear regression on ^1-balls
• Adaptive and optimal online linear regression on \(\ell ^{1}\)-balls

Cited in

(8)

• On the trade-off between number of examples and precision of supervision in machine learning problems
• Narrow big data in a stream: computational limitations and regression
• Extractor-based time-space lower bounds for learning
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Memory-sample lower bounds for learning with classical-quantum hybrid memory
• Memory-sample lower bounds for LWE
• Efficient convex optimization requires superlinear memory

This page was built for publication: Memory-sample tradeoffs for linear regression with small error

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212830)