Metraipolis › archive › dc_52ea1ecc117c
Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization — arXiv:2609.14235
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14235
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T00:39:14.133Z
- SHA-256 of the archived text
4e064504d4ecc8bb3c237716127ccfd596ffb8ad14be06cce5f5000445438cd1- Stable URL of this page
https://metraipolis.com/documento/dc_52ea1ecc117c
How to cite
Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization — arXiv:2609.14235 — arXiv (en), https://arxiv.org/abs/2609.14235 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_52ea1ecc117c (Metraipolis archive dc_52ea1ecc117c, sha256 4e064504d4ecc8bb3c237716127ccfd596ffb8ad14be06cce5f5000445438cd1)
BibTeX
@misc{dc52ea1ecc117c,
title = {Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization — arXiv:2609.14235},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14235},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_52ea1ecc117c; sha256 4e064504d4ecc8bb3c237716127ccfd596ffb8ad14be06cce5f5000445438cd1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14235. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the deterministic first-order oracle complexity of smooth nonconvex-concave minimax optimization over a bounded convex dual domain. Let $\ell$ denote the joint smoothness constant, $D_{\mathcal{Y}}$ the diameter of the dual domain, and $\Delta$ the initial gap. We prove that every deterministic first-order algorithm requires $\Omega(\ell^2D_{\mathcal{Y}}\Delta/\epsilon^3)$ oracle queries in the worst case to find an $\epsilon$-optimization-stationary point whenever $\epsilon\lesssim\min\{\ell D_{\mathcal{Y}},\sqrt{\ell\Delta}\}$. We then develop Tracked-FOAM, a first-order method that attains a matching upper bound, removing the logarithmic factor from previous upper bounds. Together, these results establish the optimal dependence on all problem parameters in the stated regime.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.14235 — 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-16T00:16:48.815Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).