Metraipolis › archive › dc_f2670b5fa2ca
Revisiting Proximal Bundle Methods: Improved Rates under H{ö}lder Smoothness — arXiv:2609.15806
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15806
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T00:39:24.445Z
- SHA-256 of the archived text
3b212b661501b9e8f967710759b5c532311f5135fe01dbf1ab04354c0c1c03cb- Stable URL of this page
https://metraipolis.com/documento/dc_f2670b5fa2ca
How to cite
Revisiting Proximal Bundle Methods: Improved Rates under H{ö}lder Smoothness — arXiv:2609.15806 — arXiv (en), https://arxiv.org/abs/2609.15806 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f2670b5fa2ca (Metraipolis archive dc_f2670b5fa2ca, sha256 3b212b661501b9e8f967710759b5c532311f5135fe01dbf1ab04354c0c1c03cb)
BibTeX
@misc{dcf2670b5fa2ca,
title = {Revisiting Proximal Bundle Methods: Improved Rates under Hölder Smoothness — arXiv:2609.15806},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15806},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f2670b5fa2ca; sha256 3b212b661501b9e8f967710759b5c532311f5135fe01dbf1ab04354c0c1c03cb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15806. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Proximal bundle methods (PBMs) are classical algorithms for nonsmooth convex optimization. Existing analyses of the classical PBM couple the null steps with the descent test. This coupling obscures how the bundle updates approximate the proximal subproblem. In this work, we consider composite objectives $F=f+h$ and view each null-step cycle as an inner bundle subroutine, called $\mathtt{ProxBundle}$. We analyze $\mathtt{ProxBundle}$ independently of any stopping criterion under general bundle model conditions and show that it automatically adapts to H{ö}lder smoothness. Combining this inner-loop analysis with the descent-step analysis yields sharper complexity bounds for the classical PBM. For any fixed proximal parameter, its overall complexity is $\mathcal O\big(\epsilon^{-\frac{3-\nu}{1+\nu}}\big)$ for $\nu\in[0,1)$ and $\mathcal O(\epsilon^{-1})$ for $\nu=1$, where $\nu$ is the H{ö}lder smoothness exponent. Choosing the proximal parameter proportional to $\epsilon$ improves the rate to $\mathcal O\big(\epsilon^{-\frac{2}{1+\nu}}\big)$ for $\nu \in [0,1)$. These are the first guarantees under Hölder smoothness with $\nu\in(0,1)$ for the classical descent test. We further introduce an absolute model-error test. The resulting PBM variant admits a clean inexact proximal-point analysis, and for any fixed proximal parameter, achieves the same complexity $\mathcal O\big(\epsilon^{-\frac{2}{1+\nu}}\big)$. Overall, our analysis separates the roles of the descent and null steps and gives a modular understanding of PBMs across different~tests.
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) ; Systems and Control (eess.SY).
Pagina del lavoro: https://arxiv.org/abs/2609.15806 — 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.846Z 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).