Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.20351 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909596712435712 |
|---|---|
| author | Fersztand, David Sun, Xu Andy |
| author_facet | Fersztand, David Sun, Xu Andy |
| contents | The proximal bundle method (PBM) is a fundamental and computationally effective algorithm for solving nonsmooth optimization problems. In this paper, we present the first variant of the PBM for smooth objectives, achieving an accelerated convergence rate of $O(ε^{-1/2}\log(1/ε))$, where $ε$ is the desired accuracy. Our approach addresses an open question regarding the convergence guarantee of proximal bundle type methods, which was previously posed in two recent papers. We interpret the PBM as a proximal point algorithm and base our proposed algorithm on an accelerated inexact proximal point scheme. Our variant introduces a novel null step test and oracle while maintaining the core structure of the original algorithm. The newly proposed oracle substitutes the traditional cutting planes with a smooth lower approximation of the true function. We show that this smooth interpolating lower model can be computed as a convex quadratic program. We also examine a second setting where Nesterov acceleration can be effectively applied, specifically when the objective is the sum of a smooth function and a piecewise linear one. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20351 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Acceleration of Proximal Bundle Methods Fersztand, David Sun, Xu Andy Optimization and Control The proximal bundle method (PBM) is a fundamental and computationally effective algorithm for solving nonsmooth optimization problems. In this paper, we present the first variant of the PBM for smooth objectives, achieving an accelerated convergence rate of $O(ε^{-1/2}\log(1/ε))$, where $ε$ is the desired accuracy. Our approach addresses an open question regarding the convergence guarantee of proximal bundle type methods, which was previously posed in two recent papers. We interpret the PBM as a proximal point algorithm and base our proposed algorithm on an accelerated inexact proximal point scheme. Our variant introduces a novel null step test and oracle while maintaining the core structure of the original algorithm. The newly proposed oracle substitutes the traditional cutting planes with a smooth lower approximation of the true function. We show that this smooth interpolating lower model can be computed as a convex quadratic program. We also examine a second setting where Nesterov acceleration can be effectively applied, specifically when the objective is the sum of a smooth function and a piecewise linear one. |
| title | On the Acceleration of Proximal Bundle Methods |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2504.20351 |