Inexactly Smooth Performance Estimation and New Optimized Gradient Methods
Aaron Zoll, Benjamin Grimmer · 2026
Read Inexactly Smooth Performance Estimation and New Optimized Gradient Methods by Aaron Zoll, Benjamin Grimmer (2026) 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-2606-01505.txt.
Introduction
Zoll and Grimmer build a theory of inexactly smooth convex functions. This class unifies several known function families. L-smooth, Lipschitz, and Hölder smooth functions all fit inside. Any combination of those traits fits as well. The class has a calculus close to the smooth case. Their main results give interpolation theorems for the class. The conditions are necessary and sufficient up to constants. First-order methods can then be analyzed via performance estimation.
Any inexactly smooth convex problem class fits that route. Drori and Taylor's constructive design approach extends too. They derive a minimax optimal method for Hölder problems. Best-known guarantees follow for the general Hölder family. A universal fast backtracking method caps the results.
Catalog record
| CREATOR | Aaron Zoll, Benjamin Grimmer |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.01505
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Inexactly Smooth Performance Estimation and New Optimized Gradient Methods Aaron Zoll, Benjamin Grimmer Abstract We consider a general class of “inexactly smooth” convex functions, providing a universal model capturing as special cases L L -smooth, M M -Lipschitz, and Hölder smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results provide inexactly smooth functions with interpolation theorems that are necessary and sufficient up to modest universal constants. These enable analysis of first-order methods for any inexactly smooth convex problem class via solving convex Performance Estimation Problems (PEPs). Further, these enable the extension of Drori and Taylor [ 8 ] ’s constructive approach to algorithm design. From this, we derive an exactly minimax optimal method for ( β , 0 ) (\beta,0) -Hölder smooth problems, methods with the best-known convergence guarantees up to constants for any ( β , p ) (\beta,p) -Hölder smooth convex minimization, and a new universal fast backtracking method for any inexactly smooth convex problem. 1 Introduction First-order methods have found success in a wide range of convex optimization tasks, ranging from smooth minimization to nonsmooth minimization. First-order methods are particularly effective at modern, large-scale unconstrained optimization problems of the form f_{\star}=\min_{x\in\mathbb{R}^{d}}f(x) where computations of (sub)gradients remain tractable while other oracle models become expensive. Since the 1970s, algorithms tailored to the structure of the given problem class (smooth, nonsmooth, etc.) have been developed with highly optimized performance, often being minimax optimal. As classic examples, see [ 25 , 24 ] . Alas, these optimized methods are typically only guaranteed to be performant on their problem class, arising from tailored analysis techniques. Here, our goal is to develop analytic tools, in particular “Performance Estimation Problems,” uniformly applicable to algorithm design over a wide range of problem classes. To this end, we are motivated by the universal methods and analysis of [ 6 ] and [ 26 ] . Therein, they design first-order methods given access to a first-order oracle returning (f(x),g) with g\in\partial f(x) for any query x . Here \partial f(x)=\{g:f(y)\geq f(x)+\langle g,y-x\rangle\ \forall y\} denotes the convex subdifferential. In particular, they considered any convex problem with Hölder continuous subgradients, referred to here as (\beta,p) -Hölder smoothness, \|g_{x}-g_{y}\|\leq\beta\|x-y\|^{p}\qquad\forall x,y\in\mathbb{R}^{d},\ g_{x}\in\partial f(x),\ g_{y}\in\partial f(y) (1.1) with \beta>0 and p\in[0,1] . Nesterov’s Universal Fast Gradient Method [ 26 ] ensures f(x_{N})-f_{\star}\leq\frac{2^{1+2p}\beta\|x_{0}-x_{\star}\|^{1+p}}{N^{\frac{1+3p}{2}}} (1.2) universally, which is within a constant factor of the minimax optimal rate [ 23 ] for each p\in[0,1] . When p=1 , Hölder smoothness corresponds to the classical smoothness assumption of \beta=L -Lipschitz gradient. When p=0 , this class corresponds to functions with subgradients differing by at most \beta . This is closely related, but distinct, from the classical nonsmooth assumption of having M=\beta -Lipschitz function values. Considering p\in(0,1) interpolates between these settings. The key analysis tool leveraged by [ 6 ] and [ 26 ] is that Hölder smoothness ( 1.1 ) implies the inexact quadratic upper bound for all x,y\in\mathbb{R}^{d},\ g_{x}\in\partial f(x) and any \delta\geq 0 f(y)\leq f(x)+\langle g_{x},y-x\rangle+\frac{\left(\frac{1-p}{1+p}\cdot\frac{1}{2\delta}\right)^{\frac{1-p}{1+p}}\beta^{\frac{2}{1+p}}}{2}\|y-x\|^{2}+\delta. (1.3) This result allows one to approach any Hölder smooth setting with similar methods and proof techniques to the smooth setting ( p=1 ) where this bound holds without the additive error \delta . Such inexact bounds provide a means to universal designs. Generalizing this key analysis tool, here we propose a family of “inexactly smooth” functions. We say a convex function is L(\cdot) -inexactly smooth for some function L\colon[0,\infty)\rightarrow(0,\infty] , if for any x,y\in\mathbb{R}^{d} , g_{x}\in\partial f(x) , and \delta\geq 0 , f(y)\leq f(x)+\left\langle{g_{x}},{y-x}\right\rangle+\frac{L(\delta)}{2}\|y-x\|^{2}+\delta. (1.4) If L(\delta)=\left(\frac{1-p}{1+p}\cdot\frac{1}{2\delta}\right)^{\frac{1-p}{1+p}}\beta^{\frac{2}{1+p}} , this family contains all (\beta,p) -Hölder smooth functions. This can additionally model functions generated by sums of smooth and nonsmooth components, which have also received notable theoretical interest recently [ 16 , 31 , 17 , 7 ] . Given a sum f=f_{0}+f_{1} , with f_{0} having subgradients differ by at most \beta_{0} and f_{1} having \beta_{1} -Lipschitz gradient, inexact smoothness holds with L(\delta)=\beta_{1}+\beta_{0}^{2}/(2\delta) . Section 3 discusses more properties and examples within this model. In this paper, we develop a principled approach to the design and analysis of algorithms for inexactly smooth convex minimization. The foundational works of [ 9 ] and [ 30 , 29 ] introduced Performance Estimation Problems (PEPs) as a principled way to design and analyze first-order methods over traditional problem classes. See PEPit [ 14 ] and the many examples therein. PEPs are mathematical programs (often semidefinite programs) that compute a worst-case problem instance from a given class (e.g., L -smooth convex problems) for a given algorithm. Dually, PEPs provide a best possible convergence proof for a given algorithm using a given set of inequalities. Agreement of these primal and dual perspectives relies on related “Interpolation Theorems.” Kamri [ 32 , Chapter 4] provided a numerical study of some PEPs for Hölder smooth problems, without the analytical support of such theorems. Our Contributions. We show that interpolation, PEP, and the constructive approach to algorithm design of [ 8 ] all extend to inexactly smooth functions. Namely, • Calculus of Inexactly Smooth Functions In Section 2 , we derive characterizations of inexactly smooth functions and their conjugates, as well as associated calculus rules. • Interpolation Theory Section 3 begins by presenting necessary and sufficient conditions for observations to be interpolable by an inexactly smooth function. Theorem 3.3 gives our most general interpolation theory, which is tight up to a small universal constant. Theorem 3.5 establishes that these conditions are exact for (\beta,0) -Hölder smooth functions. • Inexactly Smooth Performance Estimation We conclude Section 3 by using our interpolation theory to define a convex formulation for analyzing the worst-case performance of an algorithm. Note, unlike most existing PEP work, these convex programs may not be semidefinite programs. Regardless, Theorem 3.6 establishes a strong duality result. • Algorithm Design Section 4 leverages our interpolation theory to construct optimized algorithms. Algorithm 1 is minimax optimal among (\beta,0) -Hölder smooth convex functions, Algorithm 2 is an asymptotically optimized gradient method for general Hölder smooth convex minimization, and Algorithm 3 is a universal method for any inexactly smooth convex problem requiring only input of a target accuracy \varepsilon and an iteration budget N . The associated convergence guarantees are given in Theorems 4.2 , 4.3 , and 4.5 , respectively. Note the inexactness considered here ( 1.4 ) is inexactness in attainment of smoothness-type quadratic upper bounds. This is distinct from inexactness due to gradient calculations, which have separately been studied in the PEP literature [ 22 , 4 , 5 , 13 ] . 2 Preliminaries and Inexactly Smooth Function Calculus We begin with preliminaries and then discuss Hölder smooth functions as our motivating instance of inexactly smooth functions in Section 2.1 . Then Section 2.2 develops a general calculus for L(\cdot) -inexactly smooth functions which may be of independent interest. Throughout, we consider closed, convex, proper functions f:\mathbb{R}^{d}\to(-\infty,\infty] . Let \left\langle{\cdot},{\cdot}\right\rangle denote the standard Euclidean inner product with the associated two-norm \|\cdot\| . We denote the domain of f by \mathrm{dom}(f) and its subdifferential as previously introduced by \partial f(x) . We denote \mathrm{epi}(f):=\{(x,t)\in\mathbb{R}^{d}\times\mathbb{R}:f(x)\leq t\} as the epigraph of f , for which the function f is convex if and only if the set \mathrm{epi}(f)