PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Mingchen Li, Mahdi Soltanolkotabi, Samet Oymak

arXiv:1903.11680v3cs.LGstat.ML

TL;DR

The paper asks why overparameterized networks can generalize despite their ability to fit noisy labels. It analyzes gradient descent under a rich clusterable data model and shows that early stopping remains near initialization, fitting correct labels while ignoring noise, whereas noisy-label overfitting requires moving far from initialization. These results provide robustness guarantees for a constant fraction of label corruption and connect weight distance with robustness versus overfitting.

  • Problem

    Overparameterized networks can fit arbitrary labels, including pure noise, yet models trained with first-order methods can predict well on unseen data.

  • Method

    The paper analyzes gradient descent from random initialization under a clusterable dataset model with label corruption, comparing early iterations near initialization with later movement toward noisy-label fitting.

  • Results

    Gradient descent is provably robust to noise on a constant fraction of labels, fitting correct labels while near initialization; fitting noisy labels requires straying far from initialization.

  • Takeaways & Limitations

    The distance between final and initial weights helps distinguish noise-robust, generalizing solutions from solutions that overfit, supporting early stopping as a robustness heuristic.

  • Takeaways & Limitations

    The theoretical guarantees use a clusterable dataset model that allows a fraction of corruptions in each cluster.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies why overparameterized networks can remain robust to label corruption when trained with first-order methods and early stopping. It combines MNIST observations with theoretical guarantees under a clusterable, noisy-label dataset model.

  • Empirical motivation: 50% label corruption still leaves training accuracy against ground-truth labels around 100% with early stopping in the MNIST experiment.The same overparameterized network can eventually fit corrupted labels, while early stopping preserves robustness.
  • Theoretical contribution: Gradient descent is provably robust to corruption on a constant fraction of labels in overparameterized learning scenarios.The guarantee is established under an expressive dataset model and focuses theoretically on one-hidden-layer networks.
  • Theoretical contribution: After a few iterations, gradient descent remains near initialization and fits correct labels while essentially ignoring noisy labels.This is the paper’s early-stopping regime for learning from corrupted data.
  • Theoretical contribution: Overfitting noisy labels requires gradient descent to move far from the initial model.The required distance depends on input deviation from cluster centers and corruption amount.
  • Dataset model: The clusterable dataset model uses unit-norm points from balanced clusters, with multiple clusters potentially sharing a scalar class label.It permits non-linearly separable examples and defines noisy datasets with a fraction of corruptions in each cluster.

2 Main results

The paper proves that early-stopped gradient descent can learn correct labels while remaining robust to constant label corruption, provided the data and network satisfy its stated assumptions. Its analysis links this behavior to initialization distance, Jacobian structure, and the slower dynamics of fitting noise.

  • Main theorem: Gradient descent with early stopping is provably robust to label noise in overparameterized networks.The main theorem studies one-hidden-layer networks trained on a clusterable corrupted dataset.
  • Main theorem: Under the theorem’s assumptions, the learned model predicts the true label function throughout ε0-neighborhoods of the cluster centers.The guarantee holds for all inputs in those neighborhoods and applies to every training sample through the stated interpolation relation.
  • Main theorem: The required early-stopping time is at most order K and typically scales as max(1,K/d), up to condition numbers.The theorem’s iteration bound uses a prescribed step size and reaches a good model after few iterations.
  • Main theorem: The result applies with modest overparameterization: the hidden-unit requirement is K2∥C∥4, independent of sample size n.For incoherent cluster centers with K ≥ d, the total parameter count scales as dK2∥C∥4 ≲ K4.
  • Distance from initialization: Distance from initialization separates useful fitting from overfitting: fitting nearby inputs with differing labels requires movement of at least δ/ε0.The paper also argues that more corruption requires a larger model norm, while early stopping keeps parameters near initialization.
  • Key technical ideas: The proof decomposes optimization through Jacobian singular subspaces, with clean residuals in the large-singular-value subspace and label noise in the small one.Gradient descent therefore learns clean information in few iterations but takes much longer to fit noise.

