Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL 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 $\mathrm{\ell }$-smooth games with an inner $\mu$-PL inequality, we prove a complexity lower bound $\mathrm{\Omega }({\kappa }^2\mathrm{\ell }{\epsilon }^{-2}+{\kappa }^4\mathrm{\ell }{\sigma }^2{\epsilon }^{-4})$, where $\kappa =\mathrm{\ell }\mathrm{/}\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-PL games, and justify the development of alternative methods.