Label Noise SGD Provably Prefers Flat Global Minimizers

Alex Damian, Tengyu Ma, Jason D. Lee

Overview

This paper provides a rigorous theoretical foundation for why adding noise to labels during training helps deep learning models generalize better. The authors prove that Stochastic Gradient Descent (SGD) with label noise implicitly minimizes a regularized loss function that penalizes "sharp" regions of the loss landscape. By doing so, it effectively forces the model to converge to "flat" minima, which are widely known to correlate with superior test performance.

The Problem: Generalization in Overparameterized Models

In modern machine learning, we frequently use overparameterized models—networks with far more parameters than data points. These models can fit the training data perfectly in many different ways, but some of these solutions generalize to new data while others do not.

A long-standing hypothesis is that "flat" minima (regions where the loss doesn't change much if you slightly perturb the weights) generalize better than "sharp" minima. While empirical evidence suggests that SGD—and specifically SGD with added label noise—finds these flat regions, a formal mathematical proof for general models has been missing. Previous work was often limited to local stability analysis or very specific, simple models like linear regression. This paper aims to provide a global convergence analysis, demonstrating how label noise acts as an implicit regularizer across the entire optimization trajectory.

Methods and Key Innovations

The authors analyze an algorithm where, at each training step, the target label is perturbed by a random noise term.

The Implicit Regularizer

They derive an explicit formula for the regularizer $R(\theta)$ that label noise SGD effectively minimizes: $$R(\theta) = -\frac{1}{2\eta} \text{tr log} \left( I - \frac{\eta}{2} \nabla^2 L(\theta) \right)$$ This formula shows that the noise penalizes the eigenvalues of the Hessian (the matrix of second derivatives), which serves as the mathematical definition of "sharpness."

Large Learning Rate Analysis

Unlike prior work that assumed infinitesimal step sizes, this analysis accounts for large learning rates ($\eta$). It uncovers a non-linear regularization effect where larger rates penalize sharp directions even more aggressively than a simple linear scaling would suggest.

Regularization strength vs. learning rate

Local Coupling Technique

To prove global convergence, the authors use a "coupling" argument. They show that the noisy SGD trajectory stays very close to a theoretical "regularized" gradient descent path. By chaining these local approximations together, they prove the algorithm eventually hits a stationary point of the regularized loss.

Key Insights

  • Noise as a "Crawl Space": In standard SGD, the noise vanishes at a global minimum because the gradients go to zero. In label noise SGD, the noise persists even at a global minimum. This persistent noise allows the optimizer to "crawl" out of sharp valleys and keep searching until it finds a region flat enough to withstand the noise.
  • The Log-Hessian Penalty: The derived regularizer $R(\theta)$ is approximately the trace of the Hessian when the learning rate is small. However, as the learning rate increases, the penalty becomes more severe for large eigenvalues. This suggests that high learning rates are not just about speed, but are a fundamental part of the regularization mechanism.
  • Connection to SAM: The authors show a formal link between label noise SGD and Sharpness-Aware Minimization (SAM). Label noise SGD can be viewed as a stochastic version of SAM, explicitly regularizing the spectral norm of the Hessian.
  • Global vs. Local: While earlier papers showed that flat minima are stable under noise, this paper shows that the optimizer is actually driven toward them from almost anywhere in the landscape.

Experimental Validation and Results

The theoretical results are general, but the authors validate them using CIFAR-10 and a ResNet-18 architecture. They specifically use "Adversarial Initializations" (where the model is pre-trained to memorize random labels) to demonstrate that label noise SGD can escape "bad" sharp minima where standard SGD would get stuck.

Experimental results showing test accuracy and Hessian trace
  • Provable Convergence: The authors prove that label noise SGD converges to an $(\epsilon, \gamma)$-stationary point of the regularized loss $L + \lambda R$ in polynomial time.
  • Escaping Memorization: As shown in the adversarial initialization experiments, a model starting at a sharp minimum (e.g., ~48% test accuracy, zero training loss) can be "rescued" by label noise SGD, eventually reaching the standard baseline of ~80% test accuracy.
  • Hessian Correlation: They demonstrated a clear inverse correlation between the trace of the Hessian and test accuracy. As the label noise pushed the model toward lower Hessian traces (flatter regions), the test accuracy consistently improved.

Limitations and Future Work

  • Loss Function Specifics: Much of the detailed proof focuses on the square loss (regression). While they provide extensions for classification (cross-entropy), the cleanest theoretical results are tied to the properties of the square loss.
  • The KL Assumption: The proof relies on the Kurdyka-Łojasiewicz (KL) inequality, a technical assumption that the loss landscape isn't "too flat" in a way that would prevent any progress. While common in optimization theory, it can be hard to verify for real-world neural networks.
  • Cycling Behavior: The authors note that for arbitrary noise (not just label noise), the system might not converge to a fixed potential but could instead enter a permanent cycle. Exploring which types of noise lead to stable regularization versus chaotic cycling is a suggested area for future research.

Summary updated

Abstract

In overparametrized models, the noise in stochastic gradient descent (SGD) implicitly regularizes the optimization trajectory and determines which local minimum SGD converges to. Motivated by empirical studies that demonstrate that training with noisy labels improves generalization, we study the implicit regularization effect of SGD with label noise. We show that SGD with label noise converges to a stationary point of a regularized loss $L(\theta) +\lambda R(\theta)$, where $L(\theta)$ is the training loss, $\lambda$ is an effective regularization parameter depending on the step size, strength of the label noise, and the batch size, and $R(\theta)$ is an explicit regularizer that penalizes sharp minimizers. Our analysis uncovers an additional regularization effect of large learning rates beyond the linear scaling rule that penalizes large eigenvalues of the Hessian more than small ones. We also prove extensions to classification with general loss functions, significantly strengthening the prior work of Blanc et al. to global convergence and large learning rates and of HaoChen et al. to general models.
BibTeX
@inproceedings{damian2021label,
  author = {Alex Damian and Tengyu Ma and Jason D. Lee},
  title = {{Label Noise SGD Provably Prefers Flat Global Minimizers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=u6tT3UFxHe},
}
Figure