# The gradient complexity of linear regression

arXiv: https://arxiv.org/abs/1911.02212 · HTML: https://mlsanity.com/paper/1911.02212/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2019.

## Built on by (most cited first, 9 of 9)

- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Lower bounds for trace estimation via Block Krylov and other methods](https://mlsanity.com/paper/2506.22701/) (2025)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)

## Abstract (arXiv)

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.