Label Noise SGD Provably Prefers Flat Global Minimizers

• Blanc et al. [3] studied label-noise SGD’s local stability, but their analysis required sufficiently small η and predicted movement too small to affect model predictions.The predicted movement and regularizer decrease scale as η^0.4 and must be inversely polynomially small in dimension and condition number.Source: §1 · p. 2
• HaoChen et al. [12] proved sparse ground-truth recovery under well-specified sparse linear regression and isotropic features, demonstrating a global sparsity bias in quadratically-parametrized linear regression.Source: §1 · p. 2
• Label-noise SGD converges to a stationary point of L(θ) + λR(θ), where R penalizes sharp regions, even from a zero-error global minimum.Larger learning rates and smaller minibatches strengthen the regularization relative to the training loss.Source: §1 · pp. 2–3
• Larger learning rates and smaller minibatches strengthen regularization by shifting the balance between training loss and R(θ).Source: §1 · p. 3

2.1 Notation

• In regression, Algorithm 1 adds fresh noise to labels each step; the analysis assumes smooth losses and a local KL condition, which holds for analytic functions on compact domains.The noise variance controls the strength of the implicit regularization.Source: §2.1 · pp. 3–4

2.2 The Implicit Regularizer R(θ)

• The explicit regularizer penalizes larger Hessian eigenvalues more than smaller ones at large learning rates, beyond the linear scaling rule.Near a global minimizer, its infinitesimal-learning-rate form matches the regularizer in Blanc et al. [3].Source: §2.2 · p. 5

2.3 (ϵ, γ)-Stationary Points

• Because λ may shrink with ε, stationarity of L+λR can be trivial, while label-noise fluctuations obstruct exact stationarity of the rescaled loss; the paper therefore targets an (ε,γ)-stationary neighborhood.An (ε,γ)-stationary point lies within γ of a point whose gradient norm is at most ε.Source: §2.3 · p. 5

2.4 Main Result

• Under smoothness, learning-rate separation, and KL assumptions, near-global-minimum initialization lets noisy-label SGD reach an (ε,γ)-stationary point of the rescaled regularized loss with high probability in polynomially many steps.For δ=1/2, the stated bound is Õ(ε^-6 + γ^-3) steps.Source: §2.4 · p. 6

3.1 Local Coupling

• From an approximate global minimizer, noisy SGD stays close to regularized-loss gradient descent plus a small mean-zero process, with a bounded residual under the lemma’s conditions.The coupling bound holds with high probability over the specified time interval.Source: §3.1 · pp. 6–7
• The first-order deviation is an Ornstein–Uhlenbeck process whose long-run covariance is λΠG(2−ηG)^−1 on the span of G.Its norm is also bounded with high probability.Source: §3.1 · p. 8
• Unlike Blanc et al. [3], the proof couples to L+λR from nonzero-loss starts and permits convergence as the smallest nonzero Hessian eigenvalue tends to zero.It proves convergence to an (ϵ, γ)-stationary point for fixed η and λ, without requiring the learning rate to be small.Source: §3.1 · pp. 9–10
• Unlike Blanc et al. [3], the analysis does not require a small learning rate; λ can scale with ϵ by reducing η or increasing batch size, and R depends on η.R matches Blanc et al.’s regularizer only as η → 0.Source: §3.1 · p. 10

3.2 Global Convergence

• For global convergence, the proof carries the mean-zero process across successive local couplings and decreases the regularized loss by at least F after each coupling until an (ϵ, γ)-stationary point is reached.The theorem follows by repeated applications of the decrease lemma.Source: §3.2 · pp. 10–11
• Starting from the initial reference point, repeated couplings yield the theorem’s high-probability global convergence guarantee, with the number of algorithm iterations bounded in the proof.The guarantee is obtained by inductively applying the decrease lemma while the reference points are not stationary.Source: §3.2 · p. 11

Motivation

