Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise

Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:17344-17370, 2026.

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$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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-chen26ev, title = {Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise}, author = {Chen, Hongxu and Wei, Ke and Yuan, Xiaoming and Luo, Luo}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {17344--17370}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/chen26ev/chen26ev.pdf}, url = {https://proceedings.mlr.press/v306/chen26ev.html}, 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$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.} }
Endnote
%0 Conference Paper %T Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise %A Hongxu Chen %A Ke Wei %A Xiaoming Yuan %A Luo Luo %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-chen26ev %I PMLR %P 17344--17370 %U https://proceedings.mlr.press/v306/chen26ev.html %V 306 %X 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.
APA
Chen, H., Wei, K., Yuan, X. & Luo, L.. (2026). Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:17344-17370 Available from https://proceedings.mlr.press/v306/chen26ev.html.

Related Material