# Optimal Randomized First-Order Methods for Least-Squares Problems

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2020.

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

- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queries](https://mlsanity.com/paper/2211.04612/) (2022)
- [Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions](https://mlsanity.com/paper/2202.00992/) (2022)
- [Training Quantized Neural Networks to Global Optimality via Semidefinite Programming](https://mlsanity.com/paper/2105.01420/) (2021)
- [Hashing embeddings of optimal dimension, with applications to linear least squares](https://mlsanity.com/paper/2105.11815/) (2021)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [When is Momentum Extragradient Optimal? A Polynomial-Based Analysis](https://mlsanity.com/paper/2211.04659/) (2022)
- [Random Function Descent](https://mlsanity.com/paper/2305.01377/) (2023)
- [Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Models](https://mlsanity.com/paper/2509.06856/) (2025)

## Abstract (arXiv)

We provide an exact analysis of a class of randomized algorithms for solving overdetermined least-squares problems. We consider first-order methods, where the gradients are pre-conditioned by an approximation of the Hessian, based on a subspace embedding of the data matrix. This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled randomized Hadamard transforms (SRHT). Our key technical innovation is the derivation of the limiting spectral density of SRHT embeddings. Leveraging this novel result, we derive the family of normalized orthogonal polynomials of the SRHT density and we find the optimal pre-conditioned first-order method along with its rate of convergence. Our analysis of Gaussian embeddings proceeds similarly, and leverages classical random matrix theory results. In particular, we show that for a given sketch size, SRHT embeddings exhibits a faster rate of convergence than Gaussian embeddings. Then, we propose a new algorithm by optimizing the computational complexity over the choice of the sketching dimension. To our knowledge, our resulting algorithm yields the best known complexity for solving least-squares problems with no condition number dependence.