# A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)

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

## Key facts

- Cited by 25 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 25 Oct 2017.

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

- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [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)
- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [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)
- [Correlated Noise Provably Beats Independent Noise for Differentially Private Learning](https://mlsanity.com/paper/2310.06771/) (2023)
- [Provable Generalization of Overparameterized Meta-learning Trained with SGD](https://mlsanity.com/paper/2206.09136/) (2022)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averaging](https://mlsanity.com/paper/2602.03702/) (2026)
- [Risk Bounds of Accelerated SGD for Overparameterized Linear Regression](https://mlsanity.com/paper/2311.14222/) (2023)
- [Improved Scaling Laws in Linear Regression via Data Reuse](https://mlsanity.com/paper/2506.08415/) (2025)
- [(Nearly) Optimal Private Linear Regression via Adaptive Clipping](https://mlsanity.com/paper/2207.04686/) (2022)
- [The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization](https://mlsanity.com/paper/2409.09745/) (2024)
- [On the Double Descent of Random Features Models Trained with SGD](https://mlsanity.com/paper/2110.06910/) (2021)
- [Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Scheduling](https://mlsanity.com/paper/2510.14717/) (2025)
- [A Unified Analysis for Finite Weight Averaging](https://mlsanity.com/paper/2411.13169/) (2024)
- [Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems](https://mlsanity.com/paper/2403.08585/) (2024)
- [On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks](https://mlsanity.com/paper/2508.14338/) (2025)
- [Statistical and Computational Guarantees for Influence Diagnostics](https://mlsanity.com/paper/2212.04014/) (2022)
- [Local SGD in Overparameterized Linear Regression](https://mlsanity.com/paper/2210.11562/) (2022)
- [What Makes a Strong Model? A Unified Spectral Analysis of Knowledge Transfer over High-dimensional Linear Regression](https://mlsanity.com/paper/2606.01292/) (2026)

## Abstract (arXiv)

This work provides a simplified proof of the statistical minimax optimality of (iterate averaged) stochastic gradient descent (SGD), for the special case of least squares. This result is obtained by analyzing SGD as a stochastic process and by sharply characterizing the stationary covariance matrix of this process. The finite rate optimality characterization captures the constant factors and addresses model mis-specification.