# First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2019.

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

- [On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)](https://mlsanity.com/paper/2102.12470/) (2021)
- [Anticorrelated Noise Injection for Improved Generalization](https://mlsanity.com/paper/2202.02831/) (2022)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [Explicit Regularization in Overparametrized Models via Noise Injection](https://mlsanity.com/paper/2206.04613/) (2022)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions](https://mlsanity.com/paper/2301.11885/) (2023)
- [On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control](https://mlsanity.com/paper/2106.08414/) (2021)
- [On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spaces](https://mlsanity.com/paper/2201.12332/) (2022)
- [Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal States](https://mlsanity.com/paper/2211.10691/) (2022)
- [Taming Fat-Tailed ("Heavier-Tailed'' with Potentially Infinite Variance) Noise in Federated Learning](https://mlsanity.com/paper/2210.00690/) (2022)
- [Models of Heavy-Tailed Mechanistic Universality](https://mlsanity.com/paper/2506.03470/) (2025)
- [From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networks](https://mlsanity.com/paper/2406.04657/) (2024)
- [Normalization Layer Per-Example Gradients are Sufficient to Predict Gradient Noise Scale in Transformers](https://mlsanity.com/paper/2411.00999/) (2024)
- [Efficient Distributed Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2502.04164/) (2025)
- [Exponential escape efficiency of SGD from sharp minima in non-stationary regime](https://mlsanity.com/paper/2111.04004/) (2021)
- [On the Theoretical Properties of Noise Correlation in Stochastic Optimization](https://mlsanity.com/paper/2209.09162/) (2022)
- [From Mutual Information to Expected Dynamics: New Generalization Bounds for Heavy-Tailed SGD](https://mlsanity.com/paper/2312.00427/) (2023)
- [Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping](https://mlsanity.com/paper/2403.02051/) (2024)
- [On the Trade-off between Flatness and Optimization in Distributed Learning](https://mlsanity.com/paper/2406.20006/) (2024)
- [Generative AI Models for Learning Flow Maps of Stochastic Dynamical Systems in Bounded Domains](https://mlsanity.com/paper/2507.15990/) (2025)
- [Efficient Adaptive Federated Optimization](https://mlsanity.com/paper/2410.18117/) (2024)
- [Almost Bayesian: The Fractal Dynamics of Stochastic Gradient Descent](https://mlsanity.com/paper/2503.22478/) (2025)
- [Variational Learning Finds Flatter Solutions at the Edge of Stability](https://mlsanity.com/paper/2506.12903/) (2025)
- [On the Superlinear Relationship between SGD Noise Covariance and Loss Landscape Curvature](https://mlsanity.com/paper/2602.05600/) (2026)
- [Generalization at the Edge of Stability](https://mlsanity.com/paper/2604.19740/) (2026)
- [Understanding Short-Range Memory Effects in Deep Neural Networks](https://mlsanity.com/paper/2105.02062/) (2021)
- [A note on diffusion limits for stochastic gradient descent](https://mlsanity.com/paper/2210.11257/) (2022)
- [Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models](https://mlsanity.com/paper/2303.17109/) (2023)
- [Weight fluctuations in (deep) linear neural networks and a derivation of the inverse-variance flatness relation](https://mlsanity.com/paper/2311.14120/) (2023)

## Abstract (arXiv)

Stochastic gradient descent (SGD) has been widely used in machine learning due to its computational efficiency and favorable generalization properties. Recently, it has been empirically demonstrated that the gradient noise in several deep learning settings admits a non-Gaussian, heavy-tailed behavior. This suggests that the gradient noise can be modeled by using α-stable distributions, a family of heavy-tailed distributions that appear in the generalized central limit theorem. In this context, SGD can be viewed as a discretization of a stochastic differential equation (SDE) driven by a L'evy motion, and the metastability results for this SDE can then be used for illuminating the behavior of SGD, especially in terms of `preferring wide minima'. While this approach brings a new perspective for analyzing SGD, it is limited in the sense that, due to the time discretization, SGD might admit a significantly different behavior than its continuous-time limit. Intuitively, the behaviors of these two systems are expected to be similar to each other only when the discretization step is sufficiently small; however, to the best of our knowledge, there is no theoretical understanding on how small the step-size should be chosen in order to guarantee that the discretized system inherits the properties of the continuous-time system. In this study, we provide formal theoretical analysis where we derive explicit conditions for the step-size such that the metastability behavior of the discrete-time system is similar to its continuous-time limit. We show that the behaviors of the two systems are indeed similar for small step-sizes and we identify how the error depends on the algorithm and problem parameters. We illustrate our results with simulations on a synthetic model and neural networks.