Revisiting Proximal Bundle Methods: Improved Rates under H{\"o}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 $\mathtt{ProxBundle}$. We analyze $\mathtt{ProxBundle}$ independently of any stopping criterion under general bundle model conditions and show that it automatically adapts to H{\"o}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{\"o}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\"older 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.