mlsanityData to 7 Oct 2026

Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis

arXiv 2105.01650 ↗First posted 4 May 2021stat.ML cs.LG math.OCcited by 38

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) is one of the most popular algorithms in modern machine learning. The noise encountered in these applications is different from that in many theoretical analyses of stochastic gradient algorithms. In this article, we discuss some of the common properties of energy landscapes and stochastic noise encountered in machine learning problems, and how they affect SGD-based optimization. In particular, we show that the learning rate in SGD with machine learning noise can be chosen to be small, but uniformly positive for all times if the energy landscape resembles that of overparametrized deep learning problems. If the objective function satisfies a Lojasiewicz inequality, SGD converges to the global minimum exponentially fast, and even for functions which may have local minima, we establish almost sure convergence to the global minimum at an exponential rate from any finite energy initialization. The assumptions that we make in this result concern the behavior where the objective function is either small or large and the nature of the gradient noise, but the energy landscape is fairly unconstrained on the domain where the objective function takes values in an intermediate regime.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). Builds on 23 of its 44 references that are in the map. First posted on arXiv 4 May 2021.

Builds on

23 of 44 references.

References · 23

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  5. 2020A Simple Convergence Proof of Adam and Adagradcited by 169
  6. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  7. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
  8. 2015Stochastic modified equations and adaptive stochastic gradient algorithmscited by 141
  9. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  10. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  11. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  12. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
11 more
  1. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  2. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 79
  3. 2019Convergence rates for the stochastic gradient descent method for non-convex objective functionscited by 66
  4. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  5. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  6. 2018The loss landscape of overparameterized neural networkscited by 38
  7. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  8. 2019Linear Convergence of Adaptive Stochastic Gradient Descentcited by 29
  9. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 27
  10. 2020Stopping Criteria for, and Strong Convergence of, Stochastic Gradient Descent on Bottou-Curtis-Nocedal Functionscited by 13
  11. 2019Loss Patterns of Neural Networkscited by 10

Built on by

Cited by year (2026 to 7 Oct)

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

38 papers.

Sort:

  1. 2021Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticitycited by 107
  2. 2023Why Do We Need Weight Decay in Modern Deep Learning?cited by 70
  3. 2022SGD with Large Step Sizes Learns Sparse Featurescited by 66
  4. 2022Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisationcited by 29
  5. 2021Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysiscited by 25
  6. 2024Mask in the Mirror: Implicit Sparsificationcited by 12
  7. 2021A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functionscited by 10
  8. 2021Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functionscited by 9
  9. 2022On the generalization of learning algorithms that do not convergecited by 9
  10. 2021SGD with a Constant Large Learning Rate Can Converge to Local Maximacited by 8
  11. 2023A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descentcited by 8
  12. 2025ODE approximation for the Adam algorithm: General and overparametrized settingcited by 8
26 more
  1. 2023Exponential convergence rates for momentum stochastic gradient descent in the overparametrized settingcited by 7
  2. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  3. 2023On the existence of minimizers in shallow residual ReLU neural network optimization landscapescited by 6
  4. 2024Nesterov acceleration in benignly non-convex landscapescited by 6
  5. 2022From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descentcited by 5
  6. 2024Maxwell's Demon at Work: Efficient Pruning by Leveraging Saturation of Neuronscited by 5
  7. 2024Singular-limit analysis of gradient descent with noise injectioncited by 5
  8. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  9. 2023Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networkscited by 3
  10. 2023A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spacescited by 3
  11. 2024Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descentcited by 3
  12. 2025Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularizationcited by 3
  13. 2022On Uniform Boundedness Properties of SGD and its Momentum Variantscited by 2
  14. 2024Implicit Bias in Noisy-SGD: With Applications to Differentially Private Trainingcited by 2
  15. 2024Exploring Ordinality in Text Classification: A Comparative Study of Explicit and Implicit Techniquescited by 2
  16. 2024Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGDcited by 2
  17. 2024Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequalitycited by 2
  18. 2025Generalization Bounds for Markov Algorithms through Entropy Flow Computationscited by 2
  19. 2023Weight fluctuations in (deep) linear neural networks and a derivation of the inverse-variance flatness relationcited by 1
  20. 2024Sampling with Adaptive Variance for Multimodal Distributionscited by 1
  21. 2021Combining resampling and reweighting for faithful stochastic optimizationcited by 0
  22. 2022Analysis of Kinetic Models for Label Switching and Stochastic Gradient Descentcited by 0
  23. 2025Artificial Liver Classifier: A New Alternative to Conventional Machine Learning Modelscited by 0
  24. 2025Adaptive Learning Guided by Bias-Noise-Alignment Diagnosticscited by 0
  25. 2026Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approachcited by 0
  26. 2026HORST: Composing Optimizer Geometries for Sparse Transformer Trainingcited by 0