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

arXiv: https://arxiv.org/abs/1903.11680 · HTML: https://mlsanity.com/paper/1903.11680/

## Key facts

- Cited by 159 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2019.

## Built on by (most cited first, 30 of 159)

- [Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path](https://mlsanity.com/paper/2106.02073/) (2021)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [FINE Samples for Learning with Noisy Labels](https://mlsanity.com/paper/2102.11628/) (2021)
- [Sample Selection with Uncertainty of Losses for Learning with Noisy Labels](https://mlsanity.com/paper/2106.00445/) (2021)
- [Contrast to Divide: Self-Supervised Pre-Training for Learning with Noisy Labels](https://mlsanity.com/paper/2103.13646/) (2021)
- [Overview frequency principle/spectral bias in deep learning](https://mlsanity.com/paper/2201.07395/) (2022)
- [In Defense of the Unitary Scalarization for Deep Multi-Task Learning](https://mlsanity.com/paper/2201.04122/) (2022)
- [Detecting Corrupted Labels Without Training a Model to Predict](https://mlsanity.com/paper/2110.06283/) (2021)
- [Towards Label-free Scene Understanding by Vision Foundation Models](https://mlsanity.com/paper/2306.03899/) (2023)
- [ProMix: Combating Label Noise via Maximizing Clean Sample Utility](https://mlsanity.com/paper/2207.10276/) (2022)
- [Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization](https://mlsanity.com/paper/2401.15604/) (2024)
- [Learning with Noisy Labels via Sparse Regularization](https://mlsanity.com/paper/2108.00192/) (2021)
- [RIME: Robust Preference-based Reinforcement Learning with Noisy Preferences](https://mlsanity.com/paper/2402.17257/) (2024)
- [Towards Understanding Deep Learning from Noisy Labels with Small-Loss Criterion](https://mlsanity.com/paper/2106.09291/) (2021)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guarantees](https://mlsanity.com/paper/2206.02659/) (2022)
- [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023)
- [Memorisation versus Generalisation in Pre-trained Language Models](https://mlsanity.com/paper/2105.00828/) (2021)
- [Estimating Instance-dependent Bayes-label Transition Matrix using a Deep Neural Network](https://mlsanity.com/paper/2105.13001/) (2021)
- [Implicit Sparse Regularization: The Impact of Depth and Early Stopping](https://mlsanity.com/paper/2108.05574/) (2021)
- [Joint-Modal Label Denoising for Weakly-Supervised Audio-Visual Video Parsing](https://mlsanity.com/paper/2204.11573/) (2022)
- [Uncertainty-Aware Learning Against Label Noise on Imbalanced Datasets](https://mlsanity.com/paper/2207.05471/) (2022)
- [On the Activation Function Dependence of the Spectral Bias of Neural Networks](https://mlsanity.com/paper/2208.04924/) (2022)
- [BiCro: Noisy Correspondence Rectification for Multi-modality Data via Bi-directional Cross-modal Similarity Consistency](https://mlsanity.com/paper/2303.12419/) (2023)
- [Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel](https://mlsanity.com/paper/2107.12723/) (2021)
- [Mitigating Memorization of Noisy Labels via Regularization between Representations](https://mlsanity.com/paper/2110.09022/) (2021)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime](https://mlsanity.com/paper/2112.08297/) (2021)
- [Sparse Double Descent: Where Network Pruning Aggravates Overfitting](https://mlsanity.com/paper/2206.08684/) (2022)

## Abstract (arXiv)

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.