Metraipolis › archive › dc_03027bdb4ff7
Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization — arXiv:2609.24423
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.24423
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T07:08:47.576Z
- SHA-256 of the archived text
401304eec94d837aeca6dcdc200778e474e857591929b7ccac016c439f565c02- Stable URL of this page
https://metraipolis.com/documento/dc_03027bdb4ff7
How to cite
Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization — arXiv:2609.24423 — arXiv (en), https://arxiv.org/abs/2609.24423 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_03027bdb4ff7 (Metraipolis archive dc_03027bdb4ff7, sha256 401304eec94d837aeca6dcdc200778e474e857591929b7ccac016c439f565c02)
BibTeX
@misc{dc03027bdb4ff7,
title = {Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization — arXiv:2609.24423},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.24423},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_03027bdb4ff7; sha256 401304eec94d837aeca6dcdc200778e474e857591929b7ccac016c439f565c02},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24423. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-22 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.24423 — 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-09T06:58:09.644Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).