📊 statistics

What is the long-run distribution of stochastic gradient descent? A large deviations analysis

This paper employs large deviations theory to demonstrate that the long-run distribution of stochastic gradient descent in non-convex problems resembles a Boltzmann-Gibbs distribution, causing the algorithm to exponentially favor critical regions with lower energy states over non-critical areas, local maximizers, and saddle points.

Original authors: Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

Published 2026-05-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy, and incredibly complex mountain range. This mountain range represents the "loss landscape" of a machine learning problem. The valleys are good solutions (low error), the peaks are bad solutions (high error), and the flat, tricky spots in between are "saddle points" (places that look like a valley from one direction but a hill from another).

Your goal is to find the deepest valley (the global minimum). You have a tool called Stochastic Gradient Descent (SGD). Think of SGD as a hiker who is trying to walk downhill. However, this hiker is slightly drunk or walking on a bumpy, shaking path. Every time they take a step, they get a noisy, slightly wrong reading of which way is down.

For decades, we knew this hiker would eventually stop moving around a lot (converge), but we didn't know where they would finally settle down. Would they get stuck in a shallow valley? Would they wander aimlessly near a saddle point? Or would they find the deepest valley?

This paper answers that question by treating the hiker's journey like a game of physics.

The Big Idea: The Hiker is a Gas Molecule

The authors realized that the long-term behavior of this "drunk hiker" (SGD) looks exactly like the behavior of gas molecules in a room.