• Both starts were global training-loss minimizers with 100% training accuracy and poor test generalization, where minibatch SGD remains fixed because its gradient and noise vanish.The experiment tests whether label-noise SGD can escape these poor global minimizers.Source: §4 · p. 11

Initializations

• The full-batch initialization achieved 76% final test accuracy, while the adversarial initialization achieved 48% despite zero training loss.The adversarial start followed Liu et al. [21], memorizing random labels before training on true labels.Source: §4 · p. 11

Experimental setup

• With ResNet18 on CIFAR10, label flipping probability 0.2, cross-entropy loss, and batch size 256, the experiments tracked test accuracy and tr ∇2L.They used no data augmentation or weight decay and approximated R(θ) by its lower bound tr ∇2L(θ).Source: §4 · p. 12

Results

• Label-noise SGD escaped both zero-training-loss starts, reaching the minibatch-SGD baseline from the full-batch start and coming within 1% of it from the adversarial start.In both cases it converged to flatter minima that generalize much better.Source: §4 · p. 12, Figure 3 · p. 12
• Test accuracy was strongly correlated with tr ∇2L, and regularization strength was strongly correlated with η, supporting Theorem 1.The authors use tr ∇2L as a lower-bound approximation to the regularizer R(θ).Source: §4 · p. 12

5.1 Classification

• Under the stated assumptions, SGD with label smoothing for general binary classification losses reaches an (ϵ, γ)-stationary point of a regularized loss.The result covers arbitrary loss functions satisfying the quadratic-approximation assumption; logistic, exponential, and square losses are given as examples.Source: §5.1 · pp. 13–14

5.2 SGD with Momentum

• Momentum increases the regularization parameter by 1/(1−β); at β = 0.9, this is a 10× increase that the authors say likely explains improved performance.The extension also establishes a local coupling lemma for the momentum trajectory.Source: §5.2 · pp. 15–16, Figure 4 · p. 15

5.3 Arbitrary Noise Covariances

• For arbitrary noise covariance, the regularizer weights Hessian eigenvalues through a covariance-dependent matrix, and Proposition 5 gives a local coupling to its regularized trajectory.The proposition defines S using the Hessian and noise covariance at the reference minimizer, under its stated smoothness and covariance assumptions.Source: §5.3 · p. 16
• Because the covariance-dependent regularizer changes with the reference point, the analysis cannot generally establish convergence to a stationary point; an example shows minibatch SGD can cycle.The authors note that relating this changing regularizer to a fixed potential is not generally possible.Source: §5.3 · p. 16

6.1 Sharpness and the Effect of Large Learning Rates

• The regularization strength λ depends on η, label-noise strength σ², and batch size |B|; larger η and smaller batches support stronger implicit regularization [9] [26].This agrees with the linear scaling rule: maintaining constant regularization strength requires η to scale inversely with |B|.Source: §6.1 · p. 17
• As η approaches 2/λ1, R(θ) shifts from tracking tr ∇²L(θ) toward the Hessian spectral norm, increasingly penalizing eigenvalues near 2/η.The authors suggest this stronger control may make SGD more resilient to the edge-of-stability phenomenon observed by Cohen et al..Source: §6.1 · p. 17
• At global training-loss minima, SAM explicitly regularizes the Hessian spectral norm, closely connecting it to R(θ)'s large-learning-rate effect.This connection applies when η is near 2/λ1.Source: §6.1 · p. 17

6.2 Generalization Bounds

• At global minimizers, R(θ) upper-bounds the squared network-Jacobian norm and lower-bounds the all-layer margin mF up to higher-order terms, so label-noise SGD implicitly regularizes that margin [30].The bound is informal because higher-order terms were discarded in the all-layer-margin analysis.Source: §6.2 · p. 18

A Limitations

