# Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2016.

## Built on by (most cited first, 30 of 64)

- [How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?](https://mlsanity.com/paper/2310.08391/) (2023)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Exponential Moving Average of Weights in Deep Learning: Dynamics and Benefits](https://mlsanity.com/paper/2411.18704/) (2024)
- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks](https://mlsanity.com/paper/2302.05882/) (2023)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Understanding Forgetting in Continual Learning with Linear Regression](https://mlsanity.com/paper/2405.17583/) (2024)
- [The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shift](https://mlsanity.com/paper/2208.01857/) (2022)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [Sampling-based inference for large linear models, with application to linearised Laplace](https://mlsanity.com/paper/2210.04994/) (2022)
- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Improved Scaling Laws in Linear Regression via Data Reuse](https://mlsanity.com/paper/2506.08415/) (2025)
- [On the Last Iterate Convergence of Momentum Methods](https://mlsanity.com/paper/2102.07002/) (2021)
- [Provable Generalization of Overparameterized Meta-learning Trained with SGD](https://mlsanity.com/paper/2206.09136/) (2022)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization](https://mlsanity.com/paper/2409.09745/) (2024)
- [Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay](https://mlsanity.com/paper/2602.06797/) (2026)
- [Random features models: a way to study the success of naive imputation](https://mlsanity.com/paper/2402.03839/) (2024)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [(Nearly) Optimal Private Linear Regression via Adaptive Clipping](https://mlsanity.com/paper/2207.04686/) (2022)
- [Federated Learning under Covariate Shifts with Generalization Guarantees](https://mlsanity.com/paper/2306.05325/) (2023)

## Abstract (arXiv)

We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that achieves jointly the optimal prediction error rates for least-squares regression, both in terms of forgetting of initial conditions in O(1/n 2), and in terms of dependence on the noise and dimension d of the problem, as O(d/n). Our new algorithm is based on averaged accelerated regularized gradient descent, and may also be analyzed through finer assumptions on initial conditions and the Hessian matrix, leading to dimension-free quantities that may still be small while the " optimal " terms above are large. In order to characterize the tightness of these new bounds, we consider an application to non-parametric regression and use the known lower bounds on the statistical performance (without computational limits), which happen to match our bounds obtained from a single pass on the data and thus show optimality of our algorithm in a wide variety of particular trade-offs between bias and variance.