Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks

Mingchen Li, Mahdi Soltanolkotabi, Samet Oymak

Introduction

Modern deep learning often involves training overparameterized neural networks—models with significantly more parameters than training samples. While these networks possess the mathematical capacity to perfectly fit any dataset, including one with completely random labels, they typically generalize well in practice. This paper provides a theoretical foundation for the long-observed phenomenon that early stopping acts as a powerful defense against label noise. The authors prove that gradient descent prioritizes learning the underlying "signal" (true data patterns) significantly faster than it memorizes "noise" (randomly corrupted labels).

Theoretical Framework: The Clusterable Dataset Model

To analyze this behavior, the authors introduce a Clusterable Dataset Model. In this model, data points are concentrated around $K$ cluster centers, reflecting real-world scenarios where different classes occupy distinct regions in feature space.

The core of the theoretical proof lies in the Jacobian analysis of the neural network. The Jacobian matrix (the partial derivatives of outputs with respect to weights) for clusterable data exhibits a bimodal spectrum:

  1. Dominant Singular Values: A small number of large values correspond to the "signal" or the coarse cluster structure.
  2. Tail Singular Values: Many tiny values correspond to the "noise" or random corruptions.

Gradient descent learns components associated with large singular values exponentially faster. Consequently, the network fits the "clean" labels in the initial stages of training while effectively ignoring noisy labels until much later.

The Mechanism of Robustness: Distance from Initialization

A key insight of the paper is that fitting noisy labels requires the network weights to travel a much larger distance from their starting point (initialization) than fitting correct labels. This "distance from initialization" serves as an implicit regularizer.

Training loss vs. distance from initialization for various corruption levels. Fitting noise requires moving significantly further from the starting weights.

As shown in the figure above, for a clean dataset, the loss drops to zero very quickly with minimal movement in weight space. As the fraction of corrupted labels increases, the model must travel further from initialization to achieve low training loss. Early stopping effectively constrains the model to a small radius around initialization, where it has captured the signal but not yet the noise.

Empirical Validation and Key Results

The authors validated their theory using MNIST, CIFAR-10, and synthetic datasets. Their main result, Theorem 2.2, proves that for a one-hidden-layer network with sufficient width, gradient descent with early stopping achieves near-perfect accuracy on ground truth labels, even with a constant fraction of random labels.

Comparison of a fully trained model (left) vs. an early-stopped model (right) under varying levels of label corruption. Early stopping preserves test accuracy even at 70-80% corruption.

The empirical results on MNIST (above) are striking. A model trained for many iterations eventually fits 100% of the training data (including noise), leading to a collapse in test accuracy. In contrast, the early-stopped model maintains high test accuracy and high accuracy with respect to true labels, even when 70% of the training labels are corrupted. Interestingly, the model often corrects labels: its prediction for a corrupted training point frequently matches the true ground truth rather than the noisy training label.

Conclusion

This work demystifies why overparameterized networks don't immediately succumb to overfitting in the presence of "dirty" data. By showing that the optimization trajectory naturally favors signal over noise, the authors provide a rigorous justification for early stopping. While the formal proofs focus on one-hidden-layer networks, the empirical evidence suggests these principles hold for deeper architectures like ResNets, opening doors for more robust training techniques in real-world applications with imperfect labeling.

Summary updated

Abstract

Modern neural networks are typically trained in an over-parameterized regime where the parameters of the model far exceed the size of the training data. Such neural networks in principle have the capacity to (over)fit any set of labels including pure noise. Despite this, somewhat paradoxically, neural network models trained via first-order methods continue to predict well on yet unseen test data. This paper takes a step towards demystifying this phenomena. Under a rich dataset model, we show that gradient descent is provably robust to noise/corruption on a constant fraction of the labels despite overparameterization. In particular, we prove that: (i) In the first few iterations where the updates are still in the vicinity of the initialization gradient descent only fits to the correct labels essentially ignoring the noisy labels. (ii) to start to overfit to the noisy labels network must stray rather far from from the initialization which can only occur after many more iterations. Together, these results show that gradient descent with early stopping is provably robust to label noise and shed light on the empirical robustness of deep networks as well as commonly adopted heuristics to prevent overfitting.
BibTeX
@inproceedings{li2020gradient,
  author = {Mingchen Li and Mahdi Soltanolkotabi and Samet Oymak},
  title = {{Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=Xj2QuoY89b},
}
Figure