An accelerated proximal bundle method for convex optimization
This work solves a long-standing open problem in convex optimization by proving that proximal bundle methods can be accelerated to achieve optimal rates, benefiting researchers and practitioners in nonsmooth optimization.
The authors present the first accelerated proximal bundle method that achieves optimal O(1/√ε) iteration complexity for smooth convex optimization, matching Nesterov's accelerated gradient descent while retaining the structural properties of classical PBM.
The proximal bundle method (PBM) is a powerful and widely used approach for minimizing nonsmooth convex functions. However, for smooth objectives, its best-known convergence rate remains suboptimal, and whether PBM can be accelerated remains open. In this work, we present the first accelerated proximal bundle method that achieves the optimal $\mathscr{O}(1/\sqrtε)$ iteration complexity for obtaining an $ε$-accurate solution in smooth convex optimization. The proposed method is conceptually simple, which differs from Nesterov's accelerated gradient descent by only a single line and retains all key structural properties of the classical PBM. In particular, it relies on the same minimal assumptions on model approximations and preserves the standard bundle testing criterion. Numerical experiments confirm the accelerated $\mathscr{O}(1/\sqrtε)$ convergence rate predicted by our theory.