# From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 63 references that are in the map.
- First posted on arXiv 13 Oct 2022.

## Builds on (most cited first, 30 of 38)

- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent](https://mlsanity.com/paper/2102.09769/) (2021)
- [Implicit Regularization in ReLU Networks with the Square Loss](https://mlsanity.com/paper/2012.05156/) (2020)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [LQR through the Lens of First Order Methods: Discrete-time Case](https://mlsanity.com/paper/1907.08921/) (2019)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Continuous vs. Discrete Optimization of Deep Neural Networks](https://mlsanity.com/paper/2107.06608/) (2021)
- [Continuous Time Analysis of Momentum Methods](https://mlsanity.com/paper/1906.04285/) (2019)
- [Optimizing Static Linear Feedback: Gradient Method](https://mlsanity.com/paper/2004.09875/) (2020)
- [Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems](https://mlsanity.com/paper/1411.1134/) (2014)
- [Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysis](https://mlsanity.com/paper/2106.02588/) (2021)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent](https://mlsanity.com/paper/2004.01025/) (2020)

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

- [Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?](https://mlsanity.com/paper/2410.08292/) (2024)
- [Convergence of continuous-time stochastic gradient descent with applications to deep neural networks](https://mlsanity.com/paper/2409.07401/) (2024)
- [Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networks](https://mlsanity.com/paper/2304.09221/) (2023)
- [Dr. FERMI: A Stochastic Distributionally Robust Fair Empirical Risk Minimization Framework](https://mlsanity.com/paper/2309.11682/) (2023)
- [Langevin Dynamics: A Unified Perspective on Optimization via Lyapunov Potentials](https://mlsanity.com/paper/2407.04264/) (2024)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) has been the method of choice for learning large-scale non-convex models. While a general analysis of when SGD works has been elusive, there has been a lot of recent progress in understanding the convergence of Gradient Flow (GF) on the population loss, partly due to the simplicity that a continuous-time analysis buys us. An overarching theme of our paper is providing general conditions under which SGD converges, assuming that GF on the population loss converges. Our main tool to establish this connection is a general converse Lyapunov like theorem, which implies the existence of a Lyapunov potential under mild assumptions on the rates of convergence of GF. In fact, using these potentials, we show a one-to-one correspondence between rates of convergence of GF and geometrical properties of the underlying objective. When these potentials further satisfy certain self-bounding properties, we show that they can be used to provide a convergence guarantee for Gradient Descent (GD) and SGD (even when the paths of GF and GD/SGD are quite far apart). It turns out that these self-bounding assumptions are in a sense also necessary for GD/SGD to work. Using our framework, we provide a unified analysis for GD/SGD not only for classical settings like convex losses, or objectives that satisfy PL / KL properties, but also for more complex problems including Phase Retrieval and Matrix sq-root, and extending the results in the recent work of Chatterjee 2022.