Source-linked AI summary
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
Umut Simsekli, Levent Sagun, Mert Gurbuzbalaban
TL;DR
The paper asks whether Gaussian gradient-noise assumptions adequately describe SGD in deep learning. It replaces the Gaussian approximation with an α-stable, Lévy-driven framework and finds consistently heavy-tailed, highly non-Gaussian noise across configurations, while noting limits in the supporting theory and analysis.
Problem
A satisfactory theory explaining SGD’s empirical behavior remains lacking, while common analyses assume Gaussian stochastic gradient noise via the central limit theorem.
Method
The paper invokes the generalized central limit theorem, models gradient noise with an α-stable distribution, and analyzes SGD through a Lévy-motion-driven SDE.
Results
Across common architectures, loss functions, datasets, network sizes, and batch sizes, stochastic gradient noise is highly non-Gaussian and heavy-tailed.
Takeaways & Limitations
The findings provide an alternative perspective on SGD dynamics and shed more light on the view that SGD prefers wide minima.
Abstract
from arXiv · showhide
The gradient noise (GN) in the stochastic gradient descent (SGD) algorithm is often considered to be Gaussian in the large data regime by assuming that the classical central limit theorem (CLT) kicks in. This assumption is often made for mathematical convenience, since it enables SGD to be analyzed as a stochastic differential equation (SDE) driven by a Brownian motion. We argue that the Gaussianity assumption might fail to hold in deep learning settings and hence render the Brownian motion-based analyses inappropriate. Inspired by non-Gaussian natural phenomena, we consider the GN in a more general context and invoke the generalized CLT (GCLT), which suggests that the GN converges to a heavy-tailed $α$-stable random variable. Accordingly, we propose to analyze SGD as an SDE driven by a Lévy motion. Such SDEs can incur `jumps', which force the SDE transition from narrow minima to wider minima, as proven by existing metastability theory. To validate the $α$-stable assumption, we conduct extensive experiments on common deep learning architectures and show that in all settings, the GN is highly non-Gaussian and admits heavy-tails. We further investigate the tail behavior in varying network architectures and sizes, loss functions, and datasets. Our results open up a different perspective and shed more light on the belief that SGD prefers wide minima.
1 Introduction
The introduction questions Gaussian gradient-noise assumptions in SGD, arguing that heavy-tailed noise and Lévy-driven dynamics better reflect deep-learning behavior. It motivates this framework through empirical evidence, theoretical contradictions, and extensive tail-index experiments.
- Background: SGD optimizes a generally non-convex neural-network loss through stochastic updates based on minibatch gradients.The stochastic gradient is formed from a randomly sampled subset of data points, whose size is the minibatch size.
- Gaussian approximation: A common analysis treats stochastic gradient noise as Gaussian via the central limit theorem and models SGD with Brownian-motion-driven SDEs.Under this approximation, SGD corresponds to a discretization of Langevin dynamics with an invariant measure related to the loss landscape.
- Theoretical issues: The Gaussian framework faces a finite-iteration problem because convergence to its invariant measure can require exponentially many iterations in network dimension.This prevents the asymptotic distribution from explaining wide-minima preference within the limited iteration budgets typical of deep learning.
- Theoretical issues: Brownian metastability theory predicts exit times dominated exponentially by basin height but only polynomially by width, favoring deeper rather than wider minima.The authors attribute this mismatch to the continuity of Brownian paths under Gaussian noise.
- Proposed framework: The paper relaxes finite-variance assumptions, invokes the generalized central limit theorem, and replaces Brownian motion with α-stable Lévy motion.Lévy-driven dynamics can make discontinuous jumps, providing an alternative theoretical perspective on SGD and wide-minima behavior.
- Empirical findings: Across tested architectures, losses, datasets, network sizes, and batch sizes, gradient noise is highly non-Gaussian and heavy-tailed, while minibatch size has little effect on its tail index.The experiments also report architecture-, size-, and dataset-dependent tail behavior and an early phase with a jump when the tail index is lowest.
2 Stable distributions and SGD as a Lévy-Driven SDE
The paper replaces Gaussian gradient-noise modeling with symmetric α-stable noise and a Lévy-driven SDE. Unlike Brownian dynamics, Lévy jumps yield transition behavior governed mainly by basin width, supporting greater occupation of wider valleys.
- Stable distributions: For heavy-tailed variables with tail index 0 < α < 2, the generalized CLT yields an α-stable distribution instead of a Gaussian.Its density decays like 1/|x|^(α+1), and only moments of order r < α are finite.
- Stable distributions: The proposed model assumes each coordinate of the stochastic gradient noise is symmetric α-stable with common α and state-dependent scale σ(w).The scale is not central to the tail-index analysis, so it is denoted simply by σ.
- Lévy-driven SDE: For small step sizes, SGD is reformulated as an SDE driven by a multidimensional α-stable Lévy motion rather than Brownian motion.The Lévy process has independent α-stable components; α = 2 recovers a scaled Brownian-motion case.
- Metastability: When α < 2, Lévy paths can jump across basin boundaries, so transitions depend mainly on basin width rather than requiring the process to climb basin height.For α = 2, continuous Brownian paths must climb out of the basin, making transition time depend on basin height.
- Metastability: In the small-noise limit, Lévy-driven transition times scale polynomially as 1/ε^α, whereas Brownian-driven transitions require exponential time involving basin depth.The Lévy transition-time tail is bounded by an exponential form after ε^α scaling.
- Wide-valley occupation: After time normalization, the Lévy-driven process converges to a finite-state Markov chain over local minima, whose equilibrium probabilities are typically larger for wider valleys.In the two-valley example, π2 > π1 for the wider second valley, and the ratio grows with the valley-width ratio raised to α.
3 Experimental Setup and Methodology
The experiments measure stochastic-gradient tail behavior across fully connected and convolutional settings, datasets, architectures, losses, and minibatch sizes. The study uses an α-stable-specific estimator after constructing gradient-noise samples from partitioned data.
- Experimental setup: The study varies FCN depth from 2 to 10 layers, width from 2 to 1024 neurons, and minibatch size from 1 to full batch on MNIST and CIFAR10.It also evaluates a convolutional neural network architecture.
- Experimental setup: Both fully connected and convolutional models use cross-entropy and linear hinge losses, with three random seeds per configuration and unmodified SGD.Training logs include training and test accuracy plus estimated gradient-noise tails.
- Tail-index estimation: The estimator is designed specifically for α-stable distributions because several popular extreme-value estimators may fail on α-stable data.The selected estimator has a provably faster convergence rate and smaller asymptotic variance than the alternatives cited.
- Tail-index estimation: The estimator is accurate across a large range of α values in a preliminary experiment using 100 repetitions for each α.The experiment uses K1 = 100 and K2 = 1000 for 100 different α values.
- Tail-index estimation: Tail-index estimation partitions the dataset into disjoint minibatches, computes full and stochastic gradients, concatenates the resulting noise vectors, and applies the estimator.For this construction, the estimator uses K = pn/b samples and a divisor K1 chosen near the prescribed target.
4 Results
Experiments find strongly non-Gaussian gradient noise across architectures, datasets, network sizes, and minibatch settings, with tail behavior varying by configuration and iteration. Early SGD can exhibit a jump after the tail index reaches a minimum.
- Network size: Estimated α remained far from 2 across FCN configurations, with estimate variance around 0.001, indicating highly non-Gaussian gradient noise.
- Network size: On MNIST, α systematically decreased as FCN network size increased, especially with greater depth, implying heavier-tailed noise.
- Network size: For CIFAR10, α stayed in the range 1.1–1.2 without a clear network-size effect.
- Network size: For CIFAR10 and CIFAR100, α increased from extremely low values in under-parametrized networks and stabilized around 1.0–1.1 as networks became reasonably capable.
- Network size: Network architecture and dataset jointly influenced gradient-noise characteristics and algorithm dynamics, including the measured tail index α.
- Minibatch size: Increasing minibatch size did not increase α toward Gaussian behavior; α stayed nearly constant at depth 2 and varied only within a small interval at depth 4.
- Tail behavior throughout iterations: In the representative 9-layer, 512-neuron FCN, α rapidly decreased during an initial phase, then a jump occurred at its lowest level before accuracy recovered.
- Tail behavior throughout iterations: The jump supports the proposed assumptions and metastability theory, while the analysis cannot determine whether it reaches another basin or a better region of the same basin.
5 Conclusion and Open Problems
The conclusion presents heavy-tailed, non-Gaussian gradient noise as a basis for Lévy-driven SGD analysis and a bridge to metastability theory. It also identifies unresolved questions about discretization, state-dependent tail indices, and zero modes.
- Empirical evidence that gradient noise is highly non-Gaussian enabled analysis of SGD as an SDE driven by Lévy motion.
- The Lévy-motion perspective connects SGD with theoretical results that illuminate its behavior, particularly regarding the selection of wide minima.
- Open problems: Metastability theory for the discretized process and its dependence on step-size and minibatch size remain unclear.
- Open problems: Because α depends on the current state during early iterations, stable-like processes with time-dependent tail indices are suggested, but their metastability theory remains immature.
- Open problems: An extension of metastability theory to minima with zero modes is still missing.