An Absolute-Error Proximal Bundle Method through the Lens of Frank-Wolf

The proximal bundle method (PBM) is a fundamental and computationally effective algorithm for solving optimization problems with nonsmooth components.

In this paper, we conduct a theoretical investigation of a modified proximal bundle method, which we call the Modified Proximal Bundle with Fixed Absolute Accuracy (MPB-FA).

MPB-FA modifies the serious-step test of the PBM serious-step test.

In MPB-FA, it is based on an absolute accuracy criterion, and the accuracy is fixed over iterations, while the standard PBM uses a relative accuracy in the serious-step test, which changes with iterations.

Also, similarly to multiple PBM analyses, the proximal parameter in MPB-FA is also fixed over iterations, while it is permitted to change in the standard PBM.

These modifications allow us to build the first link between a proximal bundle method and a Frank-Wolfe algorithm on the Moreau envelope of the dual problem.

In light of this correspondence, we first extend the linear convergence of Kelley's method on the sum of a smooth strongly convex function and a convex piecewise linear function from the positive homogeneous to the general case.

Building on this result, we propose a novel complexity analysis of MPB-FA when the objective is the sum of a smooth and a piecewise function and derive an $\mathcal{O}(\epsilon^{-8/9})$ iteration complexity, improving upon the best known $\mathcal{O}(\epsilon^{-2})$ guarantee on a related variant of PBM.

It is worth-noting that the best known complexity bound for the classical PBM in the general case is $\mathcal{O}(\epsilon^{-3})$ and $\mathcal{O}(\epsilon^{-2})$ when the proximal parameter is fixed.

Our approach also reveals new insights on bundle management and empirical behavior of the proximal bundle methods.