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, $\Theta(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.
Cite
Text
Braverman et al. "The Gradient Complexity of Linear Regression." Conference on Learning Theory, 2020.Markdown
[Braverman et al. "The Gradient Complexity of Linear Regression." Conference on Learning Theory, 2020.](https://mlanthology.org/colt/2020/braverman2020colt-gradient/)BibTeX
@inproceedings{braverman2020colt-gradient,
title = {{The Gradient Complexity of Linear Regression}},
author = {Braverman, Mark and Hazan, Elad and Simchowitz, Max and Woodworth, Blake},
booktitle = {Conference on Learning Theory},
year = {2020},
pages = {627-647},
volume = {125},
url = {https://mlanthology.org/colt/2020/braverman2020colt-gradient/}
}