High-Probability Guarantees for SGD under eta-Heavy-Tailed Gradient Noise

arXiv:2609.32195v1 Announce Type: cross Abstract: Stochastic gradient descent (SGD) is widely used to train machine learning models, but subsampling the training data introduces noise into its updates. The strength and applicability of high-probability guarantees therefore depend critically on how the tails of gradient noise are modeled. Reports of heavy-tailed gradient noise in deep learning motivate relaxing the bounded-noise and sub-Gaussian assumptions commonly used in high-probability analyses of SGD. We use Young functions from Orlicz space theory to describe noise tails in a common framework. We model SGD gradient noise by adopting a Young function that preserves the finiteness of all polynomial moments while allowing tails heavier than sub-Weibull, including lognormal distributions. The resulting class is called eta-heavy-tailed, with eta controlling the tail heaviness. We establish concentration inequalities for eta-heavy-tailed noise and combine them with a uniform bound on the difference between empirical and population gradients along the SGD trajectory to obtain high-probability bounds on optimization and population-risk stationarity for smooth nonconvex losses under trajectory assumptions. The bounds are not restricted to a particular learning-rate decay rule and make explicit the effects of noise tails and learning-rate schedules. Under the Polyak-{L}ojasiewicz condition, we bound the risk at the last iterate. We also analyze SGD with gradient clipping under the eta-heavy-tailed noise model.

Source: arXiv cs.LG | 2026-09-29