Label Noise SGD Provably Prefers Flat Global Minimizers

Alex Damian, Tengyu Ma, Jason D. Lee

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, SGD with momentum, and SGD with general noise covariance, significantly strengthening the prior work of Blanc et al. to global convergence and large learning rates and of HaoChen et al. to general models.

Introduction

In modern deep learning, we often use "overparametrized" models—networks with far more parameters than data points. These models can achieve zero training error at many different points in the parameter space (global minimizers). However, not all minimizers are created equal: "flat" minimizers (where the loss stays low even if you wiggle the parameters) tend to generalize much better to new data than "sharp" ones. While researchers have long suspected that the inherent noise in Stochastic Gradient Descent (SGD) helps find these flat regions, proving it has been difficult. This paper provides a global convergence proof showing that SGD with label noise explicitly prefers flat global minimizers over sharp ones.

Theoretical Framework: Local Coupling

The authors analyze Algorithm 1: SGD with Label Noise, where a random perturbation $\epsilon \sim \{-\sigma, \sigma\}$ is added to the labels $y_i$ at every step. The core of their theoretical contribution is the "Local Coupling" technique. They prove that the trajectory of noisy SGD stays very close to the trajectory of a standard Gradient Descent (GD) algorithm running on a regularized loss function: $$\tilde{L}(\theta) = L(\theta) + \lambda R(\theta)$$ Where $L(\theta)$ is the standard training loss, $\lambda$ is an effective regularization parameter (proportional to learning rate and noise strength), and $R(\theta)$ is the implicit regularizer, defined as: $R(\theta) = -\frac{1}{2\eta} \text{tr log} \left( I - \frac{\eta}{2} \nabla^2 L(\theta) \right)$.

Local Coupling: The noisy SGD trajectory is coupled with a regularized GD trajectory to prove global convergence.

By Taylor expanding this log-term, the authors show that $R(\theta)$ essentially penalizes the eigenvalues of the Hessian (the matrix of second derivatives), which is the standard mathematical definition of "sharpness."

Key Insights

The Log-Hessian Penalty and Large Learning Rates

The implicit regularizer $R(\theta)$ isn't just a simple penalty on the trace of the Hessian. Because it involves a matrix logarithm, it penalizes the largest eigenvalues (the sharpest directions) much more aggressively than the smaller ones. The paper uncovers a hidden benefit of large learning rates: as the learning rate $\eta$ increases, the regularizer $R(\theta)$ starts to behave more like the spectral norm (the single largest eigenvalue) of the Hessian rather than the trace. This suggests that large learning rates are specifically tuned to suppress the "sharpest" directions in the loss landscape.

Regularization Strength vs. Learning Rate: The implicit regularizer grows faster than the linear trace approximation as learning rate increases.

Escaping "Bad" Minima

Unlike standard SGD, where the gradient vanishes at a global minimum, label noise SGD continues to have "gradient noise" even when the training error is zero. This persistent noise is what allows the model to "kick" itself out of sharp, poorly-generalizing valleys and move toward flatter ones. Furthermore, using momentum ($\beta$) effectively scales the regularization strength by a factor of $1/(1-\beta)$. For a standard momentum of 0.9, this is a 10x increase in the flattening effect.

Empirical Validation

The authors validated their theory using CIFAR-10 and ResNet18. To test if label noise truly "prefers" flat minima, they started the model at "bad" global minimizers—points that had 100% training accuracy but poor test accuracy. Under label noise SGD, these models migrated to flatter regions, eventually reaching the same high test accuracy (~90%+) as models trained normally. The experiments showed a near-perfect correlation between the decrease in the "Trace of the Hessian" (sharpness) and the increase in test accuracy.

Limitations and Future Work

The proof requires the loss function to be several times differentiable, which is technically violated by ReLU activations, though smooth approximations like Softplus behave similarly. Additionally, the proof shows convergence to a stationary point of the regularized loss, not necessarily the global minimum. Finally, while the paper extends the theory to general noise, for some noise types, a "fixed potential" might not exist, leading to complex behaviors like "cycling." Exploring these non-conservative noise fields remains a path 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, SGD with momentum, and SGD with general noise covariance, 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