Optimal Convergence Rates for the Proximal Bundle Method

Understand

We study convergence rates of the classic proximal bundle method for a variety of nonsmooth convex optimization problems.

• We show that, without any modification, this algorithm adapts to converge faster in the presence of smoothness or a H\"older growth condition.
• Our analysis reveals that with a constant stepsize, the bundle method is adaptive, yet it exhibits suboptimal convergence rates.
• We overcome this shortcoming by proposing nonconstant stepsize schemes with optimal rates.