Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise

The empirical evidence indicates that stochastic optimization with heavy-tailed gradient noise is more appropriate to characterize the training of machine learning models than that with standard bounded gradient variance noise. Most existing works on this phenomenon focus on the convergence of optimization errors, while the analysis for generalization bounds under the heavy-tailed gradient noise remains limited. In this paper, we develop a general framework for establishing generalization bounds under heavy-tailed noise. Specifically, we introduce a truncation argument to achieve the generalization error bound based on the algorithmic stability under the assumption of bounded $p$th centered moment with $p\in(1,2]$. Building on this framework, we further provide the stability and generalization analysis for several popular stochastic algorithms under heavy-tailed noise, including clipped and normalized stochastic gradient descent, as well as their mini-batch and momentum variants.

When machine learning models are trained on large datasets, they are often updated using only a small random part of the data at each step. This makes training efficient, but it also makes the update direction noisy. Recent evidence suggests that this noise may be heavy-tailed, meaning that large deviations occur more often than standard theory assumes. Many studies have examined whether algorithms can still optimize the training objective under heavy-tailed noise. However, much less is known about whether the guarantees obtained from the training data can still reflect the behavior on the underlying data distribution. We develop a general framework for proving such generalization guarantees. Our approach combines algorithmic stability, which measures sensitivity to changing one training example, with a truncation technique that controls large noisy gradients. We apply the framework to clipped and normalized SGD, including mini-batch and momentum variants. Our results help explain when these methods can remain stable and generalize under heavy-tailed noise, providing theoretical guidance for analyzing and designing stochastic training algorithms.