← All setups

Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Convex Minimization

We consider minimizing a convex function f:E→R on a real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1>0, and has an everywhere differentiable gradient. A given starting point x0∈E lies within distance R>0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For a tolerance ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives only E, L0, L1, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convexity). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Generalized smoothness). The function f and its gradient ∇f:E→E are Fréchet differentiable everywhere. The Hessian ∇2f(x):E→E satisfies ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈E.

Assumption 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. Here x⋆ is fixed independently of the algorithm’s randomness; all global minimizers have the same objective value.

Results

Convex f on a real Hilbert space has a differentiable gradient satisfying ∥∇2f(x)∥≤L0+L1∥∇f(x)∥ and a minimizer x⋆ with ∥x0−x⋆∥≤R; L0,L1,R,ε>0. Exact gradient access; target f(x^)−f(x⋆)≤ε almost surely. The constructed method receives x0,L0,L1, but neither R nor ε; the setup imposes no algorithm restriction.

Radius-only generalized-smooth convex optimization (RadiusOnlyGeneralizedSmoothConvex).
Result Oracle complexity Novelty Limitations
(1) RadiusFreeGeneralizedAccelerated (Ours) (⋆⋆) (review) O(L0R2/ε+(1+q)log⁡(2+q))
(2) SHERPA+CRUISE (Rudomanov et al. 2026), Thm. 3.7 O(L0R2/ε+(1+q)log⁡(2+q)) (1): Matches known rate; needs neither R nor ε, valid at every budget beyond threshold. Doubling may recover this adaptivity. (1): Larger proved numerical constants.
(3) (Tyurin 2026), Thm. 4.3; finite-dimensional restriction; R¯≥R, Γ0≥2Δ/∥x0−x⋆∥2 O(1+L0R2/ε
+L1R¯log+min{L12R¯2Γ0L0,Γ0R2ε}
+log+⁡(Γ0/L0))
(1): No R¯,Γ0 inputs. For q≫1, R¯=R, Γ0≍Δ/R2, Δ≍L0eq/L12: O(L0R2/ε+qlog⁡q) versus O(L0R2/ε+q2) when q2≳L0R2/ε.
(4) Backtracking accelerated (LongTails, n.d.) O(L0R2/ε
+(1+q)log[2+(1+q)2(1+a−1+a+L12ΔL0(1+a))])
(1): Removes gap dependence. For a≍1, Δ≍L0eq/L12, q≫1, replaces q2 by qlog⁡q; material when q2≳L0R2/ε. (1) needs L0,L1; (4) does not.

Abbr: q=L1R; Δ=f(x0)−f(x⋆) (or an upper bound); a=L0h0, with initial trial step h0>0; log+⁡t=max{0,log⁡t}. R¯ is a supplied radius bound and Γ0>0 an initial curvature parameter. Costs count all gradient calls, including probes and trials.

LongTails: BacktrackingGeneralizedAccelerated. n.d. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/BacktrackingGeneralizedAccelerated.lean.
Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026. Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization Under (L0,L1)-Smoothness. https://arxiv.org/abs/2610.21461v1.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://arxiv.org/abs/2508.06884v2.

Lean setup