Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces

2025-07-25 · Zhe Zhang, Suvrit Sra arxiv

We develop efficient algorithms for optimizing piecewise smooth (PWS) functions where the underlying partition of the domain into smooth pieces is \emph{unknown}. For PWS functions satisfying a quadratic growth (QG) condition, we propose a bundle-level (BL) type method that achieves global linear convergence -- to our knowledge, the first such result for any algorithm for this problem class. We extend this method to handle approximately PWS functions and to solve weakly-convex PWS problems, improving the state-of-the-art complexity to match the benchmark for smooth non-convex optimization. Furthermore, we introduce the first verifiable and accurate termination criterion for PWS optimization. Similar to the gradient norm in smooth optimization, this certificate tightly characterizes the optimality gap under the QG condition, and can moreover 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 an almost parameter-free algorithm for both the convex QG and weakly-convex settings.

📄 PDF Abstract BibTeX arXiv:2507.19465

Code (0)

등록된 구현이 없습니다.

Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth Optimization

2017-04-26 · Feihu Huang, Songcan Chen

In this paper, we study the stochastic gradient descent (SGD) method for the nonconvex nonsmooth optimization, and propose an accelerated SGD method by combining the variance reduction technique with Nesterov's extrapola…

Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems

2015-12-31 · Bo Wen, Xiaojun Chen, Ting Kei Pong

In this paper, we study the proximal gradient algorithm with extrapolation for minimizing the sum of a Lipschitz differentiable function and a proper closed convex function. Under the error bound condition used in [19] f…

Global Convergence of Model Function Based Bregman Proximal Minimization Algorithms

2020-12-24 · Mahesh Chandra Mukkamala, Jalal Fadili, Peter Ochs

Lipschitz continuity of the gradient mapping of a continuously differentiable function plays a crucial role in designing various optimization algorithms. However, many functions arising in practical applications such as …

Retrieval valid

Linear convergence of a policy gradient method for some finite horizon continuous time control problems

2022-03-22 · Christoph Reisinger, Wolfgang Stockinger, Yufei Zhang

Despite its popularity in the reinforcement learning community, a provably convergent policy gradient method for continuous space-time control problems with nonlinear state dynamics has been elusive. This paper proposes …

Policy Gradient Methods reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

A refined convergence analysis of pDCA$_e$ with applications to simultaneous sparse recovery and outlier detection

2018-04-19 · Tianxiang Liu, Ting Kei Pong, Akiko Takeda

We consider the problem of minimizing a difference-of-convex (DC) function, which can be written as the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function and a continuous possibly n…

compressed sensing CPU Outlier Detection