Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks

Pratik Chaudhari; Stefano Soatto

Source-linked AI summary

Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks

Pratik Chaudhari, Stefano Soatto

arXiv:1710.11029v2Oct 30, 2017cs.LGcond-mat.stat-mechmath.OCstat.ML

TL;DR

The paper addresses how SGD implicitly regularizes deep-network training and formalizes this behavior through a steady-state variational analysis. It shows that SGD optimizes an architecture- and dataset-dependent potential with entropy regularization, while anisotropic gradient noise produces non-classical trajectories and a low-rank covariance structure.

Problem
The precise manner in which SGD performs implicit regularization in deep neural networks has remained unclear.
Method
The paper analyzes SGD through its steady-state weight distribution, continuous-time stochastic dynamics, diffusion matrix, and associated variational functional.
Results
SGD performs variational inference for a generally different potential, while deep-network gradient-noise covariance has rank as low as 1% of its dimension and produces closed-loop trajectories.
Takeaways & Limitations
SGD's implicit bias is governed by an entropic regularization term and highly non-isotropic noise rather than necessarily by the original loss landscape or classical convergence.
Takeaways & Limitations
The analysis uses a continuous-time viewpoint, whereas practical deep-network training uses discrete-time updates for only a few epochs.

Abstract

from arXiv · show

Stochastic gradient descent (SGD) is widely believed to perform implicit regularization when used to train deep neural networks, but the precise manner in which this occurs has thus far been elusive. We prove that SGD minimizes an average potential over the posterior distribution of weights along with an entropic regularization term. This potential is however not the original loss function in general. So SGD does perform variational inference, but for a different loss than the one used to compute the gradients. Even more surprisingly, SGD does not even converge in the classical sense: we show that the most likely trajectories of SGD for deep networks do not behave like Brownian motion around critical points. Instead, they resemble closed loops with deterministic components. We prove that such "out-of-equilibrium" behavior is a consequence of highly non-isotropic gradient noise in SGD; the covariance matrix of mini-batch gradients for deep networks has a rank as small as 1% of its dimension. We provide extensive empirical validation of these claims, proven in the appendix.

1 INTRODUCTION

The paper formalizes SGD as variational inference with an implicit potential and entropy term, then shows that anisotropic gradient noise changes both the selected critical points and trajectory behavior.

1 INTRODUCTION: SGD implicitly performs variational inference by minimizing an average potential over weight distributions together with an entropic regularization term.The potential is defined through the steady-state distribution of SGD.
1 INTRODUCTION: The implicit potential depends on the architecture and dataset and is generally different from the loss used to compute back-propagation gradients.SGD therefore corresponds to variational inference with a uniform prior, but for a different loss.
1 INTRODUCTION: 1%: deep-network gradient-noise covariance has approximately 1% of the ambient dimension as its rank, indicating strongly non-isotropic noise.The paper links this anisotropy to differences between the implicit and original loss landscapes.
1 INTRODUCTION: The most likely SGD locations satisfy ∇Φ(x) = 0 rather than necessarily ∇f(x) = 0, and their displacement scales linearly with η/b.The paper reports that this deviation is typically large in practice.
1 INTRODUCTION: Non-isotropic noise gives SGD trajectories a deterministic component that produces closed loops and can generate stable limit cycles around saddle points.The paper detects these loops through Fourier analysis of SGD trajectories.

2 BACKGROUND ON CONTINUOUS-TIME SGD

The paper models discrete SGD with a continuous-time stochastic differential equation whose diffusion is determined by mini-batch gradient variance, under steady-state and boundary assumptions.

2 BACKGROUND ON CONTINUOUS-TIME SGD: SGD updates weights by subtracting the learning rate multiplied by the average gradient over a sampled mini-batch.The update is x_k+1 = x_k − η ∇f_b(x_k).
2 BACKGROUND ON CONTINUOUS-TIME SGD: The diffusion matrix D(x) is the variance of mini-batch gradients and depends on weights, architecture, loss, and dataset, but not directly on η or b.The paper distinguishes isotropic diffusion from general weight-dependent non-isotropic diffusion.
2 BACKGROUND ON CONTINUOUS-TIME SGD: The continuous-time limit represents SGD as a stochastic differential equation driven by Brownian motion, with β determined by learning rate and batch size.This construction leads to a Fokker–Planck equation for the evolving weight distribution.
2 BACKGROUND ON CONTINUOUS-TIME SGD: The continuous-time approximation treats β^-1 as capturing SGD noise magnitude through the learning rate and mini-batch size.The cited convergence result concerns discrete SGD converging to the continuous-time description.
2 BACKGROUND ON CONTINUOUS-TIME SGD: The analysis assumes a unique steady-state distribution for the Fokker–Planck equation and typically restricts weights to a compact subset.The compactness assumption can be replaced by sufficiently growing loss, such as with weight decay.