3 Numerical experiments

Experiments across MNIST, CIFAR-10, and a synthetic corrupted-cluster model examine how early stopping, label corruption, loss distributions, and Jacobian structure relate to robustness and overfitting.

  • Experimental scope: Experiments span MNIST, CIFAR-10, and synthetic data generated from the corrupted dataset model.The study examines loss, accuracy, corruption level, individual sample losses, and Jacobian spectra.
  • MNIST: Increasing label corruption increases the distance from initialization associated with training accuracy and loss on MNIST.The observed distance grows gracefully as corruption increases, matching the theoretical prediction.
  • CIFAR-10: 30% corruption on CIFAR-10 yields approximately separable clean and corrupted loss distributions, as predicted for small corruption.The experiments use ResNet-20 and all 50,000 samples with either 30% or 50% random corruption.
  • CIFAR-10: The CIFAR-10 binary Jacobian has around 270,000 parameters, with only 10 to 20 singular values exceeding 0.1× the top singular value.The singular-value histogram is similar before and after training, supporting a bimodal Jacobian structure.
  • Synthetic corrupted-cluster model: With 30% corrupted training data, the synthetic experiment uses K = 2 classes, n = 400 samples, ε0 = 0.5, and k = 1000 hidden units.An average of 15% of labels actually flip, marked by the dashed green line.
  • Synthetic corrupted-cluster model: Early stopping achieves good classification in the first few iterations, whereas prolonged training eventually overfits the corruption and loses generalization robustness.At later iterations, clean and corrupted loss distributions overlap.

4 Conclusions

The paper combines theoretical robustness guarantees with lower bounds and experiments, identifying the distance between final and initial weights as central to robustness versus overfitting.

  • Conclusions: The paper provides gradient-descent robustness guarantees with early stopping and complements them with lower bounds.The conclusions connect these guarantees to robustness against label corruption in overparameterized neural networks.
  • Conclusions: The distance between final and initial network weights is identified as a key feature distinguishing robustness from overfitting.This conclusion is described as consistent with weight decay and early-stopping heuristics.

5 Improvements for perfectly cluster-able data

For perfectly clustered data, the required overparameterization decreases, and the network can remain robust without early stopping because it does not overfit corrupted labels.

  • 5 Improvements for perfectly cluster-able data: The perfectly clustered theorem analyzes gradient descent from a randomly initialized W0 using updates Wτ+1 = Wτ − η∇L(Wτ) on least-squares loss.The theorem assumes a step-size condition and a sufficiently large number of hidden nodes.
  • 5 Improvements for perfectly cluster-able data: In the perfectly clustered limit ε0 → 0, the overparameterization requirement decreases from kd ≳ K^4 to kd ≳ K^2.The result is obtained through a perturbation argument from a refined perfectly clustered-data theorem.
  • 5 Improvements for perfectly cluster-able data: The perfectly clustered setting does not require early stopping: after sufficiently many iterations, the network remains robust and never overfits the corrupted data.This differs from the non-perfectly clustered setting, where early stopping helps avoid later overfitting.

6 To (over)fit to corrupted labels requires straying far from initialization

The analysis shows a distance gap: fitting true labels can occur near initialization, while fitting corrupted labels requires substantially greater movement from the initial weights.

  • 6 To (over)fit to corrupted labels requires straying far from initialization: A network fitting both clean and corrupted labels must satisfy a lower bound on its norm, which yields an initialization-distance guarantee under a norm condition.The triangle-inequality argument applies when ∥W0∥F ≲ O(√sδ/ε0).
  • 6 To (over)fit to corrupted labels requires straying far from initialization: The true-label solution grows from initialization by at most τε0 after τ iterations, creating a gap between generalization and overfitting distances.The paper concludes that early stopping restricts movement and can preserve robustness without fitting corrupted labels.

7 Technical Approach and General Theory

