Revisiting Proximal Bundle Methods: Improved Rates under H{ö}lder Smoothness
Abstract
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 ProxBundle. We analyze 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 𝒪(ε−(3−ν)/(1+ν)) for ν∈[0,1) and 𝒪(ε−1) for ν=1, where ν is the H{ö}lder smoothness exponent. Choosing the proximal parameter proportional to ε improves the rate to 𝒪(ε−2/(1+ν)) for ν∈ [0,1). These are the first guarantees under Hölder smoothness with ν∈(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 𝒪(ε−2/(1+ν)). Overall, our analysis separates the roles of the descent and null steps and gives a modular understanding of PBMs across different~tests.
Related
- Global Linear Convergence of the Proximal Bundle Method under Unknown Piecewise Smoothness and Quadratic Growth
- Weak Convexity and Proximal Bundle Methods for Nonsmooth Policy Optimization in Robust Control
- Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse
- Improved Guarantees for Langevin Monte Carlo with Average Smoothness
- Complexity analysis of trust-region methods under (α,L0,L1)-smoothness
BibTeX
@misc{liao2026revisiting,
title = {{Revisiting Proximal Bundle Methods: Improved Rates under Hölder Smoothness}},
author = {Feng-Yi Liao and Yang Zheng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15806},
eprint = {2609.15806},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15806},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Revisiting Proximal Bundle Methods: Improved Rates under H{ö}lder Smoothness
AU - Feng-Yi Liao
AU - Yang Zheng
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15806
UR - https://arxiv.org/abs/2609.15806
AB - 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 ProxBundle. We analyze 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 𝒪(ε^−(3−ν)/(1+ν)) for ν∈[0,1) and 𝒪(ε^−1) for ν=1, where ν is the H{ö}lder smoothness exponent. Choosing the proximal parameter proportional to ε improves the rate to 𝒪(ε^−2/(1+ν)) for ν∈ [0,1). These are the first guarantees under Hölder smoothness with ν∈(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 𝒪(ε^−2/(1+ν)). Overall, our analysis separates the roles of the descent and null steps and gives a modular understanding of PBMs across different~tests.
ER -