PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Tail Laws for Nonlinear SGD with Infinite-Variance Gradients

Xiaoli Li, Qianqian Lei, Ziyang Wei, Wei Biao Wu

arXiv:2610.23750v1math.STstat.MLstat.TH

TL;DR

Infinite-variance gradient noise can make expected excess objective infinite even when most SGD iterates stay close to the optimum. The paper derives nonlinear last-iterate tail laws by transporting large shocks through local curvature. The resulting measure gives relative tail accuracy at shrinking thresholds and supports objective-tail conclusions.

  • Problem

    With infinite-variance gradient noise, expected excess objective can be infinite even when most iterates are close to the optimum, making tail probabilities a useful accuracy measure.

    Source: §1 · pp. 1–2

  • Method

    The analysis transports a large gradient shock through the local Hessian flow to derive tail laws for nonlinear constant-stepsize SGD.

    Source: §1 · pp. 2–3

  • Results

    The propagated measure gives vanishing-relative-error tail probabilities at shrinking thresholds for nonlinear SGD and governs large-error directions and excess-objective tails.

    Source: §1 · pp. 2–3, §2 · p. 8

  • Takeaways & Limitations

    Tail probabilities and increasingly rare objective quantiles remain informative even when expected excess objective is infinite.

    Source: §1 · p. 1

    The analysis assumes fixed dimension and centered dissipativity around a single equilibrium.

    Source: §6 · p. 16

Abstract

from arXiv · show

With infinite-variance gradient noise, SGD can have infinite expected excess objective even when most iterates are close to the optimum. We characterize its accuracy through exact first-order tail probabilities for the last iterate of nonlinear, constant-stepsize SGD. For regularly varying innovations of index $t\in(1,2)$, the leading measure transports one large gradient shock through the local Hessian flow. This is the same measure that governs the central stable Ornstein--Uhlenbeck limit; we prove its relative accuracy at shrinking tolerances above the central scale, with state-dependent noise and a growing observation horizon. The admissible window is nonempty for every available gradient moment $p>1$. The main technical step is a moment bound at the central fluctuation scale and a lower-moment control of the nonlinear error. The result yields explicit projection and excess-objective tails, extreme quantiles, and a factor $b^{1-t}$ for fixed batch size $b$. For affine population gradients, a sharper comparison gives the same law at fixed tolerances, including random sample Hessians. Coupled simulations in dimensions one to one hundred examine relative calibration, objective quantiles, batch effects, and the error due to random curvature.

1 Introduction

With infinite-variance gradient noise, expected excess objective can misrepresent how often nonlinear constant-stepsize SGD makes a large error. This paper derives sharp tail probabilities by tracking a large gradient shock through local curvature, and distinguishes that rare-event analysis from prior work on convergence, stability, or Gaussian behavior.

1 Introduction

  • Exact first-order tail probabilities with leading constants characterize how often nonlinear constant-stepsize SGD exceeds shrinking error tolerances.The analysis addresses a setting where expected excess objective can be infinite even when most iterates remain close to the optimum.Source: §1 · pp. 1–3
  • The leading measure transports one large gradient shock through the local Hessian flow, determining the direction of large errors and excess-objective tails.The flow e^-sH transports a shock of age s, while 1/γ counts effective shock opportunities.Source: §1 · p. 2

1.1 Contributions

  • A central-scale moment bound and lower-moment nonlinear-error control yield a nonempty threshold window for every admissible gradient moment p > 1.For a quadratic local remainder, the stated window is (t − p)/t < a < (t − 1)/t.Source: §1.1 · p. 3
  • The tail measure supports projection and directional laws, extreme objective quantiles, and fixed-batch scaling; affine population gradients also admit a fixed-tolerance extension under an additional moment condition.That extension includes models with random sample Hessians.Source: §1.1 · p. 3

1.2 Related literature

2 Setting and main tail results

The paper characterizes extreme errors in nonlinear constant-stepsize SGD with regularly varying noise through a tail measure shaped by the local Hessian flow. Its results cover projections, error directions, and excess-objective tails, including shrinking-threshold accuracy and curvature effects.

