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

Zhiyuan Li, Tianhao Wang, Sanjeev Arora

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 a regime, Blanc et al. (2020) proved that SGD with label noise locally decreases a regularizer-like term, the sharpness of loss, $\mathrm{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 $\tilde{O}(\kappa^2)$ upper bound (HaoChen et al., 2020).

Introduction

In modern deep learning, models are often "overparameterized," possessing far more parameters than data points. This creates a "manifold" of global minimizers—a continuous landscape of points where the training loss is exactly zero. While standard Gradient Descent (GD) typically converges to the nearest point on this manifold and remains stationary, Stochastic Gradient Descent (SGD) exhibits a different behavior. Researchers have long observed that SGD finds "better" points on this manifold that generalize more effectively to unseen data.

Characterizing this "implicit bias" has been a significant challenge. Previous attempts were often limited to local analysis valid only for short durations or restricted to specific, simple architectures. This work establishes a global mathematical framework to describe the long-term trajectory of SGD once it reaches the zero-loss regime.

Methodology: Separating the Dynamics

The authors treat SGD as a continuous-time process using Stochastic Differential Equations (SDEs). Their key innovation is applying Katzenberger’s Theorem to separate the parameter dynamics into two distinct components:

  1. Fast Dynamics (Normal Space): These are forces that quickly push the parameters back toward the zero-loss manifold $\Gamma$ whenever noise knocks them off.
  2. Slow Dynamics (Tangent Space): A subtle, deterministic "drift" that moves the parameters along the manifold over a much longer time scale ($\Theta(\eta^{-2})$ steps, where $\eta$ is the learning rate).
Decomposition of SGD dynamics into fast stochastic movement in the normal space and slow deterministic drift in the tangent space along the zero-loss manifold.

By accelerating the time scale, the authors derive a "limiting SDE" that completely characterizes the implicit bias. This framework allows for the analysis of various noise types, including isotropic noise and label noise (noise proportional to data gradients).

Theoretical Insights

The framework reveals several critical properties of SGD:

  • Noise as a Deterministic Force: Random noise in the "normal" direction (perpendicular to the manifold) translates into a deterministic drift in the "tangent" direction (along the manifold). The noise is not merely random; it possesses a "preference" that guides the optimization.
  • Sharpness Minimization: For label noise, the drift specifically minimizes the trace of the Hessian ($\mathrm{tr}[\nabla^2 L]$). This confirms that SGD actively seeks "flatter" minima, which are associated with better generalization.
  • Global vs. Local Analysis: Unlike prior work valid only for $\eta^{-1.6}$ steps, this framework holds for $\eta^{-2}$ steps, enabling a truly global analysis of the optimization trajectory.

Results and Applications

The paper applies this framework to an Overparameterized Linear Model (OLM) for a sparse recovery task in $\mathbb{R}^d$ where the ground truth is $\kappa$-sparse.

  • Escaping the "Kernel Regime": In high-dimensional linear models, GD often gets stuck in a "kernel regime" requiring $\Omega(d)$ samples to generalize. The authors prove that label noise SGD can "escape" this regime, finding the true sparse structure with only $O(\kappa \ln d)$ samples—a minimax optimal result.
  • Sample Complexity Gap: This represents a massive gap in high-dimensional settings where $d \gg \kappa$, demonstrating the power of SGD's implicit bias over standard GD.

Conclusion

While the framework provides a rigorous foundation, it relies on the limit where the learning rate $\eta \to 0$. Real-world training often utilizes larger learning rates where SDE approximations may be less precise. Additionally, the analysis assumes the set of minimizers forms a smooth manifold. Future research may extend this framework to other algorithms like Adam or SGD with momentum, and explore more complex, non-linear models beyond the OLM.

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 a regime, Blanc et al. (2020) proved that SGD with label noise locally decreases a regularizer-like term, the sharpness of loss, $\mathrm{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 $\tilde{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