• Assumption 1 may fail for ReLU activations, though smooth activations such as softplus or SiLU can satisfy the needed smoothness conditions.The assumption enables second-order Taylor expansions of ∇L.Source: A Limitations · p. 23
• Assumption 2 permits learning rates arbitrarily close to 2/ℓ but does not explain optimization at the edge of stability when η > 2/ℓ.The condition is necessary because the results also cover quadratics, for which gradient descent diverges when η > 2/ℓ.Source: A Limitations · p. 23
• Under Assumption 3, convergence is ϵ^-6 when δ ≥ 1/2, but the rate can become arbitrarily bad as δ → 0.The rate is driven by a bound on E(θ*) that does not contribute to implicit regularization and can overwhelm the regularized-trajectory movement when L(θ*) = Ω(λ); avoiding Assumption 3 requires coupling to a changing potential R_S rather than a fixed R.Source: A Limitations · p. 23
• The stationarity definition does not establish convergence to an ϵ-stationary point of 1/λ times the smoothed loss.Tail-averaging might remove this limitation if iterates remain near a fixed ϵ-stationary point long enough, but first-order stationarity does not guarantee this, since iterates may escape a saddle point.Source: A Limitations · p. 23

Proposition 6

• With probability at least 1−2de^-ι, Proposition 6 bounds the auxiliary process ξ_t by X.The proposition is stated for every t ≥ 0.Source: B Missing Proofs · p. 25
• The proof establishes that the auxiliary process X(k) is a martingale by induction, providing a basis for the subsequent concentration bounds.The induction verifies the martingale property for all k.Source: B Missing Proofs · p. 25

Proposition 3

• For k ≤ t, the proof bounds ∥θ_k−θ*∥ by O(X) and expresses θ_k−θ* as ξ_k plus O(M).The argument invokes the high-probability bound on ξ_t and then uses a second-order Taylor expansion.Source: B Missing Proofs · p. 26
• The W and Z terms in Equation (72) are bounded by O(√ηkX^2) and O(√ηtX^2), respectively; together, these bounds hold with probability at least 1−10de^-ι.Source: B Missing Proofs · p. 30

Lemma 6

• Lemma 6 states that if L(θ) ≤ L, then every iterate Φ_k(θ) also satisfies L(Φ_k(θ)) ≤ L.Its proof reduces the claim to k = 1 by induction.Source: B Missing Proofs · p. 30

Lemma 3

• The proof of Lemma 3 selects an intermediate τ_m when θ_Tm is not stationary, compares regularized trajectories, and combines bounds on the regularized loss.The trajectory comparison is described in directions corresponding to eigenvalues of G(θ*).Source: B Missing Proofs · p. 31

C Reaching a global minimizer with NTK

• SGD with label noise converges to a neighborhood of a global minimizer; Theorem 1 gives the stated λ-scaled gradient bound ≲λδ/2 ≪1/√m when width exceeds a condition-number-dependent constant.The section says this convergence is the result required by Theorem 1.Source: C Reaching a global minimizer with NTK · pp. 36, 38
• Within a radius R = ˜O(√mλ0) of initialization, the Gram matrix has minimum eigenvalue at least λ0/2, where λ0 is the infinite-width NTK minimum eigenvalue.This is the cited lemma used in the section’s proof.Source: C Reaching a global minimizer with NTK · p. 36
• By induction, the residual r_k satisfies ∥r_k∥ ≤ D through the stated horizon 4 log[L(θ0)λ0/λ2]/(ηλ0), with base case r_0 = 0.Source: C Reaching a global minimizer with NTK · pp. 36–37

D Additional Experimental Details

