math.OCJul 25, 2025

Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions

Authors: Zhe Zhang, Suvrit Sra

Organizations: School of Industrial Engineering, Purdue University, USA · Department of Mathematics, CIT, TU Munich, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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~\cite{lemarechal1995new} 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.

Figures & tables

Figure 1: Illustration of a Piecewise Smooth Function.
 X(t):={x∈X∣⟨f′(xt−i),x−xt−i⟩+f(xt−i)≤f∗,∀i∈{0,…,min⁡{m−1,t}}}.\displaystyle X(t):=\{x\in X\mid\langle f^{\prime}(x^{t-i}),x-x^{t-i}\rangle+f(x^{t-i})\leq f^{*},\quad\forall i\in\{0,\ldots,\min\{m-1,t\}\}\}. 
Algorithm 2.1 The Bundle-Level Method with Known f∗f^{*} , BL( m,f∗,x0m,f^{*},x^{0} )
 X(t):={x∈X∣l~f(x;xt−i)≤f∗,∀i∈{0,…,min⁡{m−1,t}}}.\displaystyle X(t):=\{x\in X\mid\tilde{l}_{f}(x;x^{t-i})\leq f^{*},\quad\forall i\in\{0,\dots,\min\{m-1,t\}\}\}. 
Algorithm 3.1 The Approximate Bundle Level Method with Known f∗f^{*} , apx-BL( m,f∗,x0m,f^{*},x^{0} )
  Optimality Gap 
CertificateVerifiableUpper BoundProportionalComputableHandles Constraints
Optimality Gap×\times✓✓×\times✓
Gradient Mapping✓✓×\times✓✓
Moreau Stationarity✓✓✓×\times✓
Approx. Moreau×\times✓✓✓✓
Goldstein Stationarity✓✓?✓×\times
Table 1: Comparison of termination certificates for PWS problems against the criteria from Definition 9 .
More in this topic

Nonsmooth Convex Optimization

Nonsmooth convex optimization studies minimizing convex objectives that may lack gradients, using subgradients, proximal methods, and oracle-based algorithms.

See all 22 papers

Explore similar work

CardsList

  1. Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

    Oct 9, 2026Gon Buzaglo, Guy KornowskiNonconvex Stochastic OptimizationConstrained Optimization

    Princeton University · Institute for Advanced Study

  2. Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization

    Aug 31, 2025Laurent Condat, Peter RichtárikStochastic OptimizationNonconvex Stochastic Optimization

    King Abdullah University of Science and Technology (KAUST) Thuwal, Kingdom of Saudi Arabia

  3. A Parameter-Free First-Order Algorithm for Non-Convex Optimization with  O~(ε−5/3)\tilde{\mkern1mu O}(ε^{-5/3}) Global Rate

    May 4, 2026Sichao Xiong, Sadok Jerad, Coralia CartisOptimization Convergence AnalysisGradient Descent

    Department of Computer Science University of Oxford Oxford, OX1 3QG · Mathematical Institue University of Oxford Oxford, OX2 6GG