mlsanityData to 14 Oct 2026

Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems

arXiv 2403.08585 ↗First posted 13 Mar 2024cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) exhibits strong algorithmic regularization effects in practice and plays an important role in the generalization of modern machine learning. However, prior research has revealed instances where the generalization performance of SGD is worse than ridge regression due to uneven optimization along different dimensions. Preconditioning offers a natural solution to this issue by rebalancing optimization across different directions. Yet, the extent to which preconditioning can enhance the generalization performance of SGD and whether it can bridge the existing gap with ridge regression remains uncertain. In this paper, we study the generalization performance of SGD with preconditioning for the least squared problem. We make a comprehensive comparison between preconditioned SGD and (standard & preconditioned) ridge regression. Our study makes several key contributions toward understanding and improving SGD with preconditioning. First, we establish excess risk bounds (generalization performance) for preconditioned SGD and ridge regression under an arbitrary preconditions matrix. Second, leveraging the excessive risk characterization of preconditioned SGD and ridge regression, we show that (through construction) there exists a simple preconditioned matrix that can make SGD comparable to (standard & preconditioned) ridge regression. Finally, we show that our proposed preconditioning matrix is straightforward enough to allow robust estimation from finite samples while maintaining a theoretical improvement. Our empirical results align with our theoretical findings, collectively showcasing the enhanced regularization effect of preconditioned SGD.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 37 of its 54 references that are in the map. First posted on arXiv 13 Mar 2024.

Builds on

37 of 54 references.

References · 37

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  2. 2019Benign Overfitting in Linear Regressioncited by 549
  3. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  4. 2018Shampoo: Preconditioned Stochastic Tensor Optimizationcited by 426
  5. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  6. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  7. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  8. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  9. 2021On the Origin of Implicit Regularization in Stochastic Gradient Descentcited by 184
  10. 2020Benign overfitting in ridge regressioncited by 153
  11. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 148
  12. 2020Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learningcited by 126
25 more
  1. 2015Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networkscited by 121
  2. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 119
  3. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  4. 2021Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticitycited by 110
  5. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 98
  6. 2023How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?cited by 96
  7. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  8. 2018A Continuous-Time View of Early Stopping for Least Squarescited by 69
  9. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  10. 2020The Implicit Regularization of Stochastic Gradient Flow for Least Squarescited by 59
  11. 2018Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularizationcited by 53
  12. 2015Preconditioned Stochastic Gradient Descentcited by 50
  13. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 44
  14. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 39
  15. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 33
  16. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  17. 2020When Does Preconditioning Help or Hurt Generalization?cited by 31
  18. 2018Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularizationcited by 29
  19. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 26
  20. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  21. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
  22. 2020Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Studycited by 16
  23. 2016Solving Ridge Regression using Sketched Preconditioned SVRGcited by 15
  24. 2023Meta-Learning with a Geometry-Adaptive Preconditionercited by 11
  25. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Structuring Semantic Embeddings for Principle Evaluation: A Prototype-Guided Contrastive Learning Approachcited by 1
  2. 2026Structuring Relations Among Learning Paradigms via Protocol--Objective--Resource Reductionscited by 0
  3. 2026Feature Normalization under Finite Training Budgetscited by 0