PaperlayerView exact revision on arXiv

Source-linked AI summary

The Heavy-Tail Phenomenon in SGD

Mert Gurbuzbalaban, Umut Şimşekli, Lingjiong Zhu

arXiv:2006.04740v5math.OCcs.LGmath.ST

TL;DR

The paper addresses the unresolved relationship among SGD generalization perspectives including flatness, η/b, and heavy-tailed weights. It analyzes SGD through affine stochastic recursions and proves that even simple quadratic problems can yield heavy-tailed iterates, while identifying parameter, dimension, and curvature effects and testing the theory in neural networks.

  • Problem

    The originating cause of heavy-tailed behavior in SGD and its connection to stepsize, batch-size, and curvature remain insufficiently understood.

  • Method

    The paper analyzes quadratic linear-regression SGD through affine stochastic recursions and uses Lyapunov stability and implicit renewal theory to study stationary tails.

  • Results

    Even with light-tailed i.i.d. data, SGD iterates can converge to distributions with arbitrarily heavy tails and infinite variance, with tail behavior characterized by algorithm parameters, dimension, and curvature.

  • Takeaways & Limitations

    The results connect SGD's stepsize, batch-size, and curvature to the heavy-tailed behavior of its iterates and provide insights for deep-learning SGD.

  • Takeaways & Limitations

    The analysis primarily treats quadratic losses and linear regression, while extensions to fully non-convex losses and finite-sum training remain future directions.

Abstract

from arXiv · show

In recent years, various notions of capacity and complexity have been proposed for characterizing the generalization properties of stochastic gradient descent (SGD) in deep learning. Some of the popular notions that correlate well with the performance on unseen data are (i) the `flatness' of the local minimum found by SGD, which is related to the eigenvalues of the Hessian, (ii) the ratio of the stepsize $η$ to the batch-size $b$, which essentially controls the magnitude of the stochastic gradient noise, and (iii) the `tail-index', which measures the heaviness of the tails of the network weights at convergence. In this paper, we argue that these three seemingly unrelated perspectives for generalization are deeply linked to each other. We claim that depending on the structure of the Hessian of the loss at the minimum, and the choices of the algorithm parameters $η$ and $b$, the SGD iterates will converge to a \emph{heavy-tailed} stationary distribution. We rigorously prove this claim in the setting of quadratic optimization: we show that even in a simple linear regression problem with independent and identically distributed data whose distribution has finite moments of all order, the iterates can be heavy-tailed with infinite variance. We further characterize the behavior of the tails with respect to algorithm parameters, the dimension, and the curvature. We then translate our results into insights about the behavior of SGD in deep learning. We support our theory with experiments conducted on synthetic data, fully connected, and convolutional neural networks.

1. Introduction

SGD generalization is associated with flatness, optimization parameters, and heavy-tailed weights, but the origin of the observed heavy tails remains unclear. The paper argues these perspectives are linked and studies how η, b, dimension, and curvature shape SGD's stationary behavior.

  • Problem setting: Neural-network generalization is studied through population and empirical risk minimization, with SGD optimizing the empirical objective using stochastic gradients.The stochastic gradient uses a random batch of training examples, with η as stepsize and b as batch-size.
  • Open problem: SGD can show substantially different unseen-test performance depending on the stepsize η and batch-size b, a behavior not yet theoretically well-grounded.This motivates analyzing how algorithm choices affect generalization-related behavior.
  • Related perspectives: Flatness, stepsize-to-batch-size effects, and heavy-tailed network weights are three perspectives used to characterize generalization.Flatness is linked to Hessian eigenvalues, while heavier-tailed weight matrices have been associated empirically with better generalization.
  • Open problem: The originating cause of the heavy-tailed behavior observed in network weights remains unknown despite prior empirical and theoretical connections between tails and generalization.The paper positions its analysis as addressing this unresolved mechanism.
  • Paper approach: The paper argues that SGD exhibits a heavy-tail phenomenon whose stationary distribution depends on η, b, dimension d, and the curvature of the objective.The claim links algorithm parameters and local curvature to the distribution of SGD iterates.
  • Main result: Even with light-tailed i.i.d. data, quadratic optimization can produce SGD iterates with arbitrarily heavy tails and infinite variance.For isotropic Gaussian inputs, the paper further characterizes how tail heaviness changes with curvature, η, and b.

2. Technical Background

The technical background defines heavy tails and power-law decay, including the tail-index that quantifies tail thickness. It also introduces stable distributions and Wasserstein distance as tools for describing heavy-tailed limits and convergence.

  • Heavy tails: A real-valued variable is heavy-tailed when at least one tail decays more slowly than every exponential distribution.The paper formalizes this using the asymptotic behavior of tail probabilities.
  • Heavy tails: A random vector has a heavy tail when some unit-direction projection has a heavy right tail.This extends the scalar definition to vector-valued iterates.
  • Power-law decay: Power-law decay has the form P(X ≥ x) ∼ c0x^-α, where the tail-index α determines tail thickness.Smaller α corresponds to heavier tails in the paper's power-law framework.
  • Stable distributions: Symmetric α-stable distributions are power-law heavy-tailed distributions whose finite moments exist only below order α.For 0 < α < 2, their variance is infinite; α = 1 and α = 2 yield Cauchy and Gaussian cases.
  • Technical positioning: Prior work established power-law tails for broader contracting stochastic optimization algorithms, while this paper focuses on SGD for linear regression to derive parameter-dependent tail-index constants.The specialized SGD setting enables explicit dependence on data and algorithm parameters.
  • Wasserstein metric: The p-Wasserstein metric compares probability measures with finite p-th moments through the infimum over joint distributions having the specified marginals.The paper uses this metric to describe convergence toward stationary distributions.

3. Setup and Main Theoretical Results

The paper characterizes when SGD converges to stationary distributions with polynomially heavy tails, linking tail behavior to stepsize, batch-size, curvature, variance, and dimension. Its quadratic analysis identifies finite-variance, infinite-variance, and non-convergent regimes, while also establishing convergence rates and moment behavior.

  • Analytical framework: The analysis uses an affine stochastic-recursion approximation together with Lyapunov stability and implicit renewal theory to derive stationary-tail properties.The recursion framework supplies conditions for existence, uniqueness, and distributional convergence of the stationary solution.
  • Tail characterization: SGD iterates can converge to a stationary distribution with polynomial tails and infinite variance even when the input data have no heavy tails.The tail-index α is the unique positive solution of h(α)=1 under the theorem’s conditions.
  • Parameter dependence: For Gaussian inputs, the tail-index α increases with batch-size and decreases with stepsize, variance, and dimension when α≥1.For non-Gaussian inputs, the corresponding lower bound ˆα increases with batch-size and decreases with stepsize and variance under the stated condition.
  • Stepsize regimes: The critical stepsize ηcrit = 2bσ2(d+b+1) separates finite-variance and infinite-variance stationary regimes.For η<ηcrit, α>2; at η=ηcrit, α=2; and for ηcrit<η<ηmax, 0<α<2.
  • Stepsize regimes: The three regimes are finite-variance convergence when α>2, heavy-tailed infinite-variance convergence when α<2, and no guaranteed convergence when ρ>0.Increasing stepsize can move Gaussian-input SGD from the finite-variance regime into the heavy-tailed regime before the maximum stable stepsize is reached.
  • Convergence and moments: When α<2, convergence to the heavy-tailed stationary distribution is linear in the p-Wasserstein metric for p<α, while the α-th stationary moment is infinite.The α-th moments of finite iterates grow as O(k) for α≤1 and O(k^α) for α>1.

4. Experiments

Experiments on synthetic data and neural networks support the theory that SGD can produce heavy-tailed iterates, with tail behavior depending on stepsize, batch-size, dimension, curvature, and optimizer choice.

  • Synthetic experiments: Synthetic linear-regression experiments estimate stationary tail-indices using α-stable-limit estimators applied to averaged, centered iterates after burn-in.The procedure repeats runs from different initializations and estimates α from the resulting random vectors.
  • Synthetic experiments: Increasing η or decreasing b lowers α, with α strongly correlated with the ratio η/b and sometimes falling below 1.When α < 1, even the mean of the stationary distribution is not defined.
  • Synthetic experiments: Increasing σ or d decreases α, and changing d can abruptly alter the tail-index for fixed η and b.These observations match the predicted dependence of tail behavior on problem dimension and curvature-related parameters.
  • Synthetic experiments: Under RMSProp, clipping prevents the iterates from becoming heavy-tailed in the experiment, with most estimated tail-indices near 2.The result is interpreted as indicating approximately Gaussian behavior.
  • Neural-network experiments: Experiments on fully connected and VGG networks examine whether the predicted tail behavior extends beyond quadratic optimization.The VGG experiments vary η and b across layers and report layer-dependent tail-indices, with layers 2–8 correlating well with η/b.

5. Conclusion and Future Directions

The paper concludes that SGD iterates can converge to heavy-tailed random variables depending on η, b, and curvature, and reports experimental support beyond quadratic settings. It identifies finite-sum analysis and broader nonquadratic heavy-tail theory as future directions.

  • SGD can converge in distribution to a heavy-tailed random variable depending on the stepsize, batch-size, and curvature.
  • Experiments on neural networks support the theory and suggest that the results apply beyond the quadratic setting.
  • Extending the streaming-setting proofs to finite-sum problems and studying finite-sample effects on the tail-index remain future directions.

Appendix A. A Note on Stochastic Differential Equation Representations for SGD

The appendix reviews SDE representations of SGD under Gaussian and heavy-tailed noise assumptions, explaining when these approximations capture or miss heavy-tailed iterates.

  • SDE representations: SGD can be analyzed as a discretization of an SDE after rewriting its recursion in terms of stochastic gradient noise.Different statistical assumptions on the noise produce different continuous-time models.
  • Gaussian noise: Under state-independent Gaussian noise, SGD corresponds to an Ornstein–Uhlenbeck process with a Gaussian invariant measure.This approximation assumes noise covariance independent of the iterate.
  • Gaussian noise: The Gaussian approximation is suitable only when α ≥ 2; for α < 2, it cannot capture the heavy tails of SGD iterates.The limitation arises because additive isotropic noise yields a deterministic multiplicative matrix and omits multiplicative noise.
  • Multiplicative noise: State-dependent Gaussian covariance yields a multiplicative-noise SDE that can capture heavy-tailed structure, but its linear-regression process has lognormal tails.For general cost functions, the covariance is more complicated and the invariant measure may not be analytically available.
  • Heavy-tailed noise: Heavy-tailed gradient noise leads to a Lévy-driven SDE; in linear regression, the resulting fractional OU process has an α-stable invariant measure.This model is especially relevant in the large η/b regime.
  • Lévy processes: Lévy motions have independent stationary increments and include Brownian motion as a special case when α = 2.The appendix defines symmetric α-stable Lévy motion componentwise through independent scalar α-stable processes.

C.1 Proof of Theorem 2

The proof applies a stochastic-recursion theorem to the SGD dynamics and verifies its required distributional and nondegeneracy conditions under the paper’s assumptions.

  • Proof setup: The proof treats the iterates as a stochastic recursion with i.i.d. pairs (M_k, q_k), each independent of the preceding iterate.This representation enables application of the cited stochastic-recursion theorem.
  • Conditions: The theorem requires invertibility, a continuous density near the identity, nondegenerate fixed-point behavior, and additional stated conditions.The supplied proof explicitly lists invertibility, local density, and the condition P(Mx + q = x) < 1.
  • Conditions: All required conditions are satisfied under the paper’s assumptions, with specific conditions established by Lemma 21 and others following from continuity or stated assumptions.The proof assigns each verification to the relevant lemma or assumption set.

C.2 Proof of Theorem 3

The proof establishes existence and uniqueness of a positive tail index by analyzing the convex function h when its derivative at zero is negative.

  • Tail-index existence: ρ < 0 implies a unique positive α satisfying h(α) = 1.The argument uses h(0) = 1, h′(0) = ρ < 0, convexity, and lim inf_s→∞ h(s) > 1.

C.3 Proof of Theorem 4

The proof characterizes how the tail index changes with stepsize, batch size, and dimension by studying convexity and monotonicity properties of h(a, s).

  • Stepsize and variance: The tail-index α is strictly decreasing in stepsize η and variance σ^2 when α ≥ 1.The proof combines these parameters through a := ησ^2 and analyzes the level curve h(a, s) = 1.
  • Stepsize and variance: The level set C = {(a, s) ∈ (0, ∞) × [1, ∞] : h(a, s) = 1} defines the admissible tail-index curve.Smoothness permits representing the curve as s(a), whose derivative is shown to be negative.
  • Level-set geometry: The curve h(a, s) = 1 separates regions where h is below or above one, with h > 1 in the upper-right rectangular region.Convexity establishes the inequalities on either side of the marked boxes in Figure 4.
  • Level-set geometry: The proof uses convexity to show h(a, s) < 1 in the lower-left region and h(a, s) > 1 for sufficiently larger a and s.The corresponding regions are illustrated by rectangular boxes in Figure 4.
  • Batch size: The tail-index α is strictly increasing in batch size b when α ≥ 1.Jensen’s inequality makes h(b, s) strictly decreasing in b for s ≥ 1.
  • Dimension: The tail-index α is strictly decreasing in dimension d.The function h(s) is strictly increasing in d through the chi-square variable associated with d − 1 degrees of freedom.
  • Batch size: For d = 1, the same batch-size monotonicity follows because h(b, s) is strictly decreasing in b for s ≥ 1.The proof specializes the chi-square representation to Y ≡ 0.