3 SGD PERFORMS VARIATIONAL INFERENCE

SGD minimizes an energetic–entropic functional over weight distributions, but its potential generally differs from the original loss when gradient noise is non-isotropic. This framework also explains deterministic closed trajectories and predicts how learning rate, batch size, and sampling affect implicit regularization.

SGD minimizes the average potential Φ(x) plus an entropy-dependent regularization term over weight distributions.The functional decreases along Fokker–Planck trajectories and reaches zero at steady state.
Non-isotropic noise introduces a deterministic component that leaves the functional unchanged and drives most likely SGD trajectories through closed loops in weight space.The conservative force does not decrease F(ρ), while the divergence condition implies closed trajectories.
For isotropic noise, Fokker–Planck trajectories become Wasserstein gradient flows of a functional whose energetic term contains the original loss f(x).In this case the framework is equivalent to the JKO functional from optimal transport.
3.2 CONNECTION TO BAYESIAN INFERENCE: The potential Φ(x) depends on the dataset and architecture, not the optimization process, and is generally different from the loss f(x).SGD therefore performs variational inference with a uniform prior, but for a loss distinct from the one used for back-propagation gradients.
Maintaining entropic regularization requires the learning rate η to scale linearly with batch size b, while sampling with replacement is predicted to regularize better at large batch sizes.As β^-1 approaches zero, SGD’s implicit regularization vanishes; sampling without replacement reduces regularization as b approaches N.

4 EMPIRICAL CHARACTERIZATION OF SGD DYNAMICS

Experiments find that deep-network gradient noise is highly low-rank and non-isotropic, while SGD trajectories contain structured periodic components rather than behaving like Brownian motion.

4.1 Highly non-isotropic D(x) for deep networks: 0.3%–2%: The diffusion matrix’s effective rank is very small across tested networks, with non-zero eigenvalues spanning a wide range.The eigenspectrum also has substantial variance.
4.1 Highly non-isotropic D(x) for deep networks: CIFAR-10 and CIFAR-100 exhibit larger diffusion eigenvalues than MNIST, suggesting greater gradient diversity.CIFAR-100 has larger eigenvalues, greater non-isotropy, and higher rank than the compared CIFAR-10 setting.
4.1 Highly non-isotropic D(x) for deep networks: Data augmentation increases the mean and variance of diffusion eigenvalues while leaving rank almost constant.The comparison is between the corresponding CIFAR eigenspectra.
4.2 Analysis of long-term trajectories: The FFT and autocorrelation analyses reveal low-frequency periodic components and long-lag correlations, inconsistent with white-noise-driven Brownian trajectories.The experiments compare the observed spectra and correlations with flat FFTs and rapidly decaying Brownian-motion autocorrelation.
4.2 Analysis of long-term trajectories: The full-gradient norm remains large during the recorded trajectory, dropping by only about a factor of 3 over the subsequent training period.This behavior is associated with SGD remaining away from critical points.

5 SGD FOR DEEP NETWORKS IS OUT-OF-EQUILIBRIUM

The analysis shows that non-isotropic diffusion changes SGD’s effective potential and most likely states, producing rotational, out-of-equilibrium dynamics that can include limit cycles.

5 SGD for deep networks is out-of-equilibrium: An explicit potential Φ may fail to exist globally because D(x)^−1∇f(x) need not be a gradient field.The authors therefore separate local critical-point analysis from the general case.
5.2 General case: Large non-isotropic force components can produce stable limit cycles around saddle points instead of convergence to local minima.The phenomenon is illustrated by the double-well example and its gradient-field visualization.
5.2 General case: The force field can rotate gradients and shift critical points, so the most likely locations of SGD need not be critical points of the original loss.The potential and antisymmetric component are computed from ∇f(x) and D(x).
5.2 General case: The out-of-equilibrium effect persists even when D is constant, provided it is non-isotropic.The paper reports that deep-network diffusion is nearly weight-independent while the effect remains observable.
5.2 General case: Higher learning rates or smaller batches amplify out-of-equilibrium behavior, while the implicit entropic regularization vanishes as β^−1 approaches zero.The paper connects these regimes to commonly used deep-learning training conditions.
5.2 General case: Actively constructing out-of-equilibrium behavior has been associated with good generalization, and the authors infer a similar role for SGD’s intrinsic behavior.The stated connection is supported by comparisons with local-entropy and wide-minima approaches.

6 RELATED WORK

Related work frames SGD as variational inference, implicit regularization, noise-assisted optimization, and a mechanism connected to gradient diversity and non-equilibrium sampling.

