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

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

## Key facts

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

## Builds on (most cited first, 23 of 23)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic modified equations and adaptive stochastic gradient algorithms](https://mlsanity.com/paper/1511.06251/) (2015)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [Convergence rates for the stochastic gradient descent method for non-convex objective functions](https://mlsanity.com/paper/1904.01517/) (2019)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [The loss landscape of overparameterized neural networks](https://mlsanity.com/paper/1804.10200/) (2018)
- [On exponential convergence of SGD in non-convex over-parametrized learning](https://mlsanity.com/paper/1811.02564/) (2018)
- [Linear Convergence of Adaptive Stochastic Gradient Descent](https://mlsanity.com/paper/1908.10525/) (2019)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [Stopping Criteria for, and Strong Convergence of, Stochastic Gradient Descent on Bottou-Curtis-Nocedal Functions](https://mlsanity.com/paper/2004.00475/) (2020)
- [Loss Patterns of Neural Networks](https://mlsanity.com/paper/1910.03867/) (2019)

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

- [Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity](https://mlsanity.com/paper/2106.09524/) (2021)
- [Why Do We Need Weight Decay in Modern Deep Learning?](https://mlsanity.com/paper/2310.04415/) (2023)
- [SGD with Large Step Sizes Learns Sparse Features](https://mlsanity.com/paper/2210.05337/) (2022)
- [Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation](https://mlsanity.com/paper/2206.09841/) (2022)
- [Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysis](https://mlsanity.com/paper/2106.02588/) (2021)
- [Mask in the Mirror: Implicit Sparsification](https://mlsanity.com/paper/2408.09966/) (2024)
- [A 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 functions](https://mlsanity.com/paper/2108.04620/) (2021)
- [ODE approximation for the Adam algorithm: General and overparametrized setting](https://mlsanity.com/paper/2511.04622/) (2025)
- [Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2112.07369/) (2021)
- [On the generalization of learning algorithms that do not converge](https://mlsanity.com/paper/2208.07951/) (2022)
- [A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descent](https://mlsanity.com/paper/2310.00692/) (2023)
- [SGD with a Constant Large Learning Rate Can Converge to Local Maxima](https://mlsanity.com/paper/2107.11774/) (2021)
- [Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting](https://mlsanity.com/paper/2302.03550/) (2023)
- [Singular-limit analysis of gradient descent with noise injection](https://mlsanity.com/paper/2404.12293/) (2024)
- [Nesterov acceleration in benignly non-convex landscapes](https://mlsanity.com/paper/2410.08395/) (2024)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [On the existence of minimizers in shallow residual ReLU neural network optimization landscapes](https://mlsanity.com/paper/2302.14690/) (2023)
- [Maxwell's Demon at Work: Efficient Pruning by Leveraging Saturation of Neurons](https://mlsanity.com/paper/2403.07688/) (2024)
- [From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent](https://mlsanity.com/paper/2210.06705/) (2022)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networks](https://mlsanity.com/paper/2304.09221/) (2023)
- [A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces](https://mlsanity.com/paper/2310.17610/) (2023)
- [Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descent](https://mlsanity.com/paper/2407.02322/) (2024)
- [Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality](https://mlsanity.com/paper/2410.16849/) (2024)
- [Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization](https://mlsanity.com/paper/2505.11434/) (2025)
- [On Uniform Boundedness Properties of SGD and its Momentum Variants](https://mlsanity.com/paper/2201.10245/) (2022)
- [Implicit Bias in Noisy-SGD: With Applications to Differentially Private Training](https://mlsanity.com/paper/2402.08344/) (2024)
- [Exploring Ordinality in Text Classification: A Comparative Study of Explicit and Implicit Techniques](https://mlsanity.com/paper/2405.11775/) (2024)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Generalization Bounds for Markov Algorithms through Entropy Flow Computations](https://mlsanity.com/paper/2502.07584/) (2025)

## 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.