The paper models gradient descent on nonlinear least-squares problems whose Jacobians have a bimodal spectrum, then proves robustness to label corruption when updates remain near initialization.

  • Gradient-descent framework: Gradient descent updates a nonlinear model by θτ+1 = θτ −η∇L(θτ), starting from initialization θ0 with constant learning rate η.The gradient is expressed through the Jacobian and residuals: ∇L(θ) = J(θ)^T(f(θ) − y).
  • Bimodal Jacobian: The bimodal-Jacobian assumption separates a signal subspace S+ with large spectrum from a noise subspace S− with small spectrum.S+ is called the signal subspace and S− the noise subspace; when ϵ << α, the Jacobian is approximately low-rank.
  • Dataset structure: For perfectly clustered data, the Jacobian is at most rank K, and S+ consists of vectors that are constant within each cluster.Perturbed clusters yield a small but nonzero spectrum over S−.
  • Robustness theorem: Under smoothness, low-rank, and initialization-residual conditions, early-stopped gradient descent stays near initialization while fitting correct labels and largely ignoring noisy labels.The theorem requires a learning-rate bound and a stopping time satisfying its stated conditions.
  • Overfitting boundary: If gradient descent fits corrupted labels, its parameters must move far from initialization, with the required distance increasing as corruption increases.The distance-to-initialization result applies under the bimodal-Jacobian assumption and explains why early stopping avoids the overfitting regime.

8.1 Proofs for General Theory

The general proof tracks gradient-descent residuals and parameter distance through Jacobian contractions, then shows that sparse label corruption has limited effect in the signal subspace.

  • Residual dynamics: The proof linearizes residual changes along each gradient-descent step using an average Jacobian between consecutive parameter values.This connects nonlinear updates to Jacobian-based contraction and perturbation bounds.
  • Sparse-noise specialization: For sparse corruption and a diffused signal subspace, the projection of label noise onto S+ is small, yielding sample-wise robustness guarantees.The theorem’s sparse-corruption specialization uses diffusedness to bound the signal-space projection.
  • Inductive argument: Gradient descent preserves the decomposition into signal and noise components while contracting the residual over the signal subspace.The induction uses the Jacobian range-space condition and the learning-rate upper bound.
  • Error guarantee: The resulting residual bound controls the infinity norm of prediction errors after enough iterations to reduce the signal component below precision ν.The precision condition requires ν ≥ ∥ΠS+(e)∥ℓ∞.
  • Stability control: Smoothness and spectral bounds keep successive iterates inside the domain where the bimodal-Jacobian assumptions hold.The proof controls both the parameter step and the residual through positive-semidefinite Jacobian bounds.
  • Distance to interpolation: Zero training loss cannot be achieved within a sufficiently small neighborhood of initialization when the noise-space residual is nonzero.The required distance grows with the corruption component E−, supporting early stopping as a way to avoid fitting noise.

8.2 Proofs for Neural Networks

The neural-network proofs establish the required Jacobian structure and initialization bounds for one-hidden-layer networks on clusterable datasets, then apply the general robustness theorem.

  • Jacobian properties: The neural-network Jacobian is analyzed through smoothness, spectral-norm, and minimum-singular-value properties at initialization.These properties are inherited from corresponding results for the cluster-center Jacobian.
  • Support subspace: For clusterable data, the Jacobian range lies in the support subspace S+, whose coordinates repeat according to cluster membership.The support subspace has dimension K and is characterized by equal entries within each cluster.
  • Transfer to datasets: Duplicating cluster-center rows transfers singular-value and smoothness bounds from the cluster-center Jacobian to the clean dataset Jacobian.The proof uses repeated rows corresponding to cluster memberships.
  • Initialization: The initialization residual is bounded with high probability for the one-hidden-layer model under bounded activation derivatives and normalized inputs.The argument combines bounded labels with subgaussian control of the random initialization output.
  • Label-noise projection: The projection of sparse label errors onto the cluster-induced support space is bounded using per-cluster corruption counts and bounded label differences.This projection estimate supplies the noise term needed by the general theorem.
  • Classification consequence: When ρ ≤ δ/8, the network misses the correct label by at most δ/2, so all labels, including noisy ones, are correctly classified.This conclusion follows from the stated clusterable noisy-dataset conditions and initialization probability.

8.3 Perturbation analysis for perfectly clustered data (Proof of Theorem 2.2)

The perturbation analysis compares training on noisy inputs with training on their cluster-center versions, bounding the resulting Jacobian, parameter, and residual deviations.

  • Perturbation setup: The analysis compares noisy-data iterates Wτ with noiseless cluster-center iterates Ẇτ initialized at the same weights.Both sequences use gradient descent, but their losses are evaluated on the original and clean inputs respectively.
  • Jacobian perturbation: Input perturbations and parameter deviations produce bounded differences between the noisy and clean Jacobians.The bound combines Jacobian Lipschitzness in weights with an additive term proportional to input noise ε0.
  • Trajectory control: The proof recursively controls parameter distance and residual distance between the two gradient-descent trajectories.The recursion uses the noiseless residual bound and the Jacobian perturbation estimates.
  • Neural-network guarantee: Theorem 8.13 applies these perturbation bounds to clusterable noisy data under constraints on input noise, hidden width, activation derivatives, and learning rate.With the stated probability, the result holds after τ = O( K ηnλ(C))log( Γ ... iterations.
  • Prediction guarantees: For ρ ≤ δ/8, the resulting classifier has a bounded number of prediction errors relative to the true labels and is correct throughout the prescribed neighborhoods of cluster centers.The theorem separately states an error bound and a zero-error neighborhood guarantee.
  • Early-stopping range: The total distance to initialization remains bounded throughout the allowed iteration range, linking perturbation control to early stopping.The stopping time is chosen to satisfy both clean-data optimization and perturbation-analysis requirements.

9 Proof of Lemma 6.1

The proof constructs input matrices and label vectors, applies spectral-norm concentration, and derives a lower bound on the Frobenius norm of any matrix that fits the labels perfectly.

  • The proof forms matrices X and ˜X by concatenating the input samples, with X − ˜X having independent Gaussian entries.The entries are distributed as N(0,2ε^2/d).
  • Spectral-norm concentration is applied to X − ˜X with probability at least 1 − e^−d/2.
  • The label vectors y and ˜y are defined from their respective entries, and W is assumed to fit these labels perfectly.
  • The proof concludes that any such perfectly fitting matrix W satisfies the desired lower bound on ∥W∥F.

10 Uniform guarantee for minimum distance

The proof establishes a uniform guarantee over clustered inputs by combining Gaussian-process concentration, a mean-value argument, derivative bounds, and a union bound over clusters.

  • Uniform guarantee for minimum distance: The mean value theorem relates differences at (W,x), (W,˜x), (W0,x), and (W0,˜x) through an intermediate point.
  • Uniform guarantee for minimum distance: Derivative bounds, unit-norm inputs, norm comparisons, and initialization control provide the intermediate inequalities used in the guarantee.The proof invokes |φ′(z)|≤Γ, |φ′′(z)|≤Γ, Frobenius domination of spectral norm, and bounds on ∥W0∥ and ∥W−W0∥F.
  • Uniform guarantee for minimum distance: For centered coefficient vectors v, the network difference at initialization is subGaussian with Orlicz norm at most cΓ∥v∥ℓ2∥x−˜x∥ℓ2.This follows from independent Gaussian vectors, mean zero for 1^T v=0, and the subGaussian bound in (10.3).
  • Uniform guarantee for minimum distance: For inputs near a cluster center, the proof controls function differences using Gaussian-process chaining bounds.The chaining argument yields a uniform result over all input pairs of interest after applying a union bound over the K clusters.
  • Uniform guarantee for minimum distance: With probability 1−exp(−d), the resulting bound holds uniformly over all relevant x,˜x pairs, implying the advertised minimum-distance guarantee.
Loading 1903.11680v3…