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

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.

References in corpus (23)

• Learning to Reweight Examples for Robust Deep Learning
• A Convergence Theory for Deep Learning via Over-Parameterization
• Training Deep Neural Networks on Noisy Labels with Bootstrapping
• Deep Learning is Robust to Massive Label Noise
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Learning From Noisy Singly-labeled Data
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Robust Regression via Hard Thresholding
• Does data interpolation contradict statistical optimality?
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Efficient Algorithms for Outlier-Robust Regression
• High Dimensional Robust Sparse Regression
• Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization

Cited by in corpus (52)

• Early-Learning Regularization Prevents Memorization of Noisy Labels
• Ditto: Fair and Robust Federated Learning Through Personalization
• The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
• Review: Deep Learning in Electron Microscopy
• Dual T: Reducing Estimation Error for Transition Matrix in Label-noise Learning
• Contrast to Divide: Self-Supervised Pre-Training for Learning with Noisy Labels
• Self-Adaptive Training: beyond Empirical Risk Minimization
• Denoising and Regularization via Exploiting the Structural Bias of Convolutional Generators
• Identifying Mislabeled Data using the Area Under the Margin Ranking
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• FINE Samples for Learning with Noisy Labels
• Classifying Exoplanet Candidates with Convolutional Neural Networks: Application to the Next Generation Transit Survey
• Distillation $\approx$ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation
• Generalized Jensen-Shannon Divergence Loss for Learning with Noisy Labels
• Heteroskedastic and Imbalanced Deep Learning with Adaptive Regularization
• Learning Not to Learn in the Presence of Noisy Labels
• How does Early Stopping Help Generalization against Label Noise?
• LOCA: LOcal Conformal Autoencoder for standardized data coordinates
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• On Convergence and Generalization of Dropout Training
• How benign is benign overfitting?
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• When Does Preconditioning Help or Hurt Generalization?
• Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent
• Coresets for Robust Training of Neural Networks against Noisy Labels
• Conditional Density Estimation, Latent Variable Discovery and Optimal Transport
• On the Role of Dataset Quality and Heterogeneity in Model Confidence
• Convolutional Normalization: Improving Deep Convolutional Network Robustness and Training
• Self-Adaptive Training: Bridging Supervised and Self-Supervised Learning
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Adaptive Precision Training (AdaPT): A dynamic fixed point quantized training approach for DNNs
• Deep Transfer Learning for Automated Diagnosis of Skin Lesions from Photographs
• Data Quality Matters For Adversarial Training: An Empirical Study
• Learning with Noisy Labels by Efficient Transition Matrix Estimation to Combat Label Miscorrection
• KNN-enhanced Deep Learning Against Noisy Labels
• Learning to Combat Noisy Labels via Classification Margins
• Image recognition from raw labels collected without annotators
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• Low Dimensional Landscape Hypothesis is True: DNNs can be Trained in Tiny Subspaces
• Multiplicative Reweighting for Robust Neural Network Optimization
• Incompatibility Clustering as a Defense Against Backdoor Poisoning Attacks
• A Tale Of Two Long Tails
• Robustness and Reliability When Training With Noisy Labels
• Constrained Instance and Class Reweighting for Robust Learning under Label Noise
• Phases of learning dynamics in artificial neural networks: with or without mislabeled data
• Heavy-tailed Streaming Statistical Estimation
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• A termination criterion for stochastic gradient descent for binary classification
• Generalization by Recognizing Confusion