2 Setting and main tail results

  • The leading measure transports a large shock of age s through the local flow e^(-sH), with 1/γ counting effective shock opportunities.The propagated measure also governs the stationary stable Ornstein–Uhlenbeck limit.Source: §2 · pp. 6, 8
  • For nonlinear SGD with regularly varying innovations of index t in (1,2), the theorem gives a relative tail equivalence for admissible sets as the effective observation horizon diverges.The initialization and horizon must satisfy the stated burn-in conditions.Source: §2 · pp. 6–7
  • Half-space sets yield projection tails, while norm and directional sets describe the size and direction of extreme errors when their boundaries have zero νH mass.The conditional direction of a large error is obtained by mapping z to z/|z|.Source: §2 · p. 7
  • For an eigenvector projection, local curvature enters the tail constant inversely, while objective tails scale with curvature as λ^(t/2−1) under the stated isotropic case.For nonscalar H, the full interaction between curvature and tail geometry remains in νH.Source: §2 · pp. 7–8
  • The theorem gives excess-objective tails through the quadratic exceedance set; for pure power innovation tails, the objective threshold has exponent t/2 in the joint limit.These tail probabilities remain informative when expected excess objective value is infinite.Source: §2 · p. 7

3 Why the linearization is relatively accurate

The proof establishes relative accuracy by combining central-scale moment control, a linear single-jump limit, and a lower-moment comparison of nonlinear and linear recursions. This yields a nonempty admissible threshold window under the stated moment conditions.

3.1 Central-scale moments and the coupled recursion

  • The central-scale moment bound attains the polynomial order of the stable linear example, improving the coarse exponent by 1−p/t.The coupled recursion uses the same innovations for the nonlinear iterate and its linear approximation.Source: §3.1 · p. 9

3.2 Linear single-jump limit

  • The linear single-jump theorem identifies the vector tail through the Hessian-flow measure, with truncated moments controlling small jumps uniformly over the horizon.The linear theorem also allows fixed positive tolerances.Source: §3.2 · p. 10

3.3 A lower-moment nonlinear transfer

  • A lower-moment bound controls the central-scale linearization error and transfers the linear tail law to nonlinear SGD at the rare-event scale.When the gradient conditions hold for every 1<p<t, a fixed p sufficiently close to t covers every fixed threshold uγ=cγ^a with 0<a<(t−1)/t.Source: §3.3 · p. 10
  • For a quadratic remainder, the sufficient threshold window is nonempty for every available gradient moment p>1; the argument also extends to local Hölder remainders with 1<β≤2.The proof separates uniform moment control, a linear single-jump limit, and nonlinear comparison.Source: §3 · p. 8, §3.3 · p. 10

4 Consequences and extensions

The tail law supplies objective quantiles and quantifies effects of batch size, stepsize, and observation time. The paper also gives a fixed-tolerance extension for affine population gradients and explains how nonlinear flow recovers the local-Hessian description at shrinking tolerances.

4 Consequences and extensions

  • The objective quantile formula relates an extreme loss level to its exceedance probability, with the restriction on ζ keeping the iterate threshold inside the nonlinear theorem’s admissible window.Quantiles describe the upper tail even when expected objective value is infinite.Source: §4 · p. 11
  • For fixed batch size b, averaging multiplies the leading tail probability by b^(1−t); for pure power tails, its stepsize and batch dependence is (γ/b)^(t−1) at a common admissible tolerance.At t=1.5, batches of four and sixteen reduce the leading tail probability by factors of 1/2 and 1/4, respectively.Source: §4 · p. 11
  • For affine population gradients, the tail law extends to every fixed u>0 when t^2/(2t−1)<p<t, and the conclusion also holds at p=t when the full gradient conditions hold there.The extension can include sample gradients with random curvature.Source: §4 · p. 11
  • At finite effective observation time T, the eigenvector tail constant is multiplied by 1−e^(−tλvT), describing its approach to the long-time level.Source: §4 · p. 12
  • For nonlinear drift, shock propagation follows the nonlinear flow, and at shrinking tolerances the local Hessian description is recovered.Source: §4 · p. 12

5 Numerical studies

The numerical studies test nonlinear tail calibration, extreme objective quantiles and batching, and the effect of random sample curvature. The single-jump predictions calibrate rare objective events, while batch effects and finite-step curvature effects are also measured.

5.1 Tail calibration in a nonconvex model

  • Figure 1 reports nonconvex tail calibration across 241 thresholds, using the same 600,000 terminal pairs per stepsize; its black dashed curve in panel (b) is deterministic flow diagnostic Rflow(u).Source: Figure 1 · p. 13
  • At the smallest step, total ratios are within 5.2% of one; the smallest-step objective ratios are 0.907 and 0.993.The flow diagnostic tracks the transfer deficit within 0.01 at six prespecified points.Source: §5.1 · pp. 13–14, Table 1 · p. 13

5.2 Extreme objective values and batching

  • 0.5%–10.8%: single-jump predictions differ from empirical 99.9% full-objective quantiles, and all fall within pointwise intervals.The median Gaussian fits underestimate these quantiles by factors of about 37, 61, and 120.Source: Table 2 · p. 14, §5.2 · pp. 14–15
  • 0.487 and 0.252: median tail-probability ratios for batches of four and sixteen are close to 1/2 and 1/4; the matched-γ/b ratio median is 1.021.The relative-probability display includes only count-qualified thresholds with baseline probability below 0.05.Source: Figure 2 · p. 15, §5.2 · p. 15

5.3 Random curvature and finite-step accuracy

  • At γd = 1, retaining random curvature reduces median ratios from about 4.3 to 1.08–1.14; at γd = 0.1, random-Hessian ratios are 1.007 and 1.041.The ratios summarize four directions and 17 thresholds.Source: §5.3 · p. 15, Table 3 · p. 16

6 Discussion

The analysis identifies a regime where local curvature and the innovation law at the target determine rare errors, but its scope is limited to fixed dimension and centered dissipativity around one equilibrium.

6 Discussion

  • The analysis assumes fixed dimension and centered dissipativity around a single equilibrium; multiple basins and dimension-dependent regimes remain extensions.The discussion also identifies a stochastic fixed-tolerance extension and quantitative control of finite-step effects as ways to strengthen practical use of the approximation.Source: §6 · p. 16

A Proof of the Lp Moment Bound

The appendix establishes moment control and linear stability, then uses one-jump and projection arguments to obtain vector and projected tail conclusions.

A Proof of the Lp Moment Bound

  • E|Xn|^r is bounded by a geometrically decaying initialization term plus a stationary-scale term of order γ^(r−1), for 1 < r ≤ p.The bound holds for n ≥ 0 and sufficiently small γ.Source: A Proof of the Lp Moment Bound · p. 20

B.1 Stability of the vector linearization

  • Centered dissipativity implies that the linearization H is positive stable, and its small-step linear map contracts for sufficiently small γ.The proof derives a positive lower bound on the symmetric part of H from the dissipativity condition.Source: §B.1 · p. 22

B.2 Proof of Theorem 3

  • The vector tail proof obtains an additive one-jump limit and, when the limiting measure is positive on the event, the corresponding relative single-jump equivalence.The argument transfers the result to the linearized iterate after controlling initialization.Source: §B.2 · p. 26

B.3 Proof of Corollary 3

  • The projected half-space boundary has zero mass under the transported homogeneous measure, supporting the projected tail limit despite the initial-condition shift.The proof applies the result at thresholds (1 ± ε)uγ and then lets ε decrease to zero.Source: §B.3 · p. 26

B.4 Projected tails under one-dimensional regular variation

  • For a left eigenvector of H, the projected recursion is scalar, allowing a one-dimensional regular-variation assumption on projected innovations; power thresholds require a < (t−1)/t when hv(u) converges to a positive constant.The leading projected tail probability is identified as a sum of single-jump probabilities.Source: §B.4 · pp. 27–28

B.5 Proof of Theorem 6

The proof controls the projected linear tail over a growing horizon by isolating large jumps and bounding small-jump and remote-past contributions. A separate nonlinear comparison controls approximation error at the rare-event scale.