6 Related work: Earlier variational-inference accounts of SGD relied on assumptions such as quadratic steady states, whereas this paper analyzes SGD’s properties more generally.The paper positions its treatment as distinct from approximation methods for steady states.
6 Related work: The paper links deep-network architecture to implicit regularization through highly non-isotropic gradient noise and an effective potential supporting generalization and acceleration.This frames SGD’s empirical performance as consistent with its implicit-regularization interpretation.
6 Related work: Prior work studies externally added noise for saddle-point optimization, while SGD uses its own mini-batch noise during deep-network training.The related literature includes both theoretical noise injection and practical stochastic optimization.
6 Related work: Gradient-diversity work introduced scalar measures for analyzing allowable batch sizes in distributed optimization.The cited approach differs in focusing on a scalar diversity measure rather than the diffusion-matrix dynamics developed here.
6 Related work: Unlike MCMC methods that design a force to accelerate sampling, this paper computes the effective potential from the gradient and diffusion matrix.The nonzero force in deep networks is attributed to non-isotropic gradient noise.

7 DISCUSSION

The paper highlights a gap between its continuous-time analysis of SGD and practical discrete-time training, while identifying conditions under which steady state may be reached quickly.

Continuous-time analysis provides general principles governing SGD, but practical deep-network training uses discrete-time updates for only a few epochs.The paper identifies closing this theory–practice gap as an important future direction.
Small mini-batches or large learning rates can make SGD converge quickly to its steady-state distribution under typical practical conditions.

B DISCUSSION ON ASSUMPTION 4

The discussion connects Fokker–Planck dynamics to nonequilibrium thermodynamics and variational principles, showing how entropy production and probability currents characterize the dynamics.

The Fokker–Planck equation can be expressed through a probability current, linking density evolution to the flow of probability.
Nonzero conservative force occurs only when detailed balance is broken, meaning the steady-state probability current is nonzero.
A divergence-free current component is orthogonal to the gradient of the potential and does not change the relevant functional.
Variational principles interpret certain partial differential equations as steepest descent on functionals of their state distributions.
The heat equation admits equivalent interpretations as minimizing Dirichlet energy or as gradient flow of negative Shannon entropy in the Wasserstein metric.

E EXPERIMENTAL SETUP

Experiments use compact deep-network models on MNIST, CIFAR-10, and CIFAR-100, trained with SGD while retaining architectural features relevant to the analysis.

The experiments evaluate three networks on MNIST, CIFAR-10, and CIFAR-100.
The small-Lenet model has 13,338 weights and reaches about 0.75% training and validation error on MNIST.
The small-allcnn model has 26,982 weights and reaches about 11% and 17% training and validation errors, respectively.
Training uses SGD with learning-rate annealing and Nesterov momentum set to 0.9, without data augmentation.
Networks with about 20,000 weights make eigen-decomposition of D(x) tractable while preserving convolutions, dropout, and batch normalization.

F.1 THEOREM 5

The theorem decomposes Fokker–Planck dynamics into functional-changing and functional-conserving components, with deterministic anti-symmetric motion generating the most likely steady-state trajectories.

The KL-divergence functional is non-negative and equals zero only when the distribution matches the steady-state distribution.
The functional decreases over time and reaches its minimum only at the steady state of the Fokker–Planck equation.
The derivation uses suitable boundary conditions preventing probability mass from crossing the domain boundary and the positive-semidefinite covariance property of D(x).
The Fokker–Planck operator is split into symmetric and anti-symmetric components.
The anti-symmetric operator leaves the functional unchanged and describes completely deterministic dynamics through a Liouville equation.
The deterministic trajectories of the Liouville operator are the most likely trajectories under the steady-state distribution proportional to e^(-βΦ).

F.4 THEOREM 22

The section transforms the original stochastic dynamics into an equivalent formulation and derives the steady-state potential. It shows that the critical points of this potential differ from those of the original loss by a divergence-dependent term.

The original SDE is transformed into a new SDE whose deterministic and stochastic terms are matched.The construction decomposes G^-1 into symmetric and anti-symmetric parts, S and A.
The potential is obtained through a formal path-dependent expression using a curve from the initial condition to the current weight.The resulting potential does not depend on β because G(x) does not depend on β.
The modified SDE is rewritten as a second-order Langevin system, then analyzed through its Fokker–Planck equation and zero-mass limit.This yields a steady-state distribution with decoupled position and momentum variables.
The anti-symmetric matrix Q contributes no second-derivative term because its anti-symmetry makes the corresponding divergence expression vanish.This simplification is used when matching the relevant Fokker–Planck equations.
The critical points of Φ differ from those of f by the term β^-1∇·(D+Q).Thus, the most likely SGD locations are determined by the potential Φ rather than necessarily by critical points of the original loss.