Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise
Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo · 2026
Read Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise by Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19730.txt.
Introduction
Hongxu Chen, Ke Wei, Xiaoming Yuan, and Luo Luo study how machine learning models train under messy noise. In practice the random noise in gradient estimates has heavy tails, meaning extreme values occur often. That picture fits real training better than the usual bounded-noise assumption. Most theory under heavy tails covers how fast training converges.
Far less is known about generalisation: how well the trained model does on new data. The authors analyse stability and generalisation bounds for nonconvex optimization with heavy-tailed noise. Nonconvex problems are the norm in deep learning. Bounds like these explain when training will transfer to unseen examples. The work closes a gap between optimisation theory and learning practice.
Catalog record
| CREATOR | Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19730
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo Abstract 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 p th centered moment with p ∈ ( 1 , 2 ] 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. 1 Introduction Over the past decades, machine learning develops very rapidly and has achieved remarkable progress in many areas including computer vision [ 73 , 72 ] , natural language processing [ 18 , 11 ] , and reinforcement learning [ 71 , 26 ] . In many machine learning applications, the task of training the model can be formulated as an optimization problem, where one seeks parameters that yield strong generalization performance. A canonical formulation is to find the parameter by minimizing the population risk as follows \displaystyle\min_{x\in\mathbb{R}^{d}}F(x):=\mathbb{E}_{\xi\sim\mathcal{D}}\bigl[f(x;\xi)\bigr], (1) where \xi denotes data that follows a distribution \mathcal{D} and f(x;\xi) is the corresponding loss function. In practice, the explicit expression of the objective in formulation ( 1 ) is typically unavailable, but can be approximated via a training dataset S=\{\xi_{1},\dots,\xi_{n}\} of n i.i.d. samples drawn from {\mathcal{D}} . This yields the empirical risk minimization problem \displaystyle\min_{x\in\mathbb{R}^{d}}F_{S}(x):=\frac{1}{n}\sum_{i=1}^{n}f(x;\xi_{i}). (2) Since the training datasets often contains a large number of samples, it is prohibitively expensive to compute the full gradient of ( 2 ). Thus the stochastic optimization methods that exploit the finite-sum structure are natural alternatives. A representative one is stochastic gradient descent (SGD), which at each iteration uses the gradient of a single randomly sampled data point to approximate the full gradient. Its low per-iteration cost and simple update rule make it effective for training large models. The analysis of SGD can be traced back to Robbins and Monro 1951 . For convex problems, convergence can be guaranteed by classical results [ 58 , 51 ] . For nonconvex problems, analyses typically rely on the magnitude of gradients [ 24 , 7 ] . Moreover, many variants of SGD, including momentum methods [ 57 , 52 , 70 , 44 ] , variance reduction [ 33 , 82 , 16 , 2 , 75 , 64 , 4 , 36 , 20 , 43 ] , and adaptive learning rates [ 19 , 34 , 79 , 61 , 47 , 32 ] , have improved theoretical bounds or empirical performance. In real-world applications, we are more interested in the generalization measured on the population risk ( 1 ), while optimization algorithms focus on the empirical risk ( 2 ). We use notation A(S) to present the output of algorithm A to solving problem ( 2 ) with training dataset S . For convex objective, the generalization error is commonly measured by the difference of function value, i.e., F(A(S))-F_{S}(A(S)) . Specifically, Bousquet and Elisseeff 2002 introduced the notion of uniform stability and established a approach for the analysis of generalization bounds from this perspective. In subsequent work, Hardt et al. 2016 analyzed stability and generalization of SGD under the assumptions of Lipschitz and smoothness, providing theoretical explanation for the early stopping. The smoothness assumption is removed by Lei and Ying 2020 . Later, Feldman and Vondrak 2019 strengthened the stability-based bounds from expectation to near-optimal high-probability guarantees. For nonconvex objective, the generalization error is usually measured by the gradient discrepancy, i.e., \|\nabla F(A(S))-\nabla F_{S}(A(S))\| . Specifically, Lei 2023 introduced the notion of uniform stability with respect to the gradient, yielding to a general framework for the generalization analysis for nonconvex stochastic optimization algorithms. In addition, several recent works analyzed the stability and generalization of problems with minimax formulations [ 40 , 83 ] and distributed settings [ 17 , 37 , 84 , 80 ] . However, the existing results typically rely on the standard bounded-variance assumption. Recent empirical evidence suggests that, in the popular tasks such as deep neural network training [ 66 , 81 , 3 , 6 ] and reinforcement learning [ 23 ] , the noise of stochastic gradients follows heavy-tailed distribution. Simsekli et al. 2019 modeled this phenomenon using the \alpha -stable distribution and analyzed the dynamics of SGD through a Lévy-driven SDE. In optimization theory, a common way to formalize the heavy-tailed noise is the assumption of bounded p th centered moment, i.e., there exist p\in(1,2] and \sigma_{p}>0 such that for all x\in{\mathbb{R}}^{d} , it holds \displaystyle\mathbb{E}_{\xi\sim\mathcal{D}}\left[\left\|\nabla f(x;\xi)-\nabla F(x)\right\|^{p}\right]\leq\sigma_{p}^{p}. ( p -BCM) Under the assumption of p -BCM, Zhang et al. 2020 established the in-expectation convergence guarantees for clipped SGD. Cutkosky and Mehta 2021 derived the high-probability convergence guarantees accordingly. Nguyen et al. 2023 and Liu et al. 2023 further improved the high-probability analysis and developed variance-reduced clipped SGD methods [ 46 ] . The recent works show that normalized SGD also guarantees the convergence of stochastic nonconvex optimization under the p -BCM assumption. Specifically, Hübler et al. 2025 show that normalized SGD with momentum or large batch size can achieve the optimal convergence rates like the counterparts of clipped SGD. In addition, Sun et al. 2025b combines clipping and normalization with momentum to establish the sharper convergence rates by assuming the objective has Lipschitz continuous Hessian. He et al. 2025 further analyzed the acceleration by the high-order smoothness. Recently, distributed stochastic optimization under heavy-tailed noise has also been investigated [ 74 , 78 , 67 ] . The understanding of generalization analysis under the p -BCM assumption remains limited. One line of works by Raj et al. 2023a , Raj et al. 2023b established the algorithmic stability results for SGD under the general loss functions, while their analysis relies on continuous-time SDE arguments and Wasserstein distances. Recently, Sun et al. 2025c analyzed the generalization of normalized SGD under the unbounded noise and a weak gradient Lipschitz condition, which is different from commonly used p -BCM assumption for heavy-tailed noise. Table 1: Comparison of generalization errors for nonconvex problems measured by \|\nabla F(A(S))-\nabla F_{S}(A(S))\| . Here \epsilon denotes the algorithmic stability parameter. Our bound holds for p\in(1,2] and reduces to the result of Lei 2023 when p=2 . Reference Bounds Assumption Mei et al. 2018 O\left(\sqrt{{d\log(n)}/{n}}\right) sub-Gaussian Lei 2023 O(\epsilon+n^{-\frac{1}{2}}) bounded variance Theorem 4.2 O(\epsilon+n^{-\frac{p-1}{p}}) p -BCM In this paper, we develop a systematic stability-based generalization analysis for stochastic nonconvex optimization under the p -BCM condition. We apply our framework to study two representative approaches for handling heavy-tailed noise, clipped SGD and normalized SGD, as well as their mini-batch and momentum variants. The main contributions of this paper are summarized as follows. • We develop, to the best of our knowledge, the first