Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games

Junsoo Ha

stat.MLOct 6, 2026

Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games

Authors: Junsoo Ha

Abstract

How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-PL (NC-PL) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For $\ell$ -smooth games with an inner $μ$ -PL inequality, we prove a complexity lower bound $Ω(κ^2\ell\varepsilon^{-2}+κ^4\ellσ^2\varepsilon^{-4})$ , where $κ=\ell/μ$ is the condition number, $σ^2$ is the gradient variance, and $\varepsilon$ measures the outer gradient norm. This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22'). In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as $o(κ^2)$ . Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.

Figures & tables

Algorithm	Citation	Feedback	Complexity / obstruction
SGDA Alt	Yang et al. (2022)	Bounded $\sigma^{2}$	$O(\kappa^{2}\ell\varepsilon^{-2}+\kappa^{4}\ell\sigma^{2}\varepsilon^{-4})$
SGDA Sim	Theorem A.1	Bounded $\sigma^{2}$	$O(\kappa^{2}\ell\varepsilon^{-2}+\kappa^{4}\ell\sigma^{2}\varepsilon^{-4})$
Smoothed-AGDA	Yang et al. (2022)	Bounded $\sigma^{2}$	$\widetilde{O}({\color[rgb]{0,0.3984,1}\bm{\kappa}}\ell\varepsilon^{-2}+{\color[rgb]{0,0.3984,1}\bm{\kappa^{2}}}\ell\sigma^{2}\varepsilon^{-4})$
SPIDER-GDA	Chen et al. (2022)	Finite-sum	$O(n+\sqrt{n}\kappa^{2}\ell\varepsilon^{-2})$
SGDA-RR	Cho and Yun (2023)	Finite-sum	$O(n\kappa^{2}\ell\varepsilon^{-2}+\sqrt{n}\kappa^{3}\ell\sigma\varepsilon^{-3})$
MSGDA	Huang et al. (2025)	Smooth samples	$\widetilde{O}((\kappa^{3}\ell\sigma+\kappa^{4}\sigma^{3}){\color[rgb]{0,0.3984,1}\bm{\varepsilon^{-3}}})$

Table 1: Upper and lower bounds in NC-PŁ games. Our lower bounds match SGDA’s upper bounds after optimizing fixed timescale ratios and predetermined nonincreasing step sizes. With exact gradients, Theorem 6.3 rules out uniform convergence for

\rho=o(\kappa^{2})

;

\Omega(1)

denotes nonvanishing stationarity error. MSGDA and AdaMSGDA use

0<\varepsilon\leq\sigma

\dagger

AdaMSGDA measures the average expected squared norm of

A_{t}^{-1}\nabla\Phi(x_{t})

, where

A_{t}

is its primal preconditioner.

\ddagger

HCMM-2 shows only the variance-dependent cost for

\mathbb{E}\left\lVert\nabla\Phi\right\rVert\leq\varepsilon

, with Hessian variance at most

\sigma^{2}

. Appendix F gives the complete bounds and assumptions.

Panel of Figure 1 — Figure 1: The competing bounds in $f_{\mathrm{stable}}$ (schematic). Let $m$ count the initial large steps and $S=\sum_{t=m}^{T-2}\eta_{t}$ . (a) The corridor keeps gradient magnitude $G$ at $u_{m},\ldots,u_{T-1}$ . (b) Gradient noise creates inner gap $\Phi_{\sigma}(v_{t})-g_{\sigma}(v_{t},y_{t})$ . (c) Pink bands show contributions to $t^{-1}\sum_{i<t}\|\nabla\Phi_{\sigma}(v_{i})\|^{2}$ ; the initial increases are omitted. The dashed level is the bound’s scale $\kappa^{4}\ell\sigma^{2}S/(\rho T)$ for $S\geq C\rho/(\ell\kappa)$ .

Explore similar work

Negative Stepsizes Make Gradient-Descent-Ascent Converge
May 2, 2025Henry Shugart, Jason M. AltschulerLearning Rate Scheduling Optimization Convergence Analysis
UPenn
Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
Sep 24, 2026Wei Biao WuNonconvex Stochastic Optimization Stochastic Optimization Convergence
Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
Apr 17, 2026Arda Fazla, Ege C. Kaya, Antesh Upadhyay +1Stochastic Optimization Nonconvex Stochastic Optimization
School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

May 2, 2025, math.OCJ/K move · Enter open · S save

Negative Stepsizes Make Gradient-Descent-Ascent Converge

Henry Shugart, Jason M. Altschuler

UPenn

Learning Rate Scheduling Optimization Convergence Analysis Min-Max Optimization Gradient Descent Dynamics

Open paper AskPDF arXiv

Efficient computation of min-max problems is a central question in optimization, learning, games, and control. Arguably the most natural algorithm is gradient-descent-ascent (GDA). However, since the 1970s, conventional wisdom has argued that GDA fails to converge even on simple problems. This failure spurred an extensive literature on modifying GDA with additional building blocks such as extragradients, optimism, momentum, anchoring, etc. In contrast, we show that GDA converges in its original form by simply using a judicious choice of stepsizes. The key innovation is the proposal of unconventional stepsize schedules (dubbed slingshot stepsize schedules) that are time-varying, asymmetric, and periodically negative. We show that all three properties are necessary for convergence, and that altogether this enables GDA to converge on the classical counterexamples (e.g., unconstrained convex-concave problems). The core algorithmic intuition is that although negative stepsizes make backward progress, they de-synchronize the min and max variables (overcoming the cycling issue of GDA), and lead to a slingshot phenomenon in which the forward progress in the other iterations is overwhelmingly larger. This results in fast overall convergence. Geometrically, the slingshot dynamics leverage the non-reversibility of gradient flow: positive/negative steps cancel to first order, yielding a second-order net movement in a new direction that leads to convergence and is otherwise impossible for GDA to move in. We interpret this as a second-order finite-differencing algorithm and show that, intriguingly, it approximately implements consensus optimization, an empirically popular algorithm for min-max problems involving deep neural networks (e.g., training GANs).

Abstract

Explore similar work

Negative Stepsizes Make Gradient-Descent-Ascent Converge

Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance