TY - JOUR

T1 - The Gradient Complexity of Linear Regression

AU - Braverman, Mark

AU - Hazan, Elad

AU - Simchowitz, Max

AU - Woodworth, Blake

N1 - Funding Information:
Acknowledgements MB’s research is supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. EH is supported in part by NSF grant #1704860. MS is supported by an Open Philanthropy AI Fellowship, and this work was conducted while visiting Princeton University. BW is supported by the Google PhD fellowship program, and this work was conducted while an intern at Google AI Princeton. We thank Ramon Van Handel for his helpful discussions regarding random matrix theory.
Publisher Copyright:
© 2020 M. Braverman, E. Hazan, M. Simchowitz & B. Woodworth.

PY - 2020

Y1 - 2020

N2 - We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model that allows access to the data via a matrix-vector product oracle. We show that for polynomial accuracy, Θ(d) calls to the oracle are necessary and sufficient even for a randomized algorithm. Our lower bound is based on a reduction to estimating the least eigenvalue of a random Wishart matrix. This simple distribution enables a concise proof, leveraging a few key properties of the random Wishart ensemble.

AB - We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model that allows access to the data via a matrix-vector product oracle. We show that for polynomial accuracy, Θ(d) calls to the oracle are necessary and sufficient even for a randomized algorithm. Our lower bound is based on a reduction to estimating the least eigenvalue of a random Wishart matrix. This simple distribution enables a concise proof, leveraging a few key properties of the random Wishart ensemble.

UR - http://www.scopus.com/inward/record.url?scp=85097971726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097971726&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85097971726

SN - 2640-3498

VL - 125

SP - 627

EP - 647

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 33rd Conference on Learning Theory, COLT 2020

Y2 - 9 July 2020 through 12 July 2020

ER -