aiqbench analysis
This paper advances theoretical understanding by establishing dimension-independent generalization bounds for nonconvex optimization under heavy-tailed noise, a critical condition often overlooked in standard bounded variance models. By introducing truncation arguments and analyzing both smooth and nonsmooth settings, the work provides rigorous guarantees for popular algorithms like clipped SGD and momentum variants without relying on weak convexity assumptions. These findings are essential for researchers aiming to bridge the gap between empirical training stability and formal generalization theory in realistic ML environments.
Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity
arXiv:2601.19730v2 Announce Type: replace 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 stability-based frameworks to establish dimension-independent generalization bounds of nonconvex optimization under heavy-tailed noise for both smooth and nonsmooth settings. Specifically, we introduce a truncation argument to achieve the generalization error bound based on the algorithmic stability under finite $p$th moment conditions with $p\in(1,2]$. For the smooth case, we apply our framework to derive population gradient norm bounds for several popular stochastic optimization algorithms, including clipped and normalized stochastic gradient descent, as well as their mini-batch and momentum variants. For the nonsmooth case, we establish a population Goldstein stationarity guarantee for online-to-nonconvex conversion methods. It is worth noting that our theory for the nonsmooth setting is established by introducing an on-average gradient stability for the smooth surrogate function, which does not require the additional weak convexity assumption used in existing analysis based on the Moreau envelope.
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 stability-based frameworks to establish dimension-independent generalization bounds of nonconvex optimization under heavy-tailed noise for both smooth and nonsmooth settings. Specifically, we introduce a truncation argument to achieve the generalization error bound based on the algorithmic stability under finite $p$th moment conditions with $p\in(1,2]$. For the smooth case, we apply our framework to derive population gradient norm bounds for several popular stochastic optimization algorithms, including clipped and normalized stochastic gradient descent, as well as their mini-batch and momentum variants. For the nonsmooth case, we establish a population Goldstein stationarity guarantee for online-to-nonconvex conversion methods. It is worth noting that our theory for the nonsmooth setting is established by introducing an on-average gradient stability for the smooth surrogate function, which does not require the additional weak convexity assumption used in existing analysis based on the Moreau envelope.
Machine Learning (cs.LG)
arXiv:2601.19730 [cs.LG]
(or arXiv:2601.19730v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2601.19730 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 288 words
Related coverage
The Convergence Behavior of Adam under Heavy-Tailed Noise
arXiv · Jul 31, 2026
Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise
arXiv · Jul 29, 2026
Tight Complexity of Muon under Heavy-Tailed Noise
arXiv · Oct 14, 2026
Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noise
arXiv · Jun 16, 2026