acceptodds
Withdrawn from ICLR 2027

Exact Tail Laws for Nonlinear SGD with Infinite-Variance Gradients

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 , 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 . 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 for fixed batch size . 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.

Primary area:
learning theory
Keywords:
stochastic gradient descent, tail probability, extreme value theory, heavy tails, uncertainty quantification

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_NoJcOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper asserts that the expected optimization error can be a poor description of an accurate iterate, which is used to motivate the need for tail probabilities. For a sequence generated by stochastic gradient descent with heavy-tailed noise, the main result establishes a distributional limit for strongly convex ("dissipative") and smooth objectives. This result resembles the Levy-stable limits identified in prior works.

Critical strengths

I am unable to identify any critical strengths of the paper that support acceptance.

Critical weaknesses

Several critical errors are present already in the first few paragraphs.

The paper starts with a strong statement that "the expected optimization error can be a poor description of an accurate iterate". This directly conflicts with the results that this manuscript proves; the main result is the error's tail probability. Given that this is the only motivation stated for the results, it is unclear what problem/gap the authors are trying to close.

The paper states its novelty with respect to existing works as identifying "the exact shrinking-threshold tail probability ... including the sharp constant". How does this differ from the cited results, apart from differences in problem settings? What kind of established convergence guarantees and stable-limit behaviors are the authors referring to? It is written as if existing results do not recover tails as in Equation (2), which is by definition an asymptotic tail. Can the authors show why existing results do not suffice to obtain Equation (2)? For example, what are the authors claiming as the distinction with the [1]?

Theorem 2.5 is established assuming a condition on dist(A,0)\mathrm{dist}(A, 0) which is not defined.

The results are very hard to read. For example, Theorem 2.5 states a redudnatn condition on nγn_\gamma: nγγ→∞n_\gamma \gamma \to \infty and nγγ/log⁡(1/γ)→∞n_\gamma \gamma / \log (1/\gamma) \to \infty. It's also unclear whether AA can depend on nn and/or λ\lambda.

[1] Jose Blanchet, Aleksandar Mijatovic, and Wenhao Yang. "Limit theorems for stochastic gradient descent with infinite variance".

Minor comments

  • The x∗x^* is simply described as "the target". It should be defined as the minimizer of mm.

  • The ∼\sim is said to "mean that the ratio tends to one". The authors should specify the limiting variable, e.g., γ→0\gamma \to 0 or n→∞n \to \infty.

  • Equation (2) uses nγn_\gamma which is not defined. It is used in Theorem 2.5 to specify the dependence of nn on γ\gamma with a specific requirement, but this is not clear in Section 1.

  • The statements in Corollaries 2.6 and 2.7 open with "Under Theorem 2.5". It should be "Under the assumptions of Theorem 2.5".

Questions for authors

Please see my comments under "Critical Weaknesses".

Reviewer_rM9MOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the last iterate of constant-stepsize, nonlinear SGD when gradient noise has infinite variance. Specifically, the innovation η=−g(x⋆,ε)\eta = -g(x^\star,\varepsilon) is multivariate regularly varying with tail index t∈(1,2)t \in (1,2). In this setting the expected excess objective is infinite even though most iterates sit near the optimum, so the authors characterize accuracy through tail probabilities instead. The main result (Theorem 2.5) is a first-order tail law with an exact leading constant P(Xnγ/uγ∈A)=Lγ(uγ){νH(A)+o(1)}\mathbb{P} (X_{n_\gamma}/u_\gamma \in A) = L_\gamma(u_\gamma) \{\nu_H(A) + o(1) \} where $ L_\gamma(u) = \frac{\mathbb{P}(|\eta| > u/\gamma)}{\gamma}, \nu_H(A) = \int_0^\infty \mu_\eta{z : e^{-sH}z \in A},ds. $ Here LγL_\gamma is the rate of large shocks. The intuition is ``one big jump'': a single large gradient shock, with direction drawn from the tail measure μη\mu_\eta, is transported by the local Hessian flow e−sHe^{-sH}. The result holds for shrinking thresholds uγ=cγau_\gamma = c\gamma^a with $\frac{t-p}{t} < a < \frac{t-1}{t}, $where p∈(1,t]p \in (1,t] is the available gradient moment. The result holds for shrinking thresholds uγ=cγau_\gamma = c\gamma^a with $\frac{t-p}{t} < a < \frac{t-1}{t}, $where p∈(1,t]p \in (1,t] is the available gradient moment. The assumptions are one-point centered dissipativity (weaker than strong convexity, so nonconvex objectives are allowed), LpL^p gradient growth and increment bounds, and a local quadratic remainder. Under these, the authors prove a vector tail law with vanishing relative error. It covers state-dependent noise and a diverging horizon. Prior work they compare against, notably Wang & Rhee, uses fixed horizons, global Lipschitz conditions, and factorized noise.

In the validation study, all experiments couple nonlinear and linear chains through shared innovations. This lets the total error split into linear, transfer, and constant ratios, with Rtot=RlinRtrR_{\mathrm{tot}} = R_{\mathrm{lin}} R_{\mathrm{tr}}.

Critical strengths

