Global Linear Convergence of the Proximal Bundle Method under Unknown Piecewise Smoothness and Quadratic Growth

We study why the proximal bundle method (PBM) can perform better in practice when it retains more cutting planes. We consider convex objectives with quadratic growth and an unknown piecewise-smooth structure. Our key observation is that retaining sufficiently many cutting planes allows PBM to exploit the objective’s piecewise-smooth structure and behave as if it were optimizing a smooth function. We provide a theoretical explanation for the observed linear convergence of PBM on piecewise-smooth objectives when it retains sufficiently many cutting planes.