Stochastic gradient descent (SGD) is usually analyzed under the assumption that gradient noise has finite variance. But in many modern problems, especially with heavy-tailed data or losses, that assumption fails. The authors study constant-stepsize SGD where the gradient noise is regularly varying with index t in (1,2), meaning the variance is infinite. In this regime, the expected excess objective can be infinite even when most iterates are close to the optimum, so the mean is not a reliable measure of performance.
Instead, the paper derives exact first-order tail probabilities for the last iterate. The key finding is that, at the tail, the dominant event is a single large gradient shock that propagates through the local curvature of the objective. This same mechanism appears in the central stable Ornstein-Uhlenbeck limit, and the authors prove that the tail approximation is relatively accurate at shrinking tolerances above the central scale. The result holds for state-dependent noise and growing observation horizons, with a nonempty admissible window for every available gradient moment p>1.
From the tail law, the authors obtain explicit formulas for projection tails, excess-objective tails, and extreme quantiles. A notable consequence is a factor b^{1-t} for fixed batch size b, showing how batching changes the tail behavior. For affine population gradients, a sharper comparison extends the same law to fixed tolerances, even with random sample Hessians. Simulations in dimensions one through one hundred examine the calibration of these approximations, including batch effects and the error introduced by random curvature.