Strength 1. The article gives a sharp, relatively accurate tail law for genuine nonlinear SGD. Most heavy-tailed SGD theory gives convergence rates, stable limits, or high-probability bounds whose constants are not tight. This paper identifies the exact leading constant νH(A)\nu_H(A) for last-iterate tail probabilities, with vanishing relative error. It does so in a setting meaningfully harder than prior one-big-jump results: nonconvex but centered-dissipative objectives, state-dependent noise, a stepsize-dependent memory, and a diverging observation horizon.

Strength 2. The article gives a careful and candid empirical validation. Nonlinear and linear chains share innovations, so the total calibration error factors exactly as $ R_{\mathrm{tot}} = R_{\mathrm{lin}}, R_{\mathrm{tr}}, $ separating the linear single-jump and nonlinear-transfer components, with RconstR_{\mathrm{const}} isolating the finite-sum constant. This shows where any discrepancy comes from rather than just reporting agreement. The design also guards against cherry-picking: threshold exponents and sample sizes are fixed before sampling, uncertainty is handled at the level of independent trajectories, and full counts, seeds, and code are provided. The authors report the cases where the asymptotic constant fails at finite step: roughly 4×4\times error under random sample Hessians at γd=1\gamma d = 1, and deficits at fixed thresholds.

Critical weaknesses

Weakness: The main theorem holds only in a joint limit: thresholds shrink as uγ=cγau_\gamma = c\gamma^a inside the window $\frac{t-p}{t} < a < \frac{t-1}{t}, $ the stepsize goes to zero, and the horizon goes to infinity. It also requires global centered dissipativity (a single basin), fixed dimension, and a tail that comes from the additive innovation at the target. Fixed tolerances, which are what a practitioner actually sets, are covered only for affine population gradients. The paper gives no rate for the relative error, so there is no way to tell when an asymptotic regime has been reached. The paper is honest about all of this. But the practical message, that this constant predicts SGD's rare errors, is backed mostly by diagnostics rather than by theorems in the relevant regime.

Questions for authors

Can the proof be made quantitative, giving an explicit bound on $ \left|\frac{\mathbb{P}(X_{n_\gamma}/u_\gamma \in A)}{L_\gamma(u_\gamma),\nu_H(A)} - 1\right| $ in terms of γ\gamma, aa, pp, and tt? Without such a rate, a user cannot tell whether a given (γ,u)(\gamma, u) is in the asymptotic regime. The experiments (nonmonotone ratios at a=0.2a = 0.2, Rtot=0.698R_{\mathrm{tot}} = 0.698 at y=1y=1) suggest the approach can be slow. A rate, even a crude one, would substantially strengthen the practical claim.

Is the lower bound a>(t−p)/ta > (t-p)/t an artifact of the first-moment coupling, or can you show that the law fails below it? Likewise, what happens at or above a=(t−1)/ta = (t-1)/t, where thresholds approach the central fluctuation scale? Knowing whether the window is necessary would clarify how much of the stated regime is intrinsic.

Do you conjecture that $\mathbb{P}(X_{n_\gamma} \in uA) \sim \frac{\mathbb{P}(|\eta| > u/\gamma)}{\gamma} u^{t}, C^{\mathrm{flow}}_A(u) $ holds for fixed u>0u > 0 and general nonlinear mm? If so, what is the obstacle to proving it? A positive answer would close the main gap between the theory and the regime practitioners care about.

Reviewer_vAdxOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies tail probabilities for the last iterate of constant stepsize SGD with gradient noise with infinite variance. Under appropriate technical assumptions, the paper obtains asymptotically exact probabilities for errors above shrinking thresholds. The paper also derives excess objective tails and extreme quantiles, and provides numerical results on synthetic models.

Critical strengths

The main result provides decreasing relative error bounds for rare event probabilities. It seems that existing results do not imply this conclusion, and this part is novel.

Critical weaknesses
  1. I am somehow sceptical about the broad influence of the paper on the ICLR community. While some of the theoretical results might be interesting, I do not understand if they shed some new light on the empirical properties of heavy-tailed SGD. At the same time, as for the entirely theoretical paper, its technical novelty and theoretical contribution look limited. Many arguments on which the proof is based (linearization, switching to the noise at the optimum, argument of one large jump) already appeared in the literature. Especially close contribution is [1], which is only very briefly cited in the context of the stable Ornstein-Uhlenbeck measure. At the same time, this paper contains many of the outlined technical ideas.

  2. Several writing moments are too heavy or ambiguously written. For example, looking at the main contributions of the paper: neither pp nor aa are defined in this moment. Main text of the paper also contains lot of technical statements and their motivation is not always clearly explained.

References

[1] Bartosz Głowacki, Rafał Kulik, and Philippe Soulier. Convergence of stochastic gradient descent with mini-batching and infinite variance. arXiv:2605.07184, 2026. URL https://arxiv.org/abs/2605.07184v1. Version 1

Questions for authors
  1. Could the authors explain what new understanding of SGD follows from the results of the current paper beyond the existing theory? Why the passage from weak convergence to tail asymptotics should be considered a substantial advance for the ICLR audience? Does it imply some practical meaning for SGD usecases under the heavy tails assumptions?

  2. Could the authors test the theoretical constant at shrinking thresholds in a multidimensional model with state-dependent noise?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.