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

Key points

• 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.1
• For $\ell$-smooth games with an inner $μ$-PL inequality, we prove a complexity lower bound $Ω(κ^2\ell\varepsilon^{-2}+κ^4\ellσ^2\varepsilon^{-4})$, where $κ=\ell/μ$ is the condition number, $σ^2$ is the gradient variance, and $\varepsilon$ measures the outer gradient norm.1
• This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22').1
• In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as $o(κ^2)$.1

Sources (1)

• [1]Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 6, 06:08 AM

  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.

Extractive summary: sentences quoted from the sources.