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

arXiv:2610.07814v1 Announce Type: cross 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-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, we prove a complexity lower bound Omega(kappa^2ellarepsilon^{-2}+kappa^4ellsigma^2arepsilon^{-4}), where kappa=ell/mu is the condition number, sigma^2 is the gradient variance, and arepsilon 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.

Related

• Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients
• Negative Stepsizes Make Gradient-Descent-Ascent Converge
• Gradient Descent's Last Iterate is Often (slightly) Suboptimal

Source: arXiv cs.LG | 2026-10-07