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

By Mingchen Li, M. Soltanolkotabi, Samet Oymak. 2019

396 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Optimization & Training, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

In Safety, Robustness & Interpretability

Citations in the corpus

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “[37] leverages low-rank Jacobian structure to establish robustness to label noise.”
The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies (2019, background): “( Other papers also mention this phenomenon, e.g., [16]) Right: Given the 1D training data points ( x 1 , ..., x 32 ∈ S 1 ) marked in black, a two layer network learns the function represented by the orange curve, interpolating the missing data to form an approximate sinusoid of low frequency.”
Robust early-learning: Hindering the memorization of noisy labels (2021, methodology): “It would be interesting to explore the potential characteristics of the updated parameters such as the distance to initial parameters (Li et al., 2020b; Hu et al., 2020) and the mutual information with the vector of all training labels given inputs (Harutyunyan et al., 2020).”
Identifying Mislabeled Data using the Area Under the Margin Ranking (2020, background): “Li et al. (2019) and Hu et al. (2019) develop theoretical guarantees in the noisy-label setting for early stopping and other regularizations.”
Robust Learning by Self-Transition for Handling Noisy Labels (2020, background): “Furthermore, compared with prior studies on the memorization of DNNs [2, 19, 22], this is the first work to solve the problem of finding the best transition point.”
Ditto: Fair and Robust Federated Learning Through Personalization (2020, methodology): “…learning (Zhao et al., 2018; Yu et al., 2020), meta-learning (Jiang et al., 2019; Chen et al., 2018; Khodak et al., 2019; Fallah et al., 2020; Li et al., 2020a; Singhal et al., 2021), and other forms of MTL, such as hard model parameter sharing (Agarwal et al., 2020; Liang et al., 2020) or…”
Convolutional Neural Networks: A Survey (2023, neutral): “Early stopping: This technique stops the training process early based on a validation set performance metric, which helps to prevent the model from overﬁtting to the training data [122–125].”
Early-Learning Regularization Prevents Memorization of Noisy Labels (2020, background): “[23] focus on a least squares regression task, whereas we focus on the noisy label problem in classiﬁcation.”
Metadata Archaeology: Unearthing Data Subsets by Leveraging Training Dynamics (2022, methodology): “…could be: correcting mislabeled examples present in a dataset (Arazo et al., 2019), using them only in a self-supervised training objective (Li et al., 2020a), or even completely ignoring them during training (Wang et al., 2018; Talukdar et al., 2021), upweighting or balancing training on…”