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

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-PŁ (NC-PŁ) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For ℓ-smooth games with an inner μ-PŁ inequality, we prove a complexity lower bound Ω(κ²ℓε⁻²+κ⁴ℓσ²ε⁻⁴), where κ=ℓ/μ is the condition number, σ² is the gradient variance, and ε 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(κ²). Our negative results highlight the fundamental limitation of SGDA in NC-PŁ games, and justify the development of alternative methods.

Riemannian ascent--descent for nonconvex nonconcave minimax landscapes: convergence to basin saddle points and applications to distributionally robust optimization
Rishabh Dixit, Pranav Upadrashta, Alex Cloninger
arXiv12 Sep 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
PL conditions do not guarantee convergence of gradient descent-ascent dynamics
Jean-Christophe Mourrat
HAL4 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlHAL
Local Algebraic Stability of Wasserstein Gradient Descent-Ascent and Mean Field Langevin Dynamics without Spectral Gap
Jing An, Lihan Wang
arXiv26 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Optimisation & controlarXiv
A Stochastic Riemannian Alternating Descent Ascent Method for Nonsmooth Composite Expectation Optimization on Riemannian Manifolds
Meng Xu, Bo Jiang, Ya-Feng Liu +1
arXiv3 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
Neil Walton
arXiv13 Oct 2026PreprintCC BY 4.0Full textOptimisation & control ProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{ha2026stochastic,
  title = {{Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PŁ Min-Max Games}},
  author = {Junsoo Ha},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.07814},
  eprint = {2610.07814},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.07814},
}

RIS

TY  - UNPB
TI  - Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PŁ Min-Max Games
AU  - Junsoo Ha
PY  - 2026
DA  - 2026/10/09
PB  - arXiv
DO  - 10.48550/arxiv.2610.07814
UR  - https://arxiv.org/abs/2610.07814
AB  - 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-PŁ (NC-PŁ) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For ℓ-smooth games with an inner μ-PŁ inequality, we prove a complexity lower bound Ω(κ^2ℓε^−2+κ^4ℓσ^2ε^−4), where κ=ℓ/μ is the condition number, σ^2 is the gradient variance, and ε 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-PŁ games, and justify the development of alternative methods.
ER  -

Abstract

Related

Cite