The Gradient Complexity of Linear Regression

Mark Braverman; Elad Hazan; Max Simchowitz; Blake Woodworth

The Gradient Complexity of Linear Regression

Mark Braverman, Elad Hazan, Max Simchowitz, Blake Woodworth

Research output: Contribution to journal › Conference article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	627-647
Number of pages	21
Journal	Proceedings of Machine Learning Research
Volume	125
State	Published - 2020
Event	33rd Conference on Learning Theory, COLT 2020 - Virtual, Online, Austria Duration: Jul 9 2020 → Jul 12 2020

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Software
Control and Systems Engineering
Statistics and Probability

Cite this

@article{6030307ea0f04b298e007f225cd55d55,

title = "The Gradient Complexity of Linear Regression",

abstract = "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.",

author = "Mark Braverman and Elad Hazan and Max Simchowitz and Blake Woodworth",

note = "Publisher Copyright: {\textcopyright} 2020 M. Braverman, E. Hazan, M. Simchowitz & B. Woodworth.; 33rd Conference on Learning Theory, COLT 2020 ; Conference date: 09-07-2020 Through 12-07-2020",

year = "2020",

language = "English (US)",

volume = "125",

pages = "627--647",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

}

TY - JOUR

T1 - The Gradient Complexity of Linear Regression

AU - Braverman, Mark

AU - Hazan, Elad

AU - Simchowitz, Max

AU - Woodworth, Blake

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 -

The Gradient Complexity of Linear Regression

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this