The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization

Tianxi Zhu; Yi Xu; Xiangyang Ji

math.OCSep 5, 2026

The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization

Authors: Tianxi Zhu, Yi Xu, Xiangyang Ji

Organizations: School of Control Science and Engineering, Dalian University of Technology · Department of Automation, Tsinghua University

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.

Figures & tables

NC-C.	Reg.	Metric	( $\mathbb{E}$ , $\mathbb{P}$ )	$\#\textsc{Grad}(\epsilon,2L)$
SGDA ${}_{\text{\tiny Clip}}$ [ 22 ]	( $\mathbb{R}^{d}$ , $\delta_{\mathcal{Y}}$ )	$\frac{1}{T}\sum_{t=1}^{T}\\|\nabla\Phi_{1/2L}(\mathbf{x}_{t})\\|^{2}$	( ✓ , ✓ )	$\mathcal{O}{\left(\frac{(\Delta_{1}+\widehat{\delta}_{1})L^{\frac{2p-1}{p-1}}D_{\mathcal{Y}}^{\frac{p}{p-1}}(G^{2}\sigma^{\frac{p}{p-1}}+\sigma^{\frac{p^{2}}{p-1}})}{\epsilon^{\frac{6p-4}{p-1}}}\right)}$
SGDA (Theorem 3.6 )	( $\delta_{\mathcal{X}}$ , $h$ )	${\left(\frac{1}{T}\sum_{t=1}^{T}\\|\nabla\Phi_{1/2L}(\mathbf{x}_{t})\\|^{2}\right)}^{\nicefrac{{p}}{{2}}}$	( ✓ , ✗ )	$\mathcal{O}{\left(\frac{\Delta_{1}L^{\frac{2p-1}{p-1}}D_{\mathcal{Y}}^{\frac{p}{p-1}}(G^{2}\sigma^{\frac{p}{p-1}}\vee{\color[rgb]{0,0,1}\sigma^{\frac{3p-2}{p-1}}})}{\epsilon^{\frac{6p-4}{p-1}}}+{\color[rgb]{0,0,1}\frac{L\widehat{\delta}_{1}}{\epsilon^{2}}}\right)}$

Table 1: Comparison of the results of vanilla SGDA in this paper and SGDA

{}_{\text{\tiny Clip}}

in [ 22 ] using gradient clipping. “

(a,b)

” in the “Reg.” column denotes the regularizer

a

for

\mathbf{x}

and the regularizer

b

for

\mathbf{y}

. “Metric” denotes the convergence metric, “

\mathbb{E}

” denotes convergence in expectation, and “

\mathbb{P}

” denotes convergence with high probability. For the gradient complexity, We note that although the dependence on

\epsilon

is the same for both methods, our dependence on

\sigma

and

\widehat{\delta}_{1}

is tighter.

\displaystyle\begin{bmatrix}\mathbf{m}_{\mathbf{x},t}\\ \mathbf{m}_{\mathbf{y},t}\end{bmatrix}=\beta\begin{bmatrix}\mathbf{m}_{\mathbf{x},{t-1}}\\ \mathbf{m}_{\mathbf{y},{t-1}}\end{bmatrix}+(1-\beta)\begin{bmatrix}\nabla_{\mathbf{x}}f(\mathbf{x}_{t},\mathbf{y}_{t},\xi_{t})\\ \nabla_{\mathbf{y}}f(\mathbf{x}_{t},\mathbf{y}_{t},\xi_{t})\end{bmatrix}

(4.3)

Algorithm 2 Stoc-TRGDA with Momentumn ( Stoc-TRGDAM )