The Room: The entire mountain range (the problem's state space).
The Molecules: The hiker's position at any given time.
The Temperature: The step-size (how big the hiker's steps are).
- If the step-size is large, the hiker is "hot" and energetic. They bounce around wildly, jumping over small hills and exploring the whole room.
- If the step-size is tiny, the hiker is "cold." They move slowly and get stuck in the nearest dip.
The Energy: The height of the mountain at that spot (the objective function value).

The paper proves that, after a long time, the hiker doesn't just pick a random spot. They settle into a specific pattern called the Boltzmann-Gibbs distribution. In plain English, this means:

Low spots are crowded: The hiker spends the most time in the deepest valleys.
High spots are empty: The hiker rarely visits the peaks.
The "Temperature" matters: The bigger the step-size (the hotter the system), the more likely the hiker is to jump out of a shallow valley and explore higher ground.

The Four Key Discoveries

The paper breaks down exactly where the hiker ends up using four main rules:

1. The Hiker Loves "Critical" Spots
The hiker spends almost all their time in "critical regions." These are the flat spots where the ground is perfectly level (mathematically, where the gradient is zero). This includes the bottoms of valleys, the tops of peaks, and the tricky saddle points. The hiker almost never stops on a steep slope because gravity (the math) pulls them off immediately.

2. The "Ground State" is the Favorite
Among all the flat spots, there is one specific set of valleys that the hiker visits exponentially more often than any other spot. The authors call this the "ground state."

Crucial Twist: This "ground state" isn't always the absolute deepest valley in the entire mountain range. It depends on the noise (the shaking of the path). Sometimes, a slightly higher valley is "flatter" or "safer" from the noise, making it the preferred resting spot. The hiker chooses the spot that minimizes a specific "energy" that combines the valley's depth and how the noise affects it.

3. The Hierarchy of Visits
If the hiker isn't in the absolute favorite spot, they still follow a strict hierarchy:

They visit local minima (small valleys) much more often than saddle points (the tricky flat spots).
They visit saddle points much more often than local maxima (peaks).
Basically, the hiker avoids peaks and saddle points, preferring to rest in valleys. If they do visit a saddle point, it's only because they are temporarily stuck there before the noise pushes them toward a valley.

4. The "Energy" Calculation
The paper provides a formula to calculate exactly how likely the hiker is to be in any specific valley. It's like a scorecard:

Score = (Depth of Valley) + (How the Noise interacts with the Valley).
The lower the score, the more time the hiker spends there.
The "step-size" acts as the temperature dial. If you turn the dial down (smaller steps), the hiker becomes very picky and only visits the absolute lowest-scoring spots. If you turn it up, they become more adventurous and visit higher-scoring spots too.

The "Drunk Hiker" vs. The "Perfect Hiker"

In a perfect world (no noise), a hiker would just roll down the steepest path and get stuck in the first valley they hit. But because our hiker is "drunk" (noisy), they can accidentally bump their way out of a shallow valley and find a deeper one.

The paper shows that this "drunkenness" isn't a bug; it's a feature that creates a predictable distribution. The hiker doesn't just wander randomly; they wander statistically. Over a long time, you can predict exactly what percentage of the time the hiker will be in any specific valley based on the "temperature" (step-size) and the "energy" (the shape of the valley and the noise).

Summary

This paper tells us that the long-term behavior of the most popular machine learning algorithm (SGD) is not chaotic. It behaves like a physical system in thermal equilibrium.

The Algorithm: A hiker trying to find the bottom of a mountain.
The Noise: A shaking floor that makes the hiker stumble.
The Step-Size: The temperature of the room.
The Result: The hiker settles into a predictable pattern where they spend the most time in the "best" valleys, defined by a mix of how deep the valley is and how the shaking affects it.

The authors didn't just guess this; they used advanced math (Large Deviations Theory) to prove that this physical analogy is exactly how the algorithm behaves in the long run.

Technical Summary: The Long-Run Distribution of Stochastic Gradient Descent

1. Problem Statement

The paper addresses a fundamental open question in the theory of Stochastic Gradient Descent (SGD): Which regions of the state space are visited most frequently by SGD in the long run, and by what magnitude?

While existing literature provides convergence guarantees for SGD (e.g., bounds on the expected squared norm of the gradient), these results do not characterize the stationary distribution or the specific critical points where the iterates settle. In non-convex settings, which are prevalent in modern machine learning, the loss landscape is complex, containing numerous local minima, saddle points, and local maxima. Previous work has established that SGD avoids strict saddle points, but it has not quantified the relative probability of visiting different critical components or characterized the distribution of iterates far from the global minimum.

The authors aim to quantify the long-run distribution of SGD in general, non-convex problems, specifically seeking to understand the hierarchy of critical regions visited by the algorithm.

2. Methodology

The paper employs a rigorous mathematical framework based on Large Deviations Theory and the theory of randomly perturbed dynamical systems, specifically extending the Freidlin–Wentzell theory to discrete-time systems over unbounded domains.

Key Technical Steps:

Large Deviation Principle (LDP) for SGD:
- The authors establish an LDP for the SGD process by interpolating the discrete iterates into a continuous-time trajectory.
- They define an action functional $S_T[\gamma]$ based on the Lagrangian of the noise and the gradient of the objective function. This functional measures the "cost" or "likelihood" of a trajectory $\gamma$ deviating from the deterministic gradient flow.
- Unlike previous approaches relying on Stochastic Differential Equations (SDEs) which fail to capture long-run behavior due to slow convergence rates as the step-size $\eta \to 0$ , this approach directly analyzes the discrete dynamics.
Transition Costs and Quasi-Potential:
- The critical set of the objective function $f$ is decomposed into a finite number of connected components $K_i$ .
- The authors define a quasi-potential $B(K_i, K_j)$ representing the minimum action cost required for the SGD iterates to transition from component $K_i$ to $K_j$ .
- These costs form a weighted directed graph (the transition graph) where vertices are critical components and edge weights are the transition costs.
Energy Levels and Invariant Measures:
- The "energy" $E_i$ of a critical component $K_i$ is defined as the minimum total weight of a spanning tree in the transition graph rooted at $i$ .
- Using the theory of Freidlin–Wentzell adapted for discrete time, the authors derive the asymptotic behavior of the invariant measure (or mean occupation measure) of the SGD process.

3. Key Contributions and Results

The paper establishes a hierarchy of results (Theorems 1–4) describing the long-run distribution of SGD:

Concentration on Critical Regions (Theorem 3): In the long run, the iterates of SGD are exponentially more likely to be found in the vicinity of the critical set of $f$ than in non-critical regions. Specifically, the probability of being outside a $\delta$ -neighborhood of the critical set decays as $1 - e^{-c/\eta}$ .
Boltzmann–Gibbs Distribution (Theorem 1): The probability mass assigned to a specific critical component $K_i$ follows an approximate Boltzmann–Gibbs distribution:
$\mu_\infty(U_i) \propto \exp\left( -\frac{E_i}{\eta} \right)$
where $E_i$ is the energy level of the component and $\eta$ acts as the "temperature" of the system.
Dominance of Minimizers (Theorem 2): Non-minimizing critical components (local maxima or saddle points) are exponentially less likely to be visited than minimizing components. Specifically, for any non-minimizing component $K$ , there exists a minimizing component $K'$ such that the ratio of their visitation probabilities decays exponentially with $1/\eta$ .
Concentration on Ground States (Theorem 4): The iterates are exponentially concentrated around the "ground state" of the system—the set of critical components with the minimal energy $E_i$ $E_{i}$ .
- Crucial Distinction: The ground state of the SGD system (minimizing $E_i$ ) does not necessarily coincide with the global minimum of the objective function $f$ . The energy landscape is shaped by both the objective function and the statistics of the noise.

Specific Case: Gaussian Noise

For the case of Gaussian noise with variance $\sigma^2$ , the authors derive a closed-form expression for the energy levels:
$E_i \approx \frac{2 f(K_i)}{\sigma^2}$
In this specific scenario, the long-run distribution resembles the standard Gibbs measure $\exp(-f(x)/\eta_{eff})$ , where the effective temperature is proportional to the step-size and noise variance. However, for general noise models (e.g., those dependent on the gradient or position), the energy landscape can differ significantly from the objective function landscape.

4. Significance and Claims

The authors claim this work provides the first description of the invariant measure of SGD in general non-convex settings, moving beyond local convergence analysis or saddle-point avoidance.

Thermodynamic Analogy: The paper draws a direct analogy between SGD and equilibrium thermodynamics. The step-size $\eta$ plays the role of temperature, determining the ease of transitions between critical components. The "energy" of a component determines its likelihood of being visited.
Beyond Global Minima: The results challenge the intuition that SGD always converges to the global minimum. Instead, SGD converges to the "ground state" defined by the interplay of the objective function and noise statistics. A local minimum with a specific geometry (e.g., flatness) and favorable noise interaction may be visited more frequently than a deeper global minimum.
Generality: The framework applies to general non-convex objectives and various noise models (including minibatch SGD and injected noise), provided the noise satisfies sub-Gaussian tail conditions and the signal-to-noise ratio behaves appropriately at infinity.

The paper concludes that understanding the long-run distribution requires analyzing the "energy" of critical components, which is a functional of both the loss landscape and the noise structure, rather than simply the value of the loss function. This provides a theoretical basis for understanding why SGD might prefer certain solutions over others in deep learning, even if those solutions are not the global minima of the empirical risk.