Department of Mathematics,
University of California San Diego
****************************
Math 278B: Mathematics of Information, Data, and Signals
Thomas Madden
UCSD
Acceleration with large gradient steps via the proximal bundle method
Abstract:
The proximal bundle method (PBM) is a powerful and widely used approach for minimizing nonsmooth convex functions. For smooth objectives, its best-known convergence rate has remained suboptimal. We present the first accelerated proximal bundle method to achieve the optimal O(1/sqrt(epsilon)) iteration complexity. The proposed method is conceptually simple, differing from Nesterov's accelerated gradient descent by a single line, and preserving the key structural properties of the classical PBM. As a result, we obtain an accelerated algorithm with much broader stepsize selection than what is allotted by accelerated gradient descent. The talk will include many pictures and numerical simulations to motivate algorithm design and illustrate fast convergence, respectively.
February 13, 2026
11:00 AM
APM 6402
Research Areas
Mathematics of Information, Data, and Signals****************************

