Metraipolis › archive › dc_fbaf0b8562f2
Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games — arXiv:2610.07814
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.07814
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T11:27:53.877Z
- SHA-256 of the archived text
f2f2a6228421de06602d2add053846ab26188a66ecf01f74a53b18b9781325d7- Stable URL of this page
https://metraipolis.com/documento/dc_fbaf0b8562f2
How to cite
Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games — arXiv:2610.07814 — arXiv (en), https://arxiv.org/abs/2610.07814 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fbaf0b8562f2 (Metraipolis archive dc_fbaf0b8562f2, sha256 f2f2a6228421de06602d2add053846ab26188a66ecf01f74a53b18b9781325d7)
BibTeX
@misc{dcfbaf0b8562f2,
title = {Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games — arXiv:2610.07814},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.07814},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fbaf0b8562f2; sha256 f2f2a6228421de06602d2add053846ab26188a66ecf01f74a53b18b9781325d7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07814. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.07814 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:16:54.480Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).