What Happens after SGD Reaches Zero Loss? --A Mathematical Framework

Zhiyuan Li, Tianhao Wang, Sanjeev Arora

In the world of deep learning, we often train models until they reach "zero training loss." However, in overparameterized models—where there are far more parameters than data points—reaching zero loss doesn't mean the journey is over. There isn't just one perfect solution; there is an entire manifold (a continuous surface) of solutions that all yield zero loss.

The big mystery is: Which solution does Stochastic Gradient Descent (SGD) pick, and why does it generalize so well? A paper from researchers at Princeton and Yale provides a rigorous mathematical framework to answer exactly that.

TL;DR

The researchers developed a mathematical framework using Stochastic Differential Equations (SDEs) to show that after SGD reaches zero loss, it doesn't stop; it "drifts" along the manifold of perfect solutions. This drift acts as an implicit regularizer that minimizes the sharpness of the loss, explaining why SGD finds solutions that generalize better than standard Gradient Descent.

What Problem Does This Paper Address?

In modern machine learning, we use models so large they can easily memorize the training data. Because many different parameter settings can achieve zero training error, the "implicit bias" of the optimization algorithm—the hidden preference it has for certain types of solutions—is what determines the model's final performance.

Previous research suggested that SGD prefers "flat" minima (regions where the loss doesn't change much if you wiggle the parameters). However, most existing proofs were "local," only looking at what happens over a very short period. There was no global theory to describe the long-term trajectory of SGD once it hits that zero-loss manifold.

Methods

The authors adapted a sophisticated mathematical tool called Katzenberger’s Theorem (from 1991) to the context of deep learning. Their approach involves:

  1. Separating the Fast and the Slow: They split the movement of SGD into two parts. First, a "fast" movement toward the manifold of zero-loss minimizers. Second, a "slow" drift along that manifold.
Illustration of SGD dynamics near the zero-loss manifold, separated into fast normal space dynamics and slow tangent space drift.
  1. Time-Scaling: To see the slow drift clearly, they accelerated the time scale by a factor of $1/\eta^2$ (where $\eta$ is the learning rate).
  2. Limiting SDEs: They derived a specific Stochastic Differential Equation that describes the "limiting dynamics" of the parameters. This allowed them to calculate exactly how the noise in SGD pushes the model toward specific regions of the manifold.

Datasets

As a theoretical paper, the authors do not train on standard benchmarks like ImageNet or CIFAR-10. Instead, they use:

  • Overparameterized Linear Models (OLM): A controlled mathematical setting where the ground truth is "sparse" (only a few features actually matter).
  • Synthetic Data: Training data sampled from Gaussian or Boolean distributions to prove rigorous sample complexity bounds.

Key Insights and Ideas

  • Noise as a Sculptor: The "noise" in SGD (caused by looking at small batches of data) isn't just a nuisance. In the normal space (perpendicular to the manifold), this noise creates a fast-mixing process. Through a second-order effect (Ito's Lemma), this "normal" noise translates into a deterministic "tangent" drift that moves the model toward flatter regions.
  • Sharpness Minimization: For SGD with label noise, the authors proved that the algorithm globally moves to minimize the trace of the Hessian ($\text{tr}[\nabla^2 L]$), which is a formal measure of the "sharpness" of the loss.
  • Escaping the Kernel Regime: One of the most striking insights is that SGD can escape the "kernel regime" (where the model behaves like a simple linear feature extractor) and enter the "rich regime" (where it learns complex, sparse features). Standard Gradient Descent (GD) often gets stuck in the kernel regime if initialized there.

Key Results

  • Global Analysis: Unlike previous work valid for only $\eta^{-1.6}$ steps, this framework is valid for $\eta^{-2}$ steps, providing a truly global picture of the implicit bias.
  • Sample Complexity Gap: The authors showed that for a $\kappa$-sparse linear model in $d$ dimensions:
  • SGD with label noise only needs $O(\kappa \ln d)$ samples to find the right solution, regardless of how it is initialized.
  • GD initialized in the kernel regime requires $\Omega(d)$ samples.
  • This represents a massive efficiency gain for SGD in high-dimensional settings.

Limitations and Future Work

The framework currently relies on the infinitesimal learning rate limit (meaning the results are most accurate when the learning rate is very small). While this is a standard starting point for theory, real-world SGD often uses larger learning rates that might trigger different behaviors, like "catastrophic forgetting" or jumping between different basins of attraction.

The authors suggest that future work could extend this framework to other popular optimization algorithms like ADAM or include the effects of momentum, which are staples of modern deep learning practice.

Summary updated

Abstract

Understanding the implicit bias of Stochastic Gradient Descent (SGD) is one of the key challenges in deep learning, especially for overparametrized models, where the local minimizers of the loss function $L$ can form a manifold. Intuitively, with a sufficiently small learning rate $\eta$, SGD tracks Gradient Descent (GD) until it gets close to such manifold, where the gradient noise prevents further convergence. In such regime, Blanc et al. (2020) proved that SGD with label noise locally decreases a regularizer-like term, the sharpness of loss, $\text{tr}[\nabla^2 L]$. The current paper gives a general framework for such analysis by adapting ideas from Katzenberger (1991). It allows in principle a complete characterization for the regularization effect of SGD around such manifold---i.e., the "implicit bias"---using a stochastic differential equation (SDE) describing the limiting dynamics of the parameters, which is determined jointly by the loss function and the noise covariance. This yields some new results: (1) a *global* analysis of the implicit bias valid for $\eta^{-2}$ steps, in contrast to the local analysis of Blanc et al. (2020) that is only valid for $\eta^{-1.6}$ steps and (2) allowing *arbitrary* noise covariance. As an application, we show with arbitrary large initialization, label noise SGD can always escape the kernel regime and only requires $O(\kappa\ln d)$ samples for learning an $\kappa$-sparse overparametrized linear model in $\mathbb{R}^d$ (Woodworth et al., 2020), while GD initialized in the kernel regime requires $\Omega(d)$ samples. This upper bound is minimax optimal and improves the previous $\widetilde{O}(\kappa^2)$ upper bound (HaoChen et al., 2020).
BibTeX
@inproceedings{li2022what,
  author = {Zhiyuan Li and Tianhao Wang and Sanjeev Arora},
  title = {{What Happens after SGD Reaches Zero Loss? --A Mathematical Framework}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=siCt4xZn5Ve},
}
Figure