mlsanityData to 7 Oct 2026

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

arXiv 1710.09430 ↗First posted 25 Oct 2017stat.ML cs.LG math.OCcited by 25

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 6; 2023: 5; 2024: 5; 2025: 3; 2026: 2.

25 papers.

Sort:

  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  2. 2023How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?cited by 93
  3. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  4. 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 54
  5. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  6. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  7. 2024Understanding Forgetting in Continual Learning with Linear Regressioncited by 26
  8. 2022The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shiftcited by 25
  9. 2023Correlated Noise Provably Beats Independent Noise for Differentially Private Learningcited by 23
  10. 2022Provable Generalization of Overparameterized Meta-learning Trained with SGDcited by 9
  11. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  12. 2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 8
13 more
  1. 2026Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averagingcited by 8
  2. 2023Risk Bounds of Accelerated SGD for Overparameterized Linear Regressioncited by 7
  3. 2025Improved Scaling Laws in Linear Regression via Data Reusecited by 7
  4. 2022(Nearly) Optimal Private Linear Regression via Adaptive Clippingcited by 6
  5. 2024The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimizationcited by 6
  6. 2021On the Double Descent of Random Features Models Trained with SGDcited by 5
  7. 2025Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Schedulingcited by 5
  8. 2024A Unified Analysis for Finite Weight Averagingcited by 3
  9. 2024Improving Implicit Regularization of SGD with Preconditioning for Least Square Problemscited by 2
  10. 2025On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networkscited by 2
  11. 2022Statistical and Computational Guarantees for Influence Diagnosticscited by 1
  12. 2022Local SGD in Overparameterized Linear Regressioncited by 0
  13. 2026What Makes a Strong Model? A Unified Spectral Analysis of Knowledge Transfer over High-dimensional Linear Regressioncited by 0