Optimal Convergence Rates for the Proximal Bundle Method
研究了经典近端束方法在多种非光滑凸优化问题中的收敛速率，发现常数步长下算法自适应但速率次优，提出了具有最优速率的变步长方案和平行化变体，数值实验支持结论。
.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ölder 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. These schemes use function information such as growth constants, which might be prohibitive in practice. We provide a parallelizable variant of the bundle method that can be applied without prior knowledge of function parameters while maintaining near-optimal rates. The practical impact of this scheme is limited since we incur a (parallelizable) log factor in the complexity. These results improve on the scarce existing convergence rates and provide a unified analysis approach across problem settings and algorithmic details. Numerical experiments support our findings.Keywordsconvex optimizationproximal bundle methodconvergence ratesfirst-order methodsHolder growthMSC codes90C0690C3090C2565K0565K10