PaperlayerView exact revision on arXiv

Source-linked AI summary

Shape Matters: Understanding the Implicit Bias of the Noise Covariance

Jeff Z. HaoChen, Colin Wei, Jason D. Lee, Tengyu Ma

arXiv:2006.08680v2cs.LGstat.ML

TL;DR

Prior theory largely studies spherical Gaussian noise, despite evidence that parameter-dependent noise can be more effective at regularizing overparameterized models. This paper analyzes noise shape in a quadratically-parameterized model and shows that label-noise SGD can recover sparse ground truth from arbitrary initialization, unlike spherical Gaussian noise.

  • Problem

    Prior theory largely focuses on spherical Gaussian noise, while empirical work reports stronger regularization from parameter-dependent label or mini-batch noise.

    Source: §1 · pp. 1–2

  • Method

    The paper theoretically analyzes label noise and spherical Gaussian noise in a nonlinear quadratically-parameterized model.

    Source: §1 · p. 2

  • Results

    With a proper learning-rate schedule, label-noise SGD recovers the sparse ground-truth classifier from arbitrarily large initialization, whereas spherical Gaussian noise generalizes poorly.

    Source: §1 · p. 3, §2.2 · p. 6

  • Takeaways & Limitations

    Parameter-dependent covariance adds a bias toward lower-noise-covariance, low-norm solutions that spherical Gaussian noise does not provide.

    Source: §1 · p. 3

    When ησ² tends to zero, Gaussian-noise effects vanish and its behavior may resemble gradient descent.

    Source: §2.2 · p. 6

Abstract

from arXiv · show

The noise in stochastic gradient descent (SGD) provides a crucial implicit regularization effect for training overparameterized models. Prior theoretical work largely focuses on spherical Gaussian noise, whereas empirical studies demonstrate the phenomenon that parameter-dependent noise -- induced by mini-batches or label perturbation -- is far more effective than Gaussian noise. This paper theoretically characterizes this phenomenon on a quadratically-parameterized model introduced by Vaskevicius et el. and Woodworth et el. We show that in an over-parameterized setting, SGD with label noise recovers the sparse ground-truth with an arbitrary initialization, whereas SGD with Gaussian noise or gradient descent overfits to dense solutions with large norms. Our analysis reveals that parameter-dependent noise introduces a bias towards local minima with smaller noise variance, whereas spherical Gaussian noise does not. Code for our project is publicly available.

1 Introduction

The paper asks why noise shape, beyond noise scale, affects SGD’s implicit regularization, given evidence that label or mini-batch noise can outperform spherical Gaussian noise. It analyzes this difference in a quadratically-parameterized model and argues that parameter-dependent covariance biases solutions toward lower-norm sparse minima.

1 Introduction

  • Prior empirical work found label or mini-batch noise more effective than spherical Gaussian noise, motivating analysis of noise shape alongside its scale.The paper notes this may matter for distributed training when parallelism reduces mini-batch noise.Source: §1 · p. 2
  • The authors study noise-shape effects theoretically in a quadratically-parameterized model that exhibits empirical phenomena similar to deep networks.They choose label noise partly because, unlike mini-batch noise at an exactly overfit solution, it does not vanish, making analysis more tractable.Source: §1 · pp. 2–3
  • With a proper learning-rate schedule, label-noise SGD recovers the sparse ground truth from arbitrarily large initialization, while spherical Gaussian noise generalizes poorly.In the same regime, noise-free gradient descent quickly overfits in the NTK regime, and Gaussian noise is insufficient to recover the ground truth.Source: §1 · p. 3
  • Label or mini-batch noise is parameter-dependent and biases solutions toward smaller noise covariance, whereas spherical Gaussian noise lacks this additional bias.In this model, label-noise covariance scales with the parameter, producing a stronger bias toward low-norm solutions; flat-minimum bias alone is insufficient because many overfitting minima have reasonable curvature.Source: §1 · p. 3

1.1 Additional Related Works

2 Setup and Main Results

The section sets up an overparameterized sparse-recovery model and compares label-noise SGD with noise-free or spherical-Gaussian alternatives. It reports recovery under a suitable label-noise schedule even from large initialization, while the Gaussian Gibbs distribution can fail to exist.

2.1 Setup and Backgrounds

  • The model uses elementwise-squared parameters in an overparameterized setting with Gaussian data and an r-sparse, nonnegative ground truth.The paper focuses on n = poly(r) ≪ d and allows an initialization scale τ that is arbitrarily large but polynomial in d.Source: §2.1 · pp. 4–5
  • Label-noise SGD perturbs sampled training labels before applying gradient updates, while Langevin dynamics adds spherical Gaussian noise to gradient descent.The paper studies label noise partly because it is less sensitive to initialization and optimization history than minibatch noise.Source: §2.1 · p. 5

2.2 Main Results

  • The negative Gaussian-noise result is analyzed through the Gibbs distribution, separating convergence from generalization.The result concerns Gaussian noise with ησ² held fixed as η becomes sufficiently small; if ησ² tends to zero, the noise effect vanishes and behavior likely resembles gradient descent.Source: §2.1 · pp. 5–6, §2.2 · p. 6
  • With arbitrarily large initialization, a suitable label-noise level and learning-rate schedule let SGD recover the ground truth with probability at least 0.9.The theorem assumes n ≥ eΘ(r²) samples and δ ≥ eΘ(τ²d²).Source: §2.2 · p. 6
  • Earlier local analysis of label-noise bias does not establish global convergence to a well-generalizing solution from large or arbitrary initialization.The authors note that once an iterate leaves a local minimum, local tools no longer apply and its subsequent behavior is unclear.Source: §2.2 · p. 6
  • When v⋆ = 0 and n ≤ d/3, the Gibbs distribution is not well-defined with probability at least 0.9 because its partition function diverges.Consequently, Langevin diffusion does not converge to a proper stationary distribution.Source: §2.2 · p. 7
  • The paper attributes the Gibbs failure to the vast volume of bad global minima outweighing the flatness of the minimum at v⋆ = 0.The bad minima have only slightly sharper curvatures, yet their volume makes the partition function blow up.Source: §2.2 · p. 7

3 Analysis Overview of SGD with Label Noise (Theorem 2.1)

The analysis uses a one-dimensional random walk to illustrate how parameter-dependent noise can favor small parameters, then sketches label-noise SGD as a three-stage route from a large initialization to the sparse ground truth.

3.1 Warm-up: Updates with Only Parameter-dependent Noise

  • In the warm-up, the parameter-dependent random walk converges to zero with high probability, unlike Brownian motion, which diverges despite both processes preserving the mean and increasing variance.The walk's noise variance shrinks with the parameter, trapping it near zero; Brownian motion has no limiting stationary distribution.Source: §3.1 · p. 8

3.3 Stage 1: Getting Closer to v⋆with Annealed Learning Rate

  • After annealing, label noise increases coordinates on the ground-truth support while decreasing off-support coordinates, moving toward v⋆ without initialization depending on the target error.The stage assumes an ℓ∞ initialization bound of order 1/d; the analysis balances gradient signal on the support against noise bias off the support.Source: §3.3 · p. 10

3.2 Stage 0: Label Noise with Large Learning Rate Reduces the Parameter Norm

  • A large initial learning rate makes label noise shrink ||v||∞ to 1/d, entering a small-norm region where overfitting is less likely.The analysis attributes the contraction to the noise's second-order effect on a concave potential, which can outweigh the gradient contribution under the stated learning-rate condition.Source: §3.2 · pp. 9–10, §3.3 · p. 10

3.4 Stage 2: Convergence to the ground-truth v⋆

  • Further learning-rate annealing lets label-noise SGD converge to the ground truth within any target error, with high probability under the stated initialization and step-size conditions.The stage-2 result permits any noise level δ ≥ 0 and runs for T = Θ(1/η) iterations.Source: §3.4 · p. 11

4 Analysis Overview of Langevin Dynamics (Theorem 2.2)

To analyze the Langevin-dynamics partition function, the proof changes to squared-parameter coordinates and uses directions orthogonal to the data. A positive cone in those directions yields a divergent integral when d > 2n.

4 Analysis Overview of Langevin Dynamics (Theorem 2.2)

  • Changing variables to u = v⊙2 restricts the integral to positive coordinates, while loss invariance along X⊥ lets the proof integrate over a translated affine space.The loss is invariant in u + X⊥.Source: §4 · p. 11
  • The proof parameterizes X⊥ with a basis matrix whose first column is a positive vector, creating a cone where u = u′ + Aũ remains coordinate-wise positive.The positive vector in X⊥ exists with high probability, as stated in the passage.Source: §4 · p. 11
  • Integrating over that cone diverges when d > 2n, establishing that the relevant integral is infinite.The passage compares the integral to one of a polynomial of degree −d/2 across d − n dimensions.Source: §4 · p. 11

5 Conclusion

The paper analyzes noise-induced implicit bias in a quadratically parameterized model. It finds that parameter-dependent noise can aid sparse ground-truth recovery, while spherical Gaussian noise does not induce the same bias.

5 Conclusion

  • The paper theoretically studies noise-induced implicit bias in a quadratically parameterized model.The conclusion frames the analysis around how noise affects the parameter's implicit bias.Source: §5 · p. 11
  • Parameter-dependent noise can help recover the sparse ground truth from limited data, whereas spherical Gaussian noise does not induce that bias.The conclusion presents this as a contrast between the two noise types.Source: §5 · p. 11
  • The result offers an explanation for reported generalization degradation when mini-batch or label noise is replaced by Gaussian noise in deep models.The conclusion describes this as an explanation of an empirical observation.Source: §5 · p. 11

A.1 Experimental Details for the Quadratically-Parameterized Model

The experiments use a 100-dimensional quadratically parameterized model with 40 Gaussian data points and a sparse ground truth. They compare full-batch training, simulated mini-batch noise, label noise, and spherical Gaussian noise.

A.1 Experimental Details for the Quadratically-Parameterized Model

  • The experiment uses a 100-dimensional model, n = 40 Gaussian data points, and a ground-truth vector with five entries set to 1 and the rest to 0.The ground-truth vector is initialized at v[0] = 1.Source: §A.1 · p. 18
  • Mini-batch noise is simulated by adding δ times the difference between two sampled-example gradients to the full gradient, while label noise perturbs a sampled label by ±δ.Both noise levels are set to δ = 1.0 in the described experiment.Source: §A.1 · p. 18
  • Training runs for 3 × 10^5 iterations except Gaussian-noise runs, which use 1.2 × 10^6; test error is the squared ℓ2 distance between v⊙2 and v⋆⊙2.The Gaussian-noise runs are plotted after scaling the x-axis by a factor of four.Source: §A.1 · p. 18

A.2 Experimental Details for Deep Neural Networks on CIFAR100

The CIFAR100 experiments compare label noise and spherical Gaussian parameter noise with small- and large-batch training. Label noise and small-batch training outperform large-batch and Gaussian-noise training by around 13% accuracy.

A.2 Experimental Details for Deep Neural Networks on CIFAR100

  • The experiments train VGG19 on CIFAR100 and compare batch-size baselines with Gaussian parameter noise and randomly replaced labels.The label-replacement probability starts at 0.1 and is halved at each learning-rate anneal; the Gaussian parameter noise is tuned over values shown in Figure 1.Source: §A.2 · p. 18
  • The runs disable weight decay and BatchNorm to isolate noise regularization, while retaining standard data augmentation.The learning rate starts at 0.004 and is annealed by a factor of 0.1 at iterations 175950 and 293250 during 410550 total iterations.Source: §A.2 · pp. 18–19
  • The label-noise procedure uses a mean-zero gradient perturbation, unlike standard label smoothing, which also introduces a bias.The paper uses the mean-zero version to isolate the effect of noise.Source: §A.2 · p. 18
  • Around 13% accuracy separates label-noise or small-batch training from large-batch or Gaussian-noise training.Noise runs use batch size 256; the small- and large-batch baselines use 26 and 256, respectively.Source: §A.2 · p. 19

B Proof of Stage 0 (Theorem 3.1)

The Stage 0 proof controls the label-noise trajectory using a bounded coupling and a potential function. Its lemmas establish high-probability bounds under the theorem's assumptions.

B Proof of Stage 0 (Theorem 3.1)

  • Because label-noise gradient descent can blow up with small probability, the proof couples its trajectory to a bounded version that behaves similarly.When the trajectory stays within the bound, the coupled and original trajectories coincide.Source: B Proof of Stage 0 (Theorem 3.1) · p. 20
  • The b-bounded potential is nonzero only when the vector's ℓ1 norm is at most b, and the proof shows it falls below √ϵ0 with high probability after enough iterations.The stated lemma assumes the coupled trajectory remains positive in every dimension.Source: B Proof of Stage 0 (Theorem 3.1) · p. 21
  • The proof combines high-probability lemmas to bound the coupled trajectory and then establishes an upper bound on each coordinate at the final time.It also derives a lower-bound argument for each coordinate before completing the theorem proof.Source: B Proof of Stage 0 (Theorem 3.1) · pp. 20, 22

C Proof of Stage 1 (Theorem 3.3)

The Stage 1 proof treats ground-truth support coordinates separately from zero coordinates. Its lemmas control both groups and show that a bounded potential on the zero coordinates decreases.

C Proof of Stage 1 (Theorem 3.3)

  • The proof uses different trajectory boundaries for support and non-support dimensions because the former are expected to grow larger.A bounded coupling is used to keep the trajectory within those controls.Source: C Proof of Stage 1 (Theorem 3.3) · p. 23
  • Support coordinates are shown not to grow much beyond their ground-truth value, and the proof also bounds how far they can fall below it.The accompanying lemmas state that a support coordinate gets close to its target and, once close, does not become much smaller.Source: C Proof of Stage 1 (Theorem 3.3) · pp. 23, 26
  • The proof separately controls dimensions outside the support so they do not become much larger than their zero ground-truth values.A potential defined on these dimensions is shown to decrease below √ϵ1 after a suitable number of iterations.Source: C Proof of Stage 1 (Theorem 3.3) · pp. 24, 27

D Proof of Stage 2 (Theorem 3.4)

Stage 2 bootstraps the Stage 1 approximation: repeated rounds make support coordinates closer to the ground truth while controlling the remaining coordinates. The proof also contrasts label-noise SGD's initialization requirement with that of gradient descent.

D Proof of Stage 2 (Theorem 3.4)

  • Repeated bootstrapping rounds bring support coordinates closer to the ground truth by a factor of 10 while keeping other coordinates from increasing too much.The proof describes this as starting from the Stage 1 error and repeatedly applying the refinement analysis.Source: D Proof of Stage 2 (Theorem 3.4) · p. 30
  • The theorem's conclusion bounds the error outside the support by ϵs, defined in terms of the preceding round's error.The stated bound is ∥v̄S − v⋆̄S∥1 ≤ ϵs.Source: D Proof of Stage 2 (Theorem 3.4) · p. 30

E Proof of Theorem 2.1

The proof of Theorem 2.1 proceeds through three stages of SGD with label noise, tightening the target precision in successive rounds. It combines the stages into a final-iterate guarantee with probability at least 0.97.

E Proof of Theorem 2.1

  • The proof sets the intermediate target precision to ϵ1 = ϵ/403 before applying Theorem 3.3.That stage assumes n ≥ e^Θ(r^2 log^2(1/ϵ)) data.Source: E Proof of Theorem 2.1 · p. 37
  • The final stage uses ⌈log10(1/ϵ)⌉ rounds, reducing c_s by a factor of 10 each round until it lies between ϵ/10 and ϵ.The proof sets ρ = 0.01/⌈log10(1/ϵ)⌉ for these rounds.Source: E Proof of Theorem 2.1 · p. 37
  • The three stages together yield the final-iterate guarantee with probability at least 0.97.The stated total failure rate is 0.03.Source: E Proof of Theorem 2.1 · p. 37

F Proof of Theorem 2.2

The proof of Theorem 2.2 uses a high-probability intersection between the data-orthogonal subspace and the coordinate-wise positive cone. It then uses the unobserved dimensions to show divergence of the relevant integral when n < d/2.

F Proof of Theorem 2.2

  • With probability at least 0.999, the subspace orthogonal to the data intersects the coordinate-wise positive cone in a nonzero vector.The proof scales such a vector to have unit norm.Source: F Proof of Theorem 2.2 · p. 38
  • Because the loss depends only on the projection of u onto the data span, the proof rewrites it as a function of the first n transformed coordinates.The remaining d−n dimensions can then be integrated over a feasible region where Aũ is coordinate-wise positive.Source: F Proof of Theorem 2.2 · pp. 38–39
  • For n < d/2, the integral over the feasible region diverges because its integrand has polynomial degree greater than −1 in the positive integration variable.The proof obtains this region by constructing a convex cone contained in the feasible set.Source: F Proof of Theorem 2.2 · p. 39

G Helper Lemmas

The helper lemmas establish probabilistic bounds under Gaussian-data sampling and conditional drift-and-variance assumptions. Their proofs use concentration arguments and coupled supermartingales.

G Helper Lemmas

  • Lemma G.1 assumes iid standard Gaussian data and states a simultaneous per-sample property with probability at least 1−ρ.The supplied statement does not include the property itself.Source: G Helper Lemmas · p. 40
  • Lemma G.2 assumes n > 24 log(d/ρ) and states a simultaneous per-coordinate conclusion with probability at least 1−ρ.Its proof invokes concentration for a chi-squared distribution, using the Gaussian coordinate moments E[x_k^2] = 1 and E[x_k^4] = 3.Source: G Helper Lemmas · p. 40
  • Lemma G.3 considers a process whose conditional expectation contracts by 1−γ while it remains in range, and whose conditional variance is bounded.The proof couples the process to a scaled version and uses a supermartingale argument.Source: G Helper Lemmas · p. 40
  • Lemma G.4 applies a similar contraction-and-variance setup when an event may occur, using a coupled supermartingale in its proof.The process is considered while it remains in [c1,c2] and before the event occurs.Source: G Helper Lemmas · p. 41

Related papers

Loading 2006.08680v2…