C.4 Proof of Proposition 5

The proof characterizes when the SGD recursion admits a tail-index through the moment function h. It distinguishes regimes where the tail-index is below or above 2 based on η, batch size, variance, and dimension.

  • Critical stepsize: At η = ηcrit, strict Jensen inequality gives ρ < 0, and continuity extends this result to a neighborhood above ηcrit.The critical condition is ησ2(d + b + 1) = 2b.
  • Tail-index regime: When η > ηcrit, there exists 0 < α < 2 such that h(α) = 1, identifying a tail-index below 2.The result follows from the behavior of h in the supercritical regime.
  • Tail-index regime: When η ≤ ηcrit, h(2) ≤ 1 and therefore α > 2; at η = ηcrit, the tail-index equals 2.Thus the critical threshold separates finite-variance and heavier-tailed regimes in this characterization.
  • Moment bounds: The proof bounds moments of the iterates by exploiting spherical symmetry, moment inequalities, and contraction conditions for h(p).For p below the tail-index, the relevant moments remain controlled through iterative bounds.

C.6.2 PROOF OF COROLLARY 9

This proof uses the Gaussian-data representation of h(p) to distinguish whether the tail-index exceeds 2 or lies at most 2. The threshold is determined by ησ2 relative to 2b/(d+b+1).

  • Gaussian representation: For Gaussian data, h(p) is expressed using independent chi-square variables with degrees of freedom b and d − 1.The quantity h(p) is the central object used to locate the tail-index.
  • Case distinction: When ησ2 ≥ 2b/(d+b+1), the tail-index satisfies p < α ≤ 2, and a second-order approximation of h(p) applies.The proof contrasts this regime with the α > 2 case.

C.6.3 PROOF OF PROPOSITION 10

The proof establishes moment-growth behavior at and around the tail-index. Moments at the critical exponent grow linearly, while slightly higher moments grow exponentially.

  • Critical moment: At the tail-index α, the α-th moment of the stationary distribution is infinite.The proof derives this from the tail characterization of the stationary law.
  • Moment growth: For α ≤ 1, the relevant moment bound grows linearly in k.This describes the iteration-wise growth at or below the mean-existence threshold.
  • Moment growth: For α > 1, moments of order 1 + ε grow exponentially in k for every fixed ε > 0.Letting ε approach zero yields a polynomial-growth characterization at the boundary.
  • Moment growth: Choosing ε = αk^-α produces a bound that grows polynomially in k.This choice makes ε decrease with the iteration count.

C.6.4 PROOF OF COROLLARY 11

The proof develops the moment and contraction machinery underlying the corollary for the SGD recursion. It uses the Lyapunov exponent and the function h to characterize stationary behavior and tail-index dependence.

  • Recursion: The SGD iterates are represented as x_k = M_kx_{k−1} + q_k, with i.i.d. random matrix-noise pairs.This recursion is the starting point for the stationary-distribution analysis.
  • Gaussian structure: For isotropic Gaussian data, spherical symmetry reduces norm calculations to the distribution of the first basis-vector image.This reduction supports the moment formulas used throughout the proof.
  • Moment function: The function h is homogeneous under scaling of the iteration matrices, and this property links h to the corresponding scalar moment function.The proof uses this homogeneity together with h(α) = 1 to identify the relevant moment threshold.
  • Stationarity and tails: The Lyapunov exponent ρ and moment function h determine whether a stationary distribution with tail-index α exists.Strict convexity of h and its behavior at large s provide the key existence argument.
  • Technical bounds: The technical lemmas establish invertibility and moment bounds for the random matrix M needed in the stationary-distribution argument.These bounds control quantities involving M, M^-1, and the iterates' moments.
  • Parameter dependence: Convexity of h and related functions is used to establish how the tail-index changes with stepsize and variance.The proof specifically invokes convexity to show that α is strictly decreasing in η and σ2.
Loading 2006.04740v5…