Exact Tail Laws for Nonlinear SGD with Infinite-Variance Gradients
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 t∈(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 b1−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.
Related
- Breaking the Shot-Noise Barrier: Cached Recycled Variance-Reduced Gradients for Quantum Optimization
- An Exact Tail Condition for the Largest Error in Estimating a Rank-One Direction
- Variance and volatility swap valuation with nonlinear liquidity-feedback stochastic volatility and regime switching
- Unbiased Gradients, Moving Stability Boundaries: Exact Mini-Batch Geometry in Linear Self-Attention
- GRADSOLVE: fast exact gradients for ODE ensembles on GPUs
BibTeX
@misc{li2026exact,
title = {{Exact Tail Laws for Nonlinear SGD with Infinite-Variance Gradients}},
author = {Xiaoli Li and Qianqian Lei and Ziyang Wei and Wei Biao Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23750},
eprint = {2610.23750},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23750},
}
RIS
TY - UNPB
TI - Exact Tail Laws for Nonlinear SGD with Infinite-Variance Gradients
AU - Xiaoli Li
AU - Qianqian Lei
AU - Ziyang Wei
AU - Wei Biao Wu
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23750
UR - https://arxiv.org/abs/2610.23750
AB - 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∈(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.
ER -