The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization
Abstract
Stochastic min-max optimization has attracted increasing attention due to its applications in modern machine learning, while existing theoretical studies mainly rely on the bounded variance assumption for stochastic gradients. Under heavy-tailed noise, where stochastic gradients only possess a finite p-th moment for p∈(1,2], gradient clipping or normalization is commonly believed to be necessary to guarantee convergence. In this work, we revisit stochastic min-max optimization under heavy-tailed noise and provide a comprehensive theoretical study of stochastic gradient descent ascent (SGDA). We first show that vanilla SGDA, without any modification to its update rule, can converge under heavy-tailed noise in both nonconvex-strongly-concave (NC-SC) and nonconvex-concave (NC-C) settings, establishing the first convergence guarantees for SGDA in these regimes. Beyond unregularized problems, we further investigate regularized stochastic min-max optimization, where directly incorporating gradient normalization into proximal updates is nontrivial due to the incompatibility between normalization and proximal structures. We overcome this difficulty by developing new clipping-free algorithms, i.e., Stoc-TRGDAM and Stoc-TRGDmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
Related
- Recursive Gradient Retraction Methods for Stochastic Nonconvex Optimization on Stiefel Manifolds
- Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PŁ Min-Max Games
- Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
- A Proximal Gradient Method for Nonconvex Nonsmooth Optimization with Applications
- Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
BibTeX
@misc{zhu2026role,
title = {{The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization}},
author = {Tianxi Zhu and Yi Xu and Xiangyang Ji},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06064},
eprint = {2609.06064},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06064},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization
AU - Tianxi Zhu
AU - Yi Xu
AU - Xiangyang Ji
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.06064
UR - https://arxiv.org/abs/2609.06064
AB - Stochastic min-max optimization has attracted increasing attention due to its applications in modern machine learning, while existing theoretical studies mainly rely on the bounded variance assumption for stochastic gradients. Under heavy-tailed noise, where stochastic gradients only possess a finite p-th moment for p∈(1,2], gradient clipping or normalization is commonly believed to be necessary to guarantee convergence. In this work, we revisit stochastic min-max optimization under heavy-tailed noise and provide a comprehensive theoretical study of stochastic gradient descent ascent (SGDA). We first show that vanilla SGDA, without any modification to its update rule, can converge under heavy-tailed noise in both nonconvex-strongly-concave (NC-SC) and nonconvex-concave (NC-C) settings, establishing the first convergence guarantees for SGDA in these regimes. Beyond unregularized problems, we further investigate regularized stochastic min-max optimization, where directly incorporating gradient normalization into proximal updates is nontrivial due to the incompatibility between normalization and proximal structures. We overcome this difficulty by developing new clipping-free algorithms, i.e., Stoc-TRGDAM and Stoc-TRGDmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
ER -