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

arXiv: https://arxiv.org/abs/2610.07814 · HTML: https://mlsanity.com/paper/2610.07814/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Builds on (most cited first, 13 of 13)

- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Generative Adversarial Networks](https://mlsanity.com/paper/1406.2661/) (2014)
- [Robust LLM Alignment via Distributionally Robust Direct Preference Optimization](https://mlsanity.com/paper/2502.01930/) (2025)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Generative Adversarial Reasoner: Enhancing LLM Reasoning with Adversarial Reinforcement Learning](https://mlsanity.com/paper/2512.16917/) (2025)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [High-probability complexity guarantees for nonconvex minimax problems](https://mlsanity.com/paper/2405.14130/) (2024)
- [Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum](https://mlsanity.com/paper/2406.13041/) (2024)
- [Lower Bounds for Nonconvex-PL Minimax Optimization](https://mlsanity.com/paper/2608.26799/) (2026)
- [PL conditions do not guarantee convergence of gradient descent-ascent dynamics](https://mlsanity.com/paper/2602.16517/) (2026)
- [The Complexity of Min-Max Optimization for Quadratic Polynomials](https://mlsanity.com/paper/2606.17000/) (2026)

## Abstract (arXiv)

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 ℓ-smooth games with an inner μ-PL inequality, we prove a complexity lower bound Omega(kappa2ℓvarepsilon-2+kappa4ℓσ2varepsilon-4), where kappa=ℓ/μ 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(kappa2). Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.