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 fit any set of labels, including random noise. However, in practice, they often generalize well even when trained on noisy data. This paper provides a theoretical bridge between a common deep learning heuristic—early stopping—and the surprising resilience of neural networks to "dirty" data, proving that gradient descent naturally prioritizes learning clean signals over label noise.
Introduction: The Overparameterization Paradox
In modern machine learning, models with millions of parameters are frequently used to fit datasets with only thousands of examples. Theoretically, these overparameterized models are flexible enough to fit any set of labels, including completely random ones. This raises a fundamental question: if a model can fit noise, why doesn't it always overfit when the training data is corrupted?
Practitioners have long observed that "early stopping"—halting training before the loss reaches zero—seems to allow models to ignore noise and capture underlying patterns. This work demystifies this phenomenon by providing a mathematical proof for why gradient descent (GD) behaves this way in overparameterized regimes.
Theoretical Framework
The authors analyze the optimization path of a one-hidden-layer neural network using the Neural Tangent Kernel (NTK) framework. The learning process is decomposed into three key components:
- Jacobian Analysis: The Jacobian matrix of the network at initialization is shown to be typically low-rank.
- Spectral Decomposition: The learning process is viewed as a series of updates along different "directions." Clean, consistent signals align with the top singular values (strong directions) of the Jacobian, while sparse label noise aligns with the "tail" (weak directions).
- Distance from Initialization: The authors track the movement of weights from their starting values. They prove that fitting the "clean" signal requires significantly less movement than fitting "noise."
Key Insights: The Distance Threshold
A central insight of the paper is that fitting a single corrupted label requires network weights to travel a distance proportional to $1/\epsilon_0$ (where $\epsilon_0$ is the input noise). In contrast, because the clean signal is diffused across many points, the network can learn it while staying very close to its initialization.
As shown in Figure 5, optimization happens in two distinct phases. Initially, the network acts as a "low-pass filter," picking up dominant patterns. It only begins to travel far enough to memorize noise much later in the process. This suggests that gradient descent has an "implicit bias" toward simpler solutions that generalize well, even without explicit regularization.
Empirical Validation and Results
The theory was validated using MNIST, CIFAR-10, and a synthetic "clusterable" dataset. The results confirm that for a sufficiently wide network, GD with early stopping predicts true labels even when a constant fraction of training points are corrupted.
As illustrated in Figure 1, while a model trained for many iterations eventually memorizes the noise (leading to high train accuracy but poor test accuracy), early stopping maintains high test accuracy and high accuracy with respect to the true labels. In experiments on MNIST with 50% label corruption, the model achieved nearly 100% accuracy on ground truth labels during early training stages, effectively "ignoring" the corruption.
Limitations and Future Directions
While providing a rigorous foundation for early stopping, the study has limitations:
- Architecture Complexity: Formal proofs focus on one-hidden-layer networks. While empirical evidence suggests the logic holds for CNNs and ResNets, mathematical extension to deep architectures remains future work.
- The "Lazy Training" Regime: The analysis relies on the "lazy training" regime (NTK), where weights stay near initialization. Real-world feature learning may involve larger movements not fully captured here.
- Corruption Levels: Future research could further refine the exact noise thresholds a network can tolerate before the clean signal is overwhelmed.
Summary updated