Metraipolis › archive › dc_beb9dc1a91ae
On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles — arXiv:2611.04806
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04806
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T21:51:46.425Z
- SHA-256 of the archived text
13a709e986faf8e6ea057b2ed0f6cb470b9c63ba133aac0481ca2d8f01406370- Stable URL of this page
https://metraipolis.com/documento/dc_beb9dc1a91ae
How to cite
On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles — arXiv:2611.04806 — arXiv (en), https://arxiv.org/abs/2611.04806 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_beb9dc1a91ae (Metraipolis archive dc_beb9dc1a91ae, sha256 13a709e986faf8e6ea057b2ed0f6cb470b9c63ba133aac0481ca2d8f01406370)
BibTeX
@misc{dcbeb9dc1a91ae,
title = {On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles — arXiv:2611.04806},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04806},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_beb9dc1a91ae; sha256 13a709e986faf8e6ea057b2ed0f6cb470b9c63ba133aac0481ca2d8f01406370},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04806. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Finite-sum nonconvex-strongly-concave minimax problems arise in adversarial training and distributionally robust learning. Their known lower bounds cover only linear-span algorithms, zero-respecting algorithms, or a restricted proximal protocol. They leave open the power of exact component proximal steps, whose responses are global saddle points of regularized component problems and can expose directions that gradients do not reveal. We show that neither unrestricted adaptivity nor exact proximal access improves the polynomial complexity. We consider $n$ components with joint mean-squared smoothness $L$ and condition number $\kappa$, started from a point with primal gap at most $\Delta$ and joint gradient norm at most $\sqrt{2L\Delta}$. For $\varepsilon^2/(L\Delta)$ below a universal constant, every randomized adaptive algorithm with exact component values, gradients, and proximal responses needs $\Omega(n+\min\{\sqrt n\,\kappa,n^{3/4}\sqrt\kappa\}L\Delta/\varepsilon^2)$ component queries in the worst case to find an $\varepsilon$-stationary point of the value function. A method using only component gradients attains this rate up to a factor $\log^2(2+\kappa)$, including initialization. Zhou ( arXiv:2610.04944 ) concurrently proves the same rate for zero-respecting first-order methods. In our hard instances, every component admits proximal steps with the same step sizes, and a response for a component reveals hidden directions only up to the first one assigned to another component.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.04806 — 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-11-04T21:38:49.732Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).