An accelerated proximal bundle method for convex optimization

Feng-Yi Liao, Thomas Madden, Yang Zheng
Proceedings of The 8th Annual Learning for Dynamics and Control Conference, PMLR 331:1012-1034, 2026.

Abstract

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 $\mathcal{O}(1/\sqrt{\epsilon})$ iteration complexity for obtaining an $\epsilon$-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 $\mathcal{O}(1/\sqrt{\epsilon})$ convergence rate predicted by our theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v331-liao26a, title = {An accelerated proximal bundle method for convex optimization}, author = {Liao, Feng-Yi and Madden, Thomas and Zheng, Yang}, booktitle = {Proceedings of The 8th Annual Learning for Dynamics and Control Conference}, pages = {1012--1034}, year = {2026}, editor = {Sukhatme, Gaurav and Lindemann, Lars and Tu, Stephen and Wierman, Adam and Atanasov, Nikolay}, volume = {331}, series = {Proceedings of Machine Learning Research}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v331/main/assets/liao26a/liao26a.pdf}, url = {https://proceedings.mlr.press/v331/liao26a.html}, abstract = {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 $\mathcal{O}(1/\sqrt{\epsilon})$ iteration complexity for obtaining an $\epsilon$-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 $\mathcal{O}(1/\sqrt{\epsilon})$ convergence rate predicted by our theory.} }
Endnote
%0 Conference Paper %T An accelerated proximal bundle method for convex optimization %A Feng-Yi Liao %A Thomas Madden %A Yang Zheng %B Proceedings of The 8th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2026 %E Gaurav Sukhatme %E Lars Lindemann %E Stephen Tu %E Adam Wierman %E Nikolay Atanasov %F pmlr-v331-liao26a %I PMLR %P 1012--1034 %U https://proceedings.mlr.press/v331/liao26a.html %V 331 %X 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 $\mathcal{O}(1/\sqrt{\epsilon})$ iteration complexity for obtaining an $\epsilon$-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 $\mathcal{O}(1/\sqrt{\epsilon})$ convergence rate predicted by our theory.
APA
Liao, F., Madden, T. & Zheng, Y.. (2026). An accelerated proximal bundle method for convex optimization. Proceedings of The 8th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 331:1012-1034 Available from https://proceedings.mlr.press/v331/liao26a.html.

Related Material