Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces

Zhe Zhang, Suvrit Sra · 2025

Read Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces by Zhe Zhang, Suvrit Sra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19465.txt.

Introduction

Zhe Zhang and Suvrit Sra design fast algorithms for optimization problems that are smooth only in pieces in a 2025 paper. Many real functions are stitched from smooth parts, but the stitching map is unknown to the solver. For convex problems of that kind with a growth condition, their bundle level style method reaches the answer with linear convergence. They state this is the first such guarantee for this problem class.

The method extends to weakly convex problems with the same cost order as smooth non convex solvers. They also add a checkable stopping test that plays the role the gradient size plays in smooth problems. It tightly bounds the remaining error and needs no knowledge of problem parameters. A guess and check wrapper around it yields nearly parameter free algorithms.

Catalog record

CREATORZhe Zhang, Suvrit Sra
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE142 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19465

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces Zhe Zhang, Suvrit Sra Abstract We develop efficient algorithms for optimizing piecewise smooth (PWS) functions where the underlying partition of the domain into smooth pieces is unknown . For PWS functions satisfying a quadratic growth (QG) condition, we propose a bundle-level (BL) type method lemarechal1995new 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. ∎ 1 Introduction Non-smoothness is a major bottleneck in optimization. In its presence, theoretical convergence rates plummet from linear to sublinear for convex problems under the QG condition LanBook ; nesterov2003introductory ; nemirovsky1983problem , and degrade by orders of magnitude for non-convex problems zhang2020complexity ; davis2019stochastic . Crucially, for general non-smooth functions, this performance gap is fundamentally unavoidable nemirovsky1983problem ; nesterov2003introductory . In this paper, we study a specific, widely applicable class of non-smooth functions: piecewise smooth (PWS) functions. A function is PWS if its domain can be partitioned into a finite number of subsets (pieces) such that restricted to each piece (see Definition 1 ) the function is smooth. Clearly, PWS functions present a more structured form of non-smoothness compared to the general case, as their gradients are continuous within the interior of each piece, and non-differentiability occurs only on the lower-dimensional boundaries between pieces (that have measure zero). The PWS structure appears in many important applications, including statistics (e.g., elastic net regularization), signal processing (e.g., compressive sensing and phase retrieval), economics (e.g., matrix games), control (e.g., multiparametric programming), and machine learning (e.g., the ReLU activation function). A key challenge arises in many practical scenarios where the underlying pieces comprising the PWS objective function are too complicated or unknown a priori . This lack of knowledge about the function’s specific structure raises the following central research question: Can one optimize PWS functions with unknown pieces using almost the same oracle complexity as that of smooth optimization? We answer this question by developing new algorithms for optimizing PWS problems of the form: \min_{x\in X}f(x), (1.1) where the objective function f is PWS, and the feasible region X is closed, convex, and simple ben2001lectures (i.e., sets onto which projection is computationally efficient). An illustrative example of such a PWS function is given by f(x)=\|x\|^{2}+|x_{1}|,\quad x\in\mathbb{R}^{2}. (1.2) As plotted in Figure 1a , the non-smooth component |x_{1}| divides the domain \mathbb{R}^{2} into two regions, X_{1}:=(-\infty,0]\times\mathbb{R} and X_{2}:=(0,\infty)\times\mathbb{R} . Observe that f is differentiable everywhere except on the boundary between these regions (the x_{2} -axis, where x_{1}=0 ), and the gradient \nabla f(x) is continuous within the interior of each piece. (a) f(x)=\|x\|^{2}+|x_{1}|. (b) GD Iterates from x^{0}=[1e^{-4};1e^{-2}]. Figure 1: Illustration of a Piecewise Smooth Function. Despite the structure of PWS functions, there has been limited success in designing algorithms capable of achieving “almost smooth performance” for optimizing them, especially when the pieces are unknown. Specifically, for iterative first-order (FO) methods, fast convergence typically relies on computing the next iterate based on accurate FO information obtained at the current iterate. However, obtaining such information is challenging for PWS functions with unknown pieces: the FO information (e.g., the gradient) generated at a given iterate is accurate only within the smooth piece containing that iterate. Ensuring this information remains relevant for determining the next iterate is difficult when the iterates jump between different unknown smooth pieces. More concretely, the standard gradient descent (GD) method can perform poorly even on the simple example in ( 1.2 ). Since the GD update relies solely on the gradient at the previous iterate, it offers little guarantee of progress when the current iterate lands in a different smooth piece than the previous one. This potential inefficiency is demonstrated by the characteristic zig-zagging pattern often observed in GD iterates for such problems, as illustrated in Figure 1b for iterates generated using the optimal Polyak stepsize. In contrast, methods that utilize information from multiple past iterates, such as the bundle-level (BL) method, can potentially overcome this limitation. The BL method uses first-order (FO) information from the m most recent iterates (via cuts, see ( 1.3 ) later). Thus, as long as the next iterate x^{t+1} lands on the same piece as any recent iterate x^{t-i} ( i\in\{0,\dots,m-1\} ), the cut generated at x^{t-i} provides relevant information, potentially guiding x^{t+1} toward making significant progress. 1.1 Overview of Existing approaches Before detailing our approach and contributions, we first review existing approaches more broadly. In the literature, two main directions exist for tackling the PWS optimization problem ( 1.1 ), though neither approach fully achieves efficient global convergence when the function’s underlying PWS structure is unknown. First, when the PWS function admits a known max-of-smooth representation (conceptually illustrated by the shadow pieces in Figure 1a ), the prox-linear update nemirovski1995information ; nesterov2003introductory ; Lan15Bundle can be employed. This method evaluates gradients on all constituent smooth functions at the current iterate, and uses all this information to generate the next iterate. It can achieve “almost smooth performance” because at least one of these gradients provides accurate information for the active (maximal) function near the next iterate. However, the prerequisite of requiring access to all component functions is far too strong in applications where pieces are unknown. The second approach exploits the so-called \mathcal{VU} structure mifflin2005algorithm ; lemarechal2000 ; han2023survey ; davis2024local that characterizes the local geometry around an optimal solution. This structure decomposes into a smooth component (the \mathcal{U} -component) associated with an affine subspace, and a non-smooth component orthogonal to it (the \mathcal{V} -component). By analyzing projections of the iterates onto the \mathcal{U} -space, linear convergence can be achieved. However, the definition and identification of the \mathcal{U} -space rely on local information around the optimum. This limits these convergence guarantees to a local neighborhood, thus providing little insight into the global oracle complexity needed to answer our research question. The approach taken in our paper proceeds by re-examining the classical bundle-level (BL) type methods, and affirmatively answers the posed research question. As motivated above and unlike the methods reviewed, BL methods do not require explicit knowledge of the pieces, and can be analyzed globally. Rather than measuring one-step progress, the key to our approach is a novel technique that analyzes multi-step progress. Under this new perspective, we prove that the BL method makes significant progress once two iterates (that need not be consecutive) land within the same piece. When the total number of pieces is finite, say k , (by the pigeonhole principle) this event is guaranteed to happen every k+1 steps. Thus, the iterates make significant progress periodically, resulting in the desired linear convergence under the strongly convex setting. 1.2 Main

Read the complete text