arXiv：cs.LG· Junsoo Ha·· 7 小时前AI 评分36
研究：SGDA 在非凸-PL 极小极大博弈中次优
Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games
AI 导读
研究首次给出固定时间尺度比与非递增步长下双时间尺度 SGDA 在非凸-PL 博弈中的紧复杂度：下界为 Ω(κ²ℓε⁻²+κ⁴ℓσ²ε⁻⁴)，与现有 SGDA 上界吻合，并与 Smoothed-AGDA 形成复杂度分离。作者还证明当时间尺度比小至 o(κ²) 时，SGDA 可能无法找到稳定点，说明其在 NC-PL 博弈中存在根本局限，需发展替代方法。
正文
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^2\ell\varepsilon^{-2}+\kappa^4\ell\sigma^2\varepsilon^{-4})$, where $\kappa=\ell/\mu$ is the condition number, $\sigma^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(\kappa^2)$. Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.
| Subjects: | Machine Learning (stat.ML); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07814 [stat.ML] |
| (or arXiv:2610.07814v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07814 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Junsoo Ha [view email]
[v1]
Tue, 6 Oct 2026 06:08:34 UTC (270 KB)
来源：arXiv：cs.LG · arxiv.org