Methods	Settings	Complexity	Regularized	Single loop	No Clip
SGDA ${}_{\text{\footnotesize Clip}}$ [ 22 ]	NC-PL	$\mathcal{O}(\kappa^{\frac{3p-2}{p-1}}\epsilon^{-\frac{3p-2}{p-1}})$	✗	✓	( ✗ , ✗ )
N 2 SBA [ 36 ]	NC-SC	$\widetilde{\mathcal{O}}(\kappa^{\frac{2p-1}{p-1}}\epsilon^{-\frac{3p-2}{p-1}})$	✗	✗	( ✓ , ✗ )
Fed-NSGDA-M [ 59 ]	NC-PL	$\mathcal{O}(\kappa^{\frac{2p}{p-1}}\epsilon^{-\frac{2p}{p-1}})$	✗	✓	( ✓ , ✓ )
Stoc-TRGDAM ( Ours )	NC-SC	$\mathcal{O}(\kappa^{\frac{3p-2}{p-1}}\epsilon^{-\frac{3p-2}{p-1}})$	✓	✓	( ✓ , ✓ )
Stoc-TRGDAmax ( Ours )	NC-SC	$\widetilde{\mathcal{O}}(\kappa^{\frac{2p-1}{p-1}}\epsilon^{-\frac{3p-2}{p-1}})$	✓	✗	( ✓ , ✓ )

Table 2: Summary of our method and previous methods on stochastic minimax optimization under heavy-tailed noise in NC-SC or NC-PL setting. The notation

(\cdot,\cdot)

in the “No clip” column indicates whether the corresponding method employs gradient clipping for

\mathbf{x}

and

\mathbf{y}

, respectively.

Min-Max Optimization

Min-max optimization studies algorithms for objectives where one decision-maker minimizes loss while an adversary or opponent maximizes it.

See all 38 papers

Jul 9, 2026

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

Stochastic gradient descent (SGD) is a cornerstone of modern optimization. While its performance under heavy-tailed noise is often addressed through specialized modifications such as gradient clipping or normalization, we investigate a more fundamental question: how does vanilla SGD, particularly with momentum, perform in the presence of heavy-tailed noise? In this paper, we refine existing convergence results for vanilla SGD and, more importantly, provide the first comprehensive convergence analysis of vanilla SGD with momentum for strongly convex, convex, and nonconvex objectives, without employing any gradient control mechanisms. Our results demonstrate that the obtained convergence rates are inferior to the optimal rates achieved by clipped or normalized variants of SGD, thereby revealing inherent limitations of vanilla methods under heavy-tailed noise. The theoretical findings are supported by experiments on synthetic functions.

Ryusei Yamada, Naoki Sato, Hideaki Iiduka

Meiji University, Japan

Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

May 30, 2026

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise

Many stochastic gradient methods are believed not to converge when the noise in stochastic gradients has only a finite

p

-th moment for

p\in\left(1,2\right)

, a setting known as the heavy-tailed noise assumption. However, some recent studies have found that Stochastic Gradient Descent (

\textsf{SGD}

), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for Stochastic Mirror Descent (

\textsf{SMD}

) and Accelerated Stochastic Mirror Descent (

\textsf{ASMD}

) in convex optimization, and for

\textsf{SGD}

and Stochastic Gradient Descent with Momentum (

\textsf{SGDM}

) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed stochastic optimization, opening a new route to understanding first-order stochastic gradient methods.

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

Sep 11, 2026

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness

Classical convergence guarantees for stochastic gradient methods typically assume Lipschitz-smooth objectives and finite-variance gradient noise, both frequently violated in practice. In contrast, we study nonconvex stochastic optimization under the joint relaxation of these assumptions: objectives with

(L,s)

-Hölder continuous gradients,

s\in(0,1]

, and gradient noise satisfying only a bounded

α

-th moment condition for

α\in(1,2]

. We establish three convergence results. Firstly, that standard SGD converges at rate

O(T^{-s/(1+s)})

whenever

α\ge1+s

, extending the classical nonconvex SGD rate to heavy-tailed noise and Hölder smoothness simultaneously. Secondly, we analyze

δ

-regularized gradient clipping (

δ

-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of

O(T^{-2s(α-1)/[(1+s)(2α-1)]})

under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for

α\ge1+s

while in the very heavy-tailed regime

α<1+s

, it has a convergence rate

O(T^{-2s(α-1)/[(α-1)+s(2α-1)]})

--- the first convergence guarantee in this regime for any stochastic gradient based method.

Misbah Uz Zaman, Anirbit Mukherjee

Department of Mathematics and Statistics Indian Institute of Science Education and Research Kolkata · Department of Computer Science The University of Manchester

Gradient Clipping Nonconvex Stochastic Optimization Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

Abstract

Min-Max Optimization

Explore similar work

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness