Research map / Optimization / Implicit bias and generalization
What is the Long-Run Distribution of Stochastic Gradient Descent? A Large Deviations Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows via large deviations (Freidlin–Wentzell style) that the long-run distribution of constant-step SGD over critical components follows a Boltzmann–Gibbs law with temperature equal to the step-size and energies determined by the objective and noise statistics.
Problem
Characterize which critical regions of a general non-convex objective are visited by SGD in the long run (constant step-size), and by how much, since existing diffusion/Langevin approximations break down as step-size goes to zero.
Approach
Establishes a large deviations principle for discrete-time SGD over unbounded domains with general (possibly discrete) noise, by accelerating iterates and extending Freidlin–Wentzell/Kolokoltsov-type theory; derives transition costs (quasi-potential), energies via minimum spanning in-trees, and shows the invariant measure is approximately Boltzmann–Gibbs with temperature equal to the step-size.
Key results
- Critical region is visited exponentially more often than non-critical regions: invariant measure of the non-critical neighborhood is at least 1 - exp(-c/step).
- Long-run mass near each critical component is proportional to exp(-energy/step), with energy computed from transition costs via minimum spanning in-trees.
- For Gaussian noise with variance sigma^2, energy of component i equals 2 f(x_i)/sigma^2 up to a constant, so ground state can differ from global minimum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use constant step-size SGD with the stated assumptions | SGD · Non-convex objectives, long run | invariant probability near critical components | Mixed |
| Use Gaussian gradient noise | SGD · Non-convex objectives, long run | energy of critical components | Helped |
| Use a smaller step-size | SGD · Non-convex objectives, long run | concentration around the minimum-energy state | Helped |
Surprising findings
- The ground state (lowest-energy component) need not coincide with the global minimum of the objective, since noise statistics matter; flatter minima can be favored over deeper ones.
Limitations
- Energy levels are not estimated in practical settings; the paper only characterizes them theoretically.
- Results are asymptotic and hold for sufficiently small step-size and only for the unconstrained setting.
- Assumes finitely many smoothly connected critical components and sub-Gaussian noise with a SNR condition.
Experimental setup
Benchmarks: Himmelblau test function
Metrics: long-run occupation measure vs theoretical Boltzmann-Gibbs p
Baselines: SGLD stochastic modified equation approximation
Builds on: Freidlin-Wentzell theory Langevin dynamics / SGLD least action principle
Closest papers by meaning
- The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.91)
- Emergence of heavy tails in homogenized stochastic gradient descent (NeurIPS 2024 · similarity 0.89)
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.88)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.88)
- High-dimensional Limit of SGD for Diagonal Linear Networks (NeurIPS 2026 · similarity 0.88)
- Generalization of noisy SGD in unbounded non-convex settings (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.