# Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions

arXiv: https://arxiv.org/abs/2507.19465 · HTML: https://mlsanity.com/paper/2507.19465/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 46 references that are in the map.
- First posted on arXiv 25 Jul 2025.

## Builds on (most cited first, 13 of 13)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Optimal Convergence Rates for the Proximal Bundle Method](https://mlsanity.com/paper/2105.07874/) (2021)
- [Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization](https://mlsanity.com/paper/2310.12139/) (2023)
- [A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes](https://mlsanity.com/paper/2003.11457/) (2020)
- [A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth](https://mlsanity.com/paper/2205.00064/) (2022)
- [Rate of Convergence of the Bundle Method](https://mlsanity.com/paper/1609.00842/) (2016)
- [Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization](https://mlsanity.com/paper/2111.15645/) (2021)
- [Uniformly Optimal and Parameter-free First-order Methods for Convex and Function-constrained Optimization](https://mlsanity.com/paper/2412.06319/) (2024)
- [Optimal Methods for Convex Risk Averse Distributed Optimization](https://mlsanity.com/paper/2203.05117/) (2022)

## Abstract (arXiv)

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.