Stochastic gradient methods fall short on certain nonconvex games

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

Computer Science and Game TheoryMachine Learning

Summary

This paper studies a popular approach called stochastic gradient descent ascent (SGDA) used to solve problems where two players compete with complex strategies. The authors found that SGDA has fundamental limits in solving a class of these problems, meaning it can be inefficient or even fail. They proved precise mathematical bounds showing how hard the problem is for SGDA and showed that other methods can be better. This helps explain when and why simple tuning of SGDA won’t solve these problems well.

What this means in practice

  • For machine learning engineers: Avoid using fixed timescale SGDA methods in nonconvex min-max problems where PL conditions hold, as these may fail or be inefficient.
  • For optimization algorithm designers: Design alternative algorithms to SGDA for nonconvex-PL min-max games due to its provable suboptimality and failure cases at small timescale ratios.

A theory result. No direct application yet.

Authors

Junsoo Ha

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 $μ$-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. 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(κ^2)$. Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.