• ResNet18 used GroupNorm instead of BatchNorm, with a fixed group size of 32, to maintain independence of sample gradients computed in a batch.Source: D Additional Experimental Details · p. 38
• Full-batch initialization used SGD with momentum on CIFAR10 for 2,000 epochs, with warmup, cosine decay, and label smoothing; final test accuracy was 76%.The learning rate rose linearly to 1 by epoch 600, then decayed to 0; momentum was 0.9 and label smoothing was 0.2.Source: D Additional Experimental Details · p. 38
• Adversarial initialization interpolated 500,000 images made by duplicating CIFAR10 images 10×, zeroing 10% of pixels, and assigning random labels.Source: D Additional Experimental Details · p. 38
• Starting from adversarial initialization, SGD on the true dataset ran for 1,000 epochs with learning rate 0.01, batch size 256, and label smoothing 0.2; final test accuracy was 48%.The adversarial dataset was interpolated without label smoothing using learning rate 0.01 for 300 epochs.Source: D Additional Experimental Details · p. 38
• Follow-up runs from both initializations used batch size 256 for 1,000 epochs, varied maximum learning rate, and were run with and without momentum.Learning rate was warmed up linearly over 300 epochs, then held constant through epoch 1,000.Source: D Additional Experimental Details · p. 38
• The regularizer estimate averaged each step’s gradient-noise strength over an epoch and renormalized it by batch size.Gradient-noise strength was computed from the difference between minibatch and full-loss gradients.Source: D Additional Experimental Details · p. 38

E.1 Proof of Theorem 2

• Theorem 2 follows from the same decompositions as Propositions 3 and 4, yielding convergence to an (ϵ, γ)-stationary point.The proof also reuses the analysis of Theorem 1.Source: §E.1 · p. 41

E.2 Verifying Assumption 4

• The appendix verifies Assumption 4 for logistic, exponential, and square losses and derives corresponding c and σ^2 values in Table 1.Source: §E.2 · p. 41

E.2.1 Logistic Loss

• For logistic loss, the noise strength is σ^2 = p(1 − p).Source: §E.2.1 · p. 42

E.2.2 Exponential Loss

• For exponential loss, the verification sets l(x) = e^-x and proceeds from the noisy-loss minimizer to calculate the noise strength.Source: §E.2.2 · p. 42

E.2.3 Square Loss

• For square loss, the noise strength is σ^2 = 4p(1 − p).Source: §E.2.3 · p. 42

F.1 Proof of Proposition 5

• On span(H), the update is a contraction with a unique fixed point S; the proof then couples iterates to an Ornstein–Uhlenbeck process by induction.The induction bounds the residual with probability at least 1 − 8dt e^-ι.Source: §F.1 · p. 43

F.2 SGD Cycling

• With all labels set to zero, the specified minibatch-SGD example cycles (x, y) counterclockwise on x^2 + y^2 = 1, while z_i periodically grow and shrink.The figure caption describes the initialization, but the cycling and periodic changes are stated in the text.Source: §F.2 · p. 46
• The cycle arises from minimizing a rapidly changing potential, so minibatch SGD’s implicit bias cannot be recovered by coupling to a fixed potential.Different Ornstein-Uhlenbeck processes govern the dynamics around the circle.Source: §F.2 · p. 46

G Weak Contraction Bounds and Additional Lemmas

• Under bounded-vector and step-size assumptions, the appendix states weak contraction bounds for a matrix G formed from the vectors g_i.The supplied passage does not include the explicit bounds.Source: G Weak Contraction Bounds and… · p. 47
• A Hoeffding-type inequality for norm-subGaussian vectors from Jin et al. [15] gives a stated probability guarantee of at least 1 − 2de^-ι.The supplied passage omits the inequality’s bound expression.Source: G Weak Contraction Bounds and… · p. 49
• For analytic L on compact D, Lemma 17 provides δ, μ, and ε_KL ensuring Assumption 3, using compactness to obtain uniform KL control near global minima.The proof uses a compact low-loss region around the global-minimum set.Source: G Weak Contraction Bounds and… · p. 49

H Extension to SGD with Momentum

• The momentum-extension proof uses induction on the iterate bound and treats partial sums as a martingale with bounded quadratic covariation.The passage says this bound, together with a corollary, completes the argument.Source: H Extension to SGD with Momentum · p. 50

H.1 Momentum Contraction Bounds

• In an eigenbasis of G, the momentum matrices decompose into 2 × 2 blocks, whose spectral radius is strictly below 1 when λ_i ≠ 0.The passage also states a non-strict bound under a condition that is truncated in the supplied text.Source: §H.1 · p. 54