Metraipolis › archive › dc_f3ebdf825787

Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization — arXiv:2610.00229

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.00229
License (as archived)
CC0-1.0
Archived
2026-10-06T15:59:58.591Z
SHA-256 of the archived text
8e32b79bdfbac96bb683bb61eed59a27f0df871068bc5a18ed20250466f43088
Stable URL of this page
https://metraipolis.com/documento/dc_f3ebdf825787

How to cite

Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization — arXiv:2610.00229 — arXiv (en), https://arxiv.org/abs/2610.00229 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f3ebdf825787 (Metraipolis archive dc_f3ebdf825787, sha256 8e32b79bdfbac96bb683bb61eed59a27f0df871068bc5a18ed20250466f43088)
BibTeX
@misc{dcf3ebdf825787,
  title = {Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization — arXiv:2610.00229},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.00229},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f3ebdf825787; sha256 8e32b79bdfbac96bb683bb61eed59a27f0df871068bc5a18ed20250466f43088},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.00229. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We characterize the fresh-gradient oracle complexity of smooth nonconvex-strongly-concave minimax optimization, with matching upper and lower bounds up to logarithmic factors. Let $\Phi(x)=\max_y f(x,y)$, where $f$ is jointly $L$-smooth and $\mu$-strongly concave in $y$ on unconstrained Euclidean domains, and set $\kappa=L/\mu$. Each query returns a fresh unbiased joint gradient with conditional variance at most $\sigma^2$. Given initial primal gap at most $\Delta$ and dual residual $\|\nabla_y f(x_0,y_0)\|\le G$, the fixed-budget complexity of finding $\|\nabla\Phi(\widehat x)\|\le\epsilon$ with probability at least $2/3$ is $\widetilde{\Theta}(\sqrt{\kappa}L\Delta/\epsilon^2+\kappa L\Delta\sigma^2/\epsilon^4+\kappa^2\sigma^2/\epsilon^2+\sqrt{\kappa}\log_+(G/(\epsilon\sqrt{\kappa})))$, where $\log_+u=\log\max\{1,u\}$. This characterization holds when $\kappa$ and $L\Delta/\epsilon^2$ exceed universal constants, uniformly over finite dimensions, and the suppressed logarithms are independent of $G$. It establishes the necessity of linear condition-number dependence in the global stochastic cost and identifies a separate statistical refinement cost. A proximal method separates coarse primal progress from one final refinement, while the lower bounds apply to arbitrary adaptive randomized algorithms. Dual initialization contributes only an additive logarithmic cost, yet removing its control eliminates every finite dimension-free complexity bound, even with exact gradients.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-02 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.00229 — 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-06T15:14:57.922Z dalla pagina https://arxiv.org/catchup/math.OC/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).