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 $\ell$-smooth games with an inner $\mu$-PŁ inequality, we prove a complexity lower bound $\Omega ({\kappa }^2\ell {\epsilon }^{-2}+{\kappa }^4\ell {\sigma }^2{\epsilon }^{-4})$, where $\kappa =\ell /\mu$ is the condition number, ${\sigma }^2$ is the gradient variance, and $\epsilon$ 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({\kappa }^2)$. Our negative results highlight the fundamental limitation of SGDA in NC-PŁ games, and justify the development of alternative methods.