Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions

We develop efficient algorithms for optimizing piecewise smooth (PWS) functions when their smooth regions are unknown to the algorithm. For convex PWS functions satisfying a quadratic growth (QG) condition, we demonstrate that the bundle-level (BL)-type method~citelemarechal1995new achieves global linear convergence---to our knowledge, the first such result for any algorithm for this problem class. We extend the method to solve weakly convex PWS problems, achieving the same order of complexity as in smooth non-convex optimization. Furthermore, we introduce a verifiable and accurate termination criterion for PWS optimization. Like the gradient norm in smooth optimization, this certificate tightly characterizes the optimality gap under the QG condition and can be evaluated without knowledge of any problem parameters. We develop a search subroutine for this certificate and embed it within a guess-and-check framework, resulting in almost parameter-free algorithms for both convex QG and weakly convex PWS problems.