B.5 Proof of Theorem 6

  • The projected linear tail is asymptotically bounded above and below by the one-jump intensity, using truncation to control multiple large jumps and the small-jump remainder.The proof also splits shock ages at a cutoff to handle the growing horizon.Source: §B.5 · pp. 29, 31
  • The proof controls the matrix-weight limit, remote-past contributions, and accumulated small jumps, yielding the impulse-response constant and removing initialization under the burn-in condition.These estimates extend beyond the cited framework’s bounded drift and noise assumptions and support the subsequent nonlinear transfer.Source: §B.5 · pp. 33–34

C.1 Proof of the central-scale moment bound

The appendix establishes moment control and a lower-moment comparison that transfer the linear single-jump tail law to nonlinear SGD. It then extends the result to projections, objectives, less smooth remainders, fixed batches, extreme quantiles, conditional directions, affine fixed tolerances, and finite horizons.

C.1 Proof of the central-scale moment bound; C.2 Comparison at lower moments

  • The central-scale moment argument and lower-moment comparison bound the nonlinear error at the rare-event scale, enabling transfer of the linear tail law.The comparison gives E|∆n|^q ≤ Cqγ^(p−1) plus an exponentially decaying initialization term for 1 ≤ q ≤ p.Source: §C.1 · pp. 35–36, §C.2 · p. 36

D Transfer of vector and objective-value tails

  • Projection and excess-objective tails follow from the vector tail law; projected-only regular variation needs p > 2 − 1/t.The projected-only result avoids radial tail control for other coordinates, but has a narrower sufficient moment and threshold window.Source: D Transfer of vector and… · p. 39

E.1 H¨older local remainders

  • For a local remainder |x−x⋆|^β with 1 < β ≤ 2 and 1 < p < t, (24) holds for q ∈ [q*, p], and nonlinear vector, projection, and objective-value tail results hold under the stated threshold window.Here q* = max(1, p/β); the window is nonempty because p > q* for p > 1 and β > 1.Source: §E.1 · p. 40

E.2 Fixed mini-batches

  • A fixed batch of b independent gradients multiplies the leading tail by b^(1−t); at a common admissible threshold, (γ,b) and (γ/b,1) have the same leading tail.The equal-sample-budget comparison also requires a sufficiently growing observation horizon.Source: §E.2 · pp. 41–42

E.3 Extreme objective quantiles

  • The tail law yields excess-objective quantiles for vanishing tail probabilities, with an asymptotic inverse needed for general slowly varying tails.The corresponding threshold exponent is a = (t−1−ζ)/t.Source: §E.3 · p. 42

E.4 Conditional sizes and directions

  • Conditioned on an exceedance, the limiting shock direction is determined by the propagated tail measure, while eigenvector projection constants remain marginal quantities.The direction law is obtained by restricting the measure to |z| > 1 and normalizing by its mass.Source: §E.4 · p. 42

E.5 Affine population gradients at fixed tolerances

  • For affine population gradients, the same tail law extends to fixed tolerances, including random sample Hessians when the stated gradient conditions hold.The sufficient cutoff is p > 9/8 when t = 1.5.Source: §E.5 · p. 43

E.6 Finite observation horizons

  • A finite observation horizon with nγγ → T yields a corresponding vector tail limit with the one-jump sum ending at T.The proof transfers the limit to the nonlinear iterate using the same set-sandwich argument.Source: §E.6 · pp. 43–44

E.7 Localization of the nonlinear flow

The nonlinear-flow localization result connects a large shock propagated through the nonlinear drift to the local linear-flow measure. The adjoining examples distinguish settings where fixed-tolerance stochastic tails remain unproved and where tail probabilities remain informative despite infinite expected excess objective.

E.7 Localization of the nonlinear flow

  • Deterministic localization shows that the nonlinear flow’s small-scale propagated shock measure agrees with the local linear flow’s measure on sets bounded away from zero.The result also holds for the superlinear remainder in Theorem 8.Source: §E.7 · pp. 44–45
  • A fixed-tolerance stochastic tail formula for general nonlinear drifts requires a separate theorem.The text distinguishes this open extension from the deterministic localization and scalar studies described here.Source: §E.7 · p. 45

E.8 Different innovation and state-dependent moment indices

  • State-dependent noise can have fewer available moments away from the target innovation, while the theorem still applies when the stated assumptions hold at p = 1.2.In the example, the target innovation has tail index 1.5, but the full gradient has moments only below 1.25 away from zero.Source: §E.8 · p. 45

E.9 When the expected objective is infinite

  • With regularly varying innovations of index t < 2, expected excess objective is infinite, but the tail probabilities and quantiles remain finite.The text derives the infinite expectation from the infinite second moment and the quadratic lower bound on excess objective.Source: §E.9 · pp. 45–46

F Shrinking-threshold and objective-value experiments

The experiments test shrinking-threshold tail calibration and objective-tail ratios, then isolate random-curvature and nonlinear-drift effects. Calibration generally improves as stepsizes decrease, but finite-step discrepancies remain and depend on the threshold and curvature.

F Shrinking-threshold and objective-value experiments

  • For a = 0.2, total tail ratios are 0.951, 0.972, and 0.948; for a = 0.3, they are 1.021, 1.041, and 1.034.All six paired transfer intervals lie below one, while the point estimates move toward one as the stepsize decreases; Figure 3 and Table 4 report the prespecified comparisons.Source: Table 4 · p. 47, F Shrinking-threshold and… · p. 48, Figure 3 · p. 48
  • The exact-CDF finite-sum correction ranges from 1.000250 to 1.002522 and cannot explain the larger observed differences from one.The experiments use 600,000 independent terminal pairs at each prespecified threshold sequence.Source: F Shrinking-threshold and… · pp. 46, 49
  • For a = 0.2, objective-tail ratios are 0.884, 0.944, and 0.907; for a = 0.3, they are 0.973, 1.007, and 0.993.The faster-shrinking sequence is accurate at the smallest step, while the slower sequence retains a visible finite-threshold discrepancy; Figure 4 gives the objective-tail comparisons.Source: Figure 4 · p. 48, F Shrinking-threshold and… · p. 49

F.1 Random-curvature ablation

  • The random-weight tth-power diagnostic is 1.337, 1.081, and 1.026 across decreasing stepsizes, but it is not a finite-step probability formula.The diagnostic isolates coefficient amplification and omits accumulated small jumps and nonlinear drift.Source: §F.1 · p. 50
  • At the smallest step, random-curvature ratios are 1.080 for a = 0.2 and 1.039 for a = 0.3, while total ratios are 1.019 and 1.074, respectively.Figure 5 and Table 5 distinguish total calibration, random-curvature effects, and the population-remainder effect; finite-step ratios do not show a strictly monotone trend.Source: Table 5 · p. 50, §F.1 · p. 51, Figure 5 · p. 51

G Objective tails, quantiles, and batch effects

The section compares objective-tail benchmarks and plug-in estimates, then specifies multidimensional models, stepsize choices, and the Monte Carlo benchmark used for projected-tail calibration. Pilot calibration improves with sample size, while the multidimensional experiments are designed to probe heavy-tailed noise, random sample curvature, and nonlinear coupling.

G Objective tails, quantiles, and batch effects

  • Three objective-tail predictions range from a local quadratic approximation to an exact-objective evaluation of linearly transported shocks; batch predictions count individual extreme samples, each weighted γ/b.For b > 1, the benchmark sums over independent samples in the unrolled recursion rather than replacing the batch average with a Student variable; theorem control applies in the stated shrinking-tolerance regime.Source: G Objective tails, quantiles, and… · pp. 52–53
  • The covariance-based Gaussian diagnostic is deliberately misspecified because the true innovation covariance is infinite.Five independent covariance fits feed Gaussian predictions evaluated on the full objective, while the matched heavy-tail reference is the coupled linear chain.Source: G Objective tails, quantiles, and… · pp. 53–54

G.1 Repeated plug-in pilots

  • At K = 106, the median empirical/predicted ratio across 20 pilot reporting cells ranges from 0.983 to 1.064, compared with 0.571 to 1.847 at K = 104.The five-fit repetitions show more stable median calibration at the larger pilot size, though individual directions and thresholds retain finite-level discrepancies.Source: §G.1 · p. 55

H Multidimensional Projected-Tail Experiments

  • The multidimensional experiments compare additive heavy-tailed gradients with random-design regression, whose sample Hessian is random and whose noise depends on state.Both models have regularly varying innovations with index 1.5 and satisfy the stated gradient-moment conditions for 1 < p < 1.5; the claims do not give dimension-uniform constants.Source: H Multidimensional Projected-Tail… · p. 57, §H.1 · pp. 57–58

H.2 Step sizes, projections and simulation protocol

  • For Model B, the mean-square contraction bound is approximately 0.1263 at d = 10 and 0.01325 at d = 100, motivating a stepsize scale of 1/d.The simulations use four directions, including a dense non-eigendirection, and independent terminal trajectories at each setting.Source: §H.2 · pp. 59–60

H.3 Deterministic benchmark and Monte Carlo uncertainty

  • The projected-tail benchmark is a finite-horizon sum of single-jump probabilities for the population-Hessian linear recursion, and its plotted intervals quantify Monte Carlo uncertainty only.Symmetry pooling reduces estimator variance in the examples, but the paired signs are not independent trials and the intervals do not include approximation error or simultaneous coverage.Source: §H.3 · pp. 60–61

H.4 Results and scope

The projected-tail experiments show close calibration for additive-noise SGD and larger finite-step discrepancies for random-design regression, with similar patterns at matched γd. A separate random-Hessian benchmark propagates shocks through sample Hessians and reports numerical checks on its denominator.

H.4 Results and scope

  • For Model A, median total ratios are within 6% of one in both dimensions; for Model B, they fall from 4.266 to 1.588 to 1.081 at d = 10 and from 4.331 to 1.586 to 1.118 at d = 100 as matched γd decreases.The similar patterns support the stepsize scaling motivated by γd, without establishing a dimension-uniform result.Source: §H.4 · pp. 62–63, Table 7 · p. 62
  • At d = 100 and γ = 0.001 in Model B, direction-specific median total ratios range from 1.078 to 1.152, leaving an approximately 12% median excess over one.Across the common reporting domain, median and maximum full widths of the pointwise ratio intervals are 0.169 and 0.263.Source: §H.4 · p. 63
  • The fixed-threshold grid is a finite-step diagnostic, whereas the theorem uses shrinking thresholds; near the origin, the one-big-jump sum need not be a rare-event probability.The reported discrepancy patterns are attributed to threshold choice, single-jump calibration, and nonlinear transfer.Source: §H.4 · pp. 62–63

H.5 A random-Hessian single-jump benchmark

  • The random-Hessian benchmark propagates a shock backward through successive sample Hessians, unlike the population-flow benchmark, which uses the population Hessian.The largest shorter-cutoff correction is 0.287%, and the final omitted-age bounds are below 4.1×10^-9 relative to the calculated denominators.Source: §H.5 · pp. 68–69

I Additional scalar calibration studies

Scalar studies test how closely the one-big-jump approximation calibrates nonlinear recursions at finite thresholds. The results show threshold-dependent calibration in the smooth model, while the additional threshold and expectile studies have distinct scope and uncertainty constraints.

I Additional scalar calibration studies

  • The threshold model tests finite-level behavior across a drift breakpoint because every reported threshold lies beyond the neighborhood where the local quadratic condition holds.Its 900,000 retained observations are dependent within ten chains, and the intervals do not assess residual burn-in bias.Source: I Additional scalar calibration studies · pp. 70–71
  • The expectile study uses τ = 0.4 and 0.6 with Student-t1.2 noise, whose infinite second moment makes subtraction before expectation essential.It retains 4,500,000 observations from 100 chains, with uncertainty estimated across independent chain-level tail estimates.Source: I Additional scalar calibration studies · pp. 70–71
  • At γ = 0.001, the smooth-model ratio is 0.698 at y = 1 and 1.016 at y = 3, while the τ = 0.4 expectile ratio at y = 3 is 0.887.The τ = 0.6 expectile ratio is 1.036; the threshold-model interval at the reported setting is much wider, [0.271, 1.738].Source: I Additional scalar calibration studies · p. 71
  • The deterministic nonlinear-flow factor approaches one as thresholds shrink, while the fixed-threshold SGD comparison is an empirical diagnostic of that approximation.The theorem proves the deterministic localization; numerical integration methods agree within 2×10^-8 at validation points.Source: I Additional scalar calibration studies · p. 71, Figure 14 · p. 73

Related papers

Loading 2610.23750v1…