Metraipolis › archive › dc_52f451970fab
Optimal Deterministic Oracle Complexity for Weakly Convex Optimization — arXiv:2608.03246
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.03246
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T12:48:29.402Z
- SHA-256 of the archived text
499f26d049d0a7df37ec58042929b8befbfbbdec806356364602e81a48a233ab- Stable URL of this page
https://metraipolis.com/documento/dc_52f451970fab
How to cite
Optimal Deterministic Oracle Complexity for Weakly Convex Optimization — arXiv:2608.03246 — arXiv (en), https://arxiv.org/abs/2608.03246 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_52f451970fab (Metraipolis archive dc_52f451970fab, sha256 499f26d049d0a7df37ec58042929b8befbfbbdec806356364602e81a48a233ab)
BibTeX
@misc{dc52f451970fab,
title = {Optimal Deterministic Oracle Complexity for Weakly Convex Optimization — arXiv:2608.03246},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.03246},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_52f451970fab; sha256 499f26d049d0a7df37ec58042929b8befbfbbdec806356364602e81a48a233ab},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03246. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the oracle complexity of finding $\epsilon$-stationary points of $\rho$-weakly convex and $G$-Lipschitz functions, where stationarity is measured by the gradient of the Moreau envelope. We consider a first-order oracle that returns both the function value and the full subdifferential at every query point. We prove that every deterministic first-order algorithm requires $ \Omega({\rho G^2\Delta}/{\epsilon^4})$ oracle queries whenever $\Delta \leq {G^2}/{\rho}$, where $f(\bz)-\inf f \leq \Delta$. This lower bound matches the best known deterministic and stochastic first-order upper bounds, up to universal constants, and establishes the optimal deterministic oracle complexity. The result reveals a fundamental complexity separation between smooth nonconvex and nonsmooth weakly convex optimization. While smooth nonconvex minimization admits a $\Theta(\epsilon^{-2})$ oracle complexity, nonsmooth weakly convex optimization incurs an intrinsic additional $\epsilon^{-2}$ factor arising from nonsmooth geometry rather than stochasticity.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.03246 — 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-31T12:35:48.810Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).