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

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 $\mu$-PL inequality and fixed initial-gap budgets, we prove a complexity lower bound $\Omega ({\kappa }^2\ell {\text{eps}}^{-2}+{\kappa }^4\ell {\sigma }^2{\text{eps}}^{-4})$, where $\kappa =\ell /\mu$ is the condition number, ${\sigma }^2$ is the gradient variance, and $\text{eps}$ 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-PL games, and justify the development of alternative methods.