An accelerated proximal bundle method for convex optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908994718662656 |
|---|---|
| author | Liao, Feng-Yi Madden, Thomas Zheng, Yang |
| author_facet | Liao, Feng-Yi Madden, Thomas Zheng, Yang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_04523 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An accelerated proximal bundle method for convex optimization Liao, Feng-Yi Madden, Thomas Zheng, Yang Optimization and Control Systems and Control 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. |
| title | An accelerated proximal bundle method for convex optimization |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2512.04523 |