Research map / Optimization / Implicit bias and generalization

Emergence of heavy tails in homogenized stochastic gradient descent

NeurIPS 2024 · Optimization › Implicit bias and generalization · approach: SGD noise and flat minima · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows via a convex-stochastic-order comparison to Pearson diffusions that homogenized SGD (hSGD) on regularized linear regression has an asymptotically heavy-tailed parameter distribution, with explicit upper and lower bounds on the tail-index validated numerically.

Problem

Explaining why SGD iterates develop heavy-tailed parameter distributions, and quantifying how the tail-index depends on optimization meta-parameters, in a tractable setting.

Approach

Compare the diffusion approximation hSGD (SDE driven by Brownian motion with state-dependent noise) in convex stochastic order to decoupled Pearson diffusions (skew t stationary laws), yielding explicit tail-index upper bound and lower bound from moment stability.

Key results

• Empirical ccdf of SGD iterates lies between the explicit lower bound eta_* and upper bound eta^* (e.g., eta_*=3.56, eta^*=3.61 for the synthetic setting).
• The fitted t-distribution gives a good QQ fit to SGD iterates, while the fitted alpha-stable overestimates tail heaviness; KS test rejects the alpha-stable fit for two of three settings.
• Tail-index bounds increase with regularization and batch size and decrease with learning rate and top singular value of the data matrix.

Measured effects reported in the paper

Surprising findings

• The tail-index bounds do not explicitly depend on dimension d, which appears to contradict prior qualitative findings but is reconciled via the Wishart largest-eigenvalue scaling.

Limitations

• Results derived only for plain SGD with constant learning rate, not momentum or adaptive methods.
• Analysis based on a quadratic (linear regression with ridge) loss and a diffusion approximation of SGD.
• Lower bound requires an assumption on the learning rate (gamma below an upper threshold).

Experimental setup

Datasets: synthetic isotropic Gaussian regression data (n=2000) scikit-learn handwritten digits (n=1797) random feature model built on digits

Benchmarks: synthetic Gaussian regression digits dataset regression random feature model

Metrics: tail-index bounds QQ-plots complementary CDF Kolmogorov-Smirnov test p-value

Baselines: alpha-stable fit (Simsekli et al.) Gurbuzbalaban et al. heavy-tail analysis

Builds on: homogenized stochastic gradient descent Pearson diffusions Ornstein-Uhlenbeck approximation of SGD

Closest papers by meaning

• The Heavy-Tail Phenomenon in SGD (ICML 2021 · similarity 0.94)
• Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions (ICML 2023 · similarity 0.92)
• Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent (NeurIPS 2023 · similarity 0.92)
• Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.91)
• Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD (ICML 2024 · similarity 0.89)
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.89)