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 ℓ-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.