David Fersztand

On the Acceleration of Proximal Bundle Methods

  • David Fersztand
  • Xu Andy Sun
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    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 \(\frac{1}{\sqrt{\epsilon}}\log(\frac{1}{\epsilon})\), where \(\epsilon\) is the desired accuracy. Our approach addresses an open question regarding the convergence guarantee of … Read more

    The Proximal Bundle Algorithm Under a Frank-Wolfe Perspective: an Improved Complexity Analysis

  • David Fersztand
  • Xu Andy Sun
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    The proximal bundle algorithm (PBA) is a fundamental and computationally effective algorithm for solving optimization problems with nonsmooth components. We investigate its convergence rate, focusing on composite settings where one function is smooth and the other is piecewise linear. We interpret a sequence of null steps of the PBA as a Frank-Wolfe algorithm on the … Read more