aiqbench analysis
This research establishes the first convergence guarantees for vanilla Stochastic Gradient Descent Ascent (SGDA) under heavy-tailed noise in nonconvex settings, challenging the prevailing necessity of gradient clipping or normalization. By introducing new clipping-free algorithms like Stoc-TRGDAM and Stoc-TRGDmax, the study provides optimal accuracy dependence for regularized min-max problems without relying on standard variance-bounded assumptions. These theoretical advances offer a more robust foundation for training generative models and adversarial networks where gradient distributions often exhibit heavy tails.
The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization
arXiv:2609.06064v1 Announce Type: cross 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\in(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.
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\in(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.
Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)
arXiv:2609.06064 [math.OC]
(or arXiv:2609.06064v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2609.06064 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
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 · 274 words
Related coverage
Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity
arXiv · Oct 6, 2026
Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
arXiv · Sep 22, 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