Label Noise SGD Provably Prefers Flat Global Minimizers

Alex Damian; Tengyu Ma; Jason D. Lee

Source-linked AI summary

Label Noise SGD Provably Prefers Flat Global Minimizers

Alex Damian, Tengyu Ma, Jason D. Lee

arXiv:2106.06530v2Jun 11, 2021cs.LGcs.ITmath.OCstat.ML

TL;DR

The paper asks how label noise affects the implicit regularization and solution selection of SGD in overparameterized models, beyond prior local or model-specific analyses. It models label-noise SGD as optimizing an explicitly regularized loss and proves convergence toward stationary points that favor flatter regions, while identifying stronger curvature penalization at large learning rates.

Problem
Prior analyses of label-noise SGD were local or restricted to specific models, leaving its global implicit regularization effect insufficiently characterized.
Method
The paper analyzes label-noise SGD through a regularized loss L(θ) + λR(θ), extending the framework to global convergence and general noise covariances.
Results
Label-noise SGD converges to a stationary point of the regularized loss, whose curvature-based regularizer penalizes larger Hessian eigenvalues more strongly at large learning rates.
Takeaways & Limitations
Learning rate, label-noise strength, and batch size control the balance between training loss and implicit flatness regularization.
Takeaways & Limitations
For arbitrary noise covariances, the induced regularizer can change with the reference point, preventing a general convergence proof to a fixed potential and allowing perpetual cycling in an example.

Abstract

from arXiv · show

In overparametrized models, the noise in stochastic gradient descent (SGD) implicitly regularizes the optimization trajectory and determines which local minimum SGD converges to. Motivated by empirical studies that demonstrate that training with noisy labels improves generalization, we study the implicit regularization effect of SGD with label noise. We show that SGD with label noise converges to a stationary point of a regularized loss $L(θ) +λR(θ)$, where $L(θ)$ is the training loss, $λ$ is an effective regularization parameter depending on the step size, strength of the label noise, and the batch size, and $R(θ)$ is an explicit regularizer that penalizes sharp minimizers. Our analysis uncovers an additional regularization effect of large learning rates beyond the linear scaling rule that penalizes large eigenvalues of the Hessian more than small ones. We also prove extensions to classification with general loss functions, SGD with momentum, and SGD with general noise covariance, significantly strengthening the prior work of Blanc et al. to global convergence and large learning rates and of HaoChen et al. to general models.

1 Introduction

This paper studies how label noise in SGD globally regularizes optimization in overparameterized models, building on prior local and model-specific analyses. It shows that label noise, learning rate, and batch size jointly shape convergence toward flatter solutions.

Earlier analysis only established parameter movement of η^0.4, too small to affect model predictions under its required dimension and conditioning assumptions.
Prior work showed that label-noise SGD can recover sparse ground truth in quadratically parametrized linear regression under well-specified sparse isotropic settings.
The paper proves that label-noise SGD converges to a stationary point of L(θ) + λR(θ), where R(θ) penalizes sharp regions of the loss landscape.
The analysis extends earlier local results by establishing a global regularization effect even when SGD starts at a zero-error global minimum.
Larger learning rates and smaller batch sizes produce stronger implicit regularization through the balance between the loss and regularizer.

2 Problem Setup and Main Result

The paper formulates label-noise SGD as optimization of an explicitly regularized loss and states conditions for convergence near approximate global minimizers. Its regularizer depends on curvature, while learning rate, noise strength, and batch size determine the effective regularization.

2.1 Notation: Label-noise SGD adds fresh additive noise to labels before computing each stochastic gradient, with σ controlling noise strength.
2.1 Notation: The effective regularization parameter depends on learning rate, label-noise strength, and batch size, with larger learning rates and smaller batches strengthening regularization.
2.2 The Implicit Regularizer R(θ): The implicit regularizer R(θ) is defined from the Hessian, and its eigenvalue weights penalize larger curvature more strongly at large learning rates.Near infinitesimal learning rates, it matches the trace-Hessian regularizer associated with prior work.
2.3 (ϵ, γ)-Stationary Points: The paper uses an (ϵ, γ)-stationary notion because ordinary ϵ-stationarity can become uninformative when λ scales with ϵ and label noise causes fluctuations.The definition requires proximity to some point whose gradient is at most ϵ.
2.4 Main Result: The main result proves convergence to an (ϵ, γ)-stationary point of the rescaled regularized loss under smoothness, learning-rate separation, and a local KL assumption.The theorem assumes initialization near an approximate global minimizer and gives convergence within a polynomial number of steps.
2.4 Main Result: The theorem guarantees convergence within Õ(ϵ^-6 + γ^-3) steps when δ = 1, while extending the earlier local analysis to a global result.

3 Proof Sketch

The proof couples label-noise SGD locally to gradient descent on a regularized loss, then chains these couplings to establish global convergence toward stationarity.

3.1 Local Coupling: The analysis couples label-noise SGD to gradient descent on L(θ) + λR(θ), with a controlled stochastic deviation around the regularized trajectory.The deviation is decomposed into a mean-zero Ornstein–Uhlenbeck process and a bounded residual error.
3.1 Local Coupling: The label-noise update is decomposed into minibatch noise and label-noise terms, with the latter dominating the former in the proof.The label-noise component is further split into a reference-point term and a term caused by evaluating the gradient away from that point.
3.1 Local Coupling: The Ornstein–Uhlenbeck process has mean zero and an asymptotic covariance shaped by the model-gradient covariance and the regularization strength.Its covariance converges to λΠ_G(2 − ηG)^−1 on the span of G.
3.1 Local Coupling: The implicit regularizer weights curvature through the learning rate, so larger eigenvalues receive stronger regularization at nonzero η.The proof uses the eigenvalue-dependent factor whose derivative is 1/(2 − ηx).
3.2 Global Convergence: Unlike prior local analyses, the proof handles nonzero training loss, changing Hessian conditioning, and learning rates that need not be small.The resulting convergence is to a stationary point of the full regularized loss rather than only the regularizer.
3.2 Global Convergence: Repeating local couplings across reference points decreases the regularized loss until label-noise SGD reaches an (ϵ, γ)-stationary point.The argument bounds the number of coupling iterations and establishes the claimed high-probability convergence.

4 Experiments

Experiments initialize SGD at poor zero-training-loss solutions and show that label noise escapes them, reaches flatter solutions, and substantially improves generalization.

Experiments: The experiments use ResNet18 on CIFAR10 with randomized label flipping at probability 0.2, cross-entropy loss, and batch size 256.No data augmentation or weight decay is used.
Experiments: SGD with label noise escapes both zero-training-loss initializations, reaches the full-batch SGD baseline from one, and comes within 1% of it from the adversarial initialization.The two initializations have final test accuracies of 76% and 48%, respectively, before label-noise SGD training.
Experiments: Test accuracy is strongly correlated with tr ∇2L, the experimental lower-bound proxy used for the implicit regularizer.Figure 3 tracks training accuracy, tr ∇2L, and their correlation over time across three random seeds.

5 Extensions

The paper extends label-noise SGD analysis to general classification losses, momentum, and arbitrary noise covariances. These extensions characterize convergence, momentum-enhanced regularization, and covariance-dependent local dynamics.

5.1 Classification: The classification extension applies to logistic, exponential, and square losses through a smoothed loss with a unique global minimizer and a local quadratic approximation.The paper explicitly verifies the quadratic-approximation assumptions for these three losses and tabulates their associated constants.
5.1 Classification: Label-noise SGD with general classification losses converges to an approximate stationary point of a regularized loss under stated assumptions on the model, loss, step size, and initialization.The theorem uses λ = ησ^2/B and gives a polynomial iteration bound under initialization near an approximate global minimizer.
5.2 SGD with Momentum: With momentum, the regularized trajectory is locally coupled to the momentum dynamics, while momentum increases the effective regularization parameter by 1/(1−β).For β = 0.9, the paper identifies this as a 10× increase in regularization.
5.3 Arbitrary Noise Covariances: For arbitrary noise covariance, the induced regularizer is R_S(θ)=⟨S,∇^2L(θ)⟩, with S weighting Hessian eigenvalues through a covariance-dependent fixed-point equation.The local coupling result assumes the covariance at the minimizer is bounded by a constant multiple of the Hessian.
5.3 Arbitrary Noise Covariances: The arbitrary-covariance extension does not generally yield convergence to a stationary point because the covariance-dependent regularizer changes with θ and need not define a fixed potential.The paper gives an example where minibatch SGD perpetually cycles and leaves continuously changing potentials for future study.

6 Discussion

The discussion explains how learning rate, batch size, and Hessian spectrum shape the implicit regularizer. In particular, large learning rates shift the regularization from trace-like sharpness toward control of the largest Hessian eigenvalues.

6 Discussion: The effective regularization strength is λ=ησ^2/|B|, so larger learning rates and smaller batches produce stronger implicit regularization.This agrees with the linear scaling rule for maintaining constant regularization strength.
6.1 Sharpness and the Effect of Large Learning Rates: After normalization, R(θ) approaches the Hessian spectral norm as η approaches 2/λ1, interpolating from tr ∇^2L(θ) at small η.The paper connects this large-learning-rate behavior to spectral-norm regularization in SAM.
6.2 Generalization: At global minimizers, R(θ) lower-bounds the all-layer margin up to higher-order terms, linking label-noise SGD's implicit regularization to data-dependent generalization quantities.The associated Jacobian-norm relationship is described as an informal bound because higher-order terms are discarded.

A Limitations

The analysis depends on smoothness, learning-rate, and KL assumptions, each imposing scope or convergence limitations. The authors also identify limitations in the stationarity definition and in controlling approximation errors.

Assumptions: Smoothness assumptions may exclude ReLU networks, although smooth activations such as softplus or SiLU can resolve this limitation.
Assumptions: The analysis does not explain optimization at the edge of stability when η > 2/ℓ, because the learning-rate treatment targets the quadratic cutoff.
Assumptions: The convergence rate can become arbitrarily bad as δ →0 because the bound on E(θ∗) introduces uncontrolled error unrelated to implicit regularization.
Assumptions: Removing the KL assumption requires coupling to a changing potential R_S rather than a fixed regularizer R.
Stationarity: The stationarity definition is a fundamental limitation because first-order stationarity does not ensure iterates remain near a fixed point long enough for tail averaging.

B Missing Proofs

The proofs establish concentration, trajectory control, and descent properties through martingale arguments, Taylor expansions, and induction. These components support convergence to an approximate stationary point of the regularized loss.

Proof components: Martingale concentration bounds control stochastic deviations, including ξ_t and contributions from W and Z, with probabilities of the form 1−2de^−ι.
Proof components: Inductive arguments show that auxiliary processes are martingales and that deterministic trajectories remain controlled relative to stochastic iterates.
Proof components: Second-order Taylor expansions around global minimizers connect SGD updates to the regularized trajectory and bound approximation remainders.
Convergence argument: The proof selects times τ_m where insufficient stationarity yields regularized-loss decrease, then combines this decrease with trajectory bounds.
Convergence argument: Together, these bounds imply convergence to an (ε, γ)-stationary point when the iterate is not already stationary.

C Reaching a global minimizer with NTK

In the kernel regime, the analysis extends gradient-descent convergence to label-noise SGD and shows that iterates approach a neighborhood of a global minimizer. The resulting regularized stationarity can be achieved near such minimizers.

Global minimization: The NTK argument extends kernel-regime convergence from gradient descent to label-noise SGD, establishing proximity to a global minimizer.
Global minimization: Jacobian and residual bounds control the training gradient while the iterate remains near the reference minimizer.
Proof setup: The proof accommodates nonzero initial noise processes by continuing the auxiliary process without changing the argument.
Regularized stationarity: For sufficiently large width, Theorem 1 yields a point whose rescaled regularized gradient is much smaller than 1/√m.

D Additional Experimental Details

The experiments use ResNet18 on CIFAR10 with controlled initialization, learning-rate, momentum, and label-smoothing settings. The adversarial initialization creates a heavily duplicated, randomly relabeled dataset before true-data training.

Setup: Experiments use ResNet18 with GroupNorm, fixed group size 32, and CIFAR10 training data under cross-entropy loss.
Setup: The full-batch initialization uses momentum SGD with η=1, β=0.9, 2000 epochs, warmup, cosine decay, and label smoothing 0.2.
Initialization: The adversarial initialization duplicates CIFAR10 images tenfold, randomly zeros 10% of pixels, assigns random labels, and trains with η=0.01 and batch size 256.
Initialization: Starting from the adversarial initialization, true-data training with label smoothing 0.2 produced 48% final test accuracy.
Evaluation: Remaining runs vary the maximum learning rate with fixed batch size 256, with and without momentum, while estimating regularization from per-step gradient-noise strength.

E.1 Proof of Theorem 2

The proof establishes convergence results by simplifying the dynamics, coupling SGD to auxiliary processes, and controlling deviations with concentration bounds. It also verifies the framework for several losses and computes corresponding label-noise strengths.

Rescaling the loss by 1/α and the learning rate by α leaves the update and λL + R unchanged, so the proof may assume α = 1.
The proof replaces labels with normalized signs and decomposes the true loss into its signal and label-noise components before applying martingale and concentration arguments.
A local coupling argument compares the SGD trajectory with an Ornstein–Uhlenbeck process whose fixed point is characterized in the Hessian eigenbasis.
The proof reuses the analysis of Theorem 1 to show convergence to an (ϵ, γ)-stationary point, thereby establishing Theorem 2.
For logistic and exponential losses, the derived label-noise strengths are σ^2 = p(1 −p) and σ^2 = 4p(1 −p), respectively.
The analysis bounds Gaussian and truncated-noise contributions using tail, Bernstein, and related concentration inequalities, yielding high-probability control of the approximation error.

F.2 SGD Cycling

The cycling construction shows that minibatch SGD can follow a persistent cycle rather than behave like optimization under a fixed implicit potential. The example explains this behavior through rapidly changing noise-induced curvature preferences.

SGD Cycling: The construction defines twelve functions f_i over θ = (x, y, z1, z2, z3, z4) and trains them with squared loss and zero labels.
SGD Cycling: Minibatch SGD cycles counterclockwise on x^2 + y^2 = 1 while the associated z_i coordinates periodically grow and shrink.
SGD Cycling: At different points on the circle, oscillations concentrate noise in different z_i directions, changing which Hessian entry minibatch SGD favors reducing.
SGD Cycling: The constraint enforced by f13 keeps θ on x^2 + y^2 = 1 throughout the process, while the changing potential drives the observed cycling.
SGD Cycling: The example demonstrates that minibatch SGD’s implicit bias cannot generally be recovered by coupling it to a fixed potential.