← All setups

Known-Gap Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Known-Gap Generalized Smooth Convex Minimization

We consider minimizing a differentiable convex function f:Rd→R, where d is a positive integer. The function f is (L0,L1)-smooth, with L0>0 and L1>0: its differentiable gradient satisfies ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥ everywhere. A given point x0 satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆, with R,Δ>0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯ with integrable objective gap satisfying EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean norm on Rd and its induced operator norm on linear maps. The algorithm receives d,L0,L1,x0,R,Δ, and ε.

Our assumptions:

Assumption 1 (Parameter regime and dimension). The parameters satisfy L0>0,L1>0,R>0,ε>0,16ε≤L0R2,L1R≥220, and Δ≥ε(2+L1R)2,Δ≥εL0R2ε,d≥⌈246(1+L1R+L0R2ε)6⌉.

Assumption 2 (Convexity and generalized smoothness). The function f is differentiable everywhere, and, for every x,y∈Rd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). Its gradient is Fréchet differentiable everywhere and satisfies ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈Rd. Here ∇2f(x) is a linear operator from Rd to Rd.

Assumption 3 (Initial distance and objective gap). There exists a global minimizer x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Queries may be made at any point of Rd. After the allotted gradient calls, the output x¯∈Rd must have an integrable objective gap under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Results

Convex f:Rd→R has differentiable gradient satisfying ∥∇2f(x)∥≤L0+L1∥∇f(x)∥, and a minimizer x⋆ with ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ. All parameters are public; access is to exact gradients, with no algorithm restriction. The setup requires L0,L1,R,ε>0, 16ε≤L0R2, L1R≥220, Δ≥εmax{(2+L1R)2,L0R2/ε}, and d≥⌈246(1+L1R+L0R2/ε)6⌉. Target: integrable gap with ∫[f(x^(ω))−f(x⋆)]dP(ω)≤ε under the execution probability law P. Result (2) constructs a deterministic output. The paired bounds retain a gap: Λ versus Λ2/3 in their gap branches, and logarithms in q.

Known-gap generalized-smooth convex optimization: necessary and sufficient budgets for GeneralizedSmoothConvexKnownGapPolynomialDimension.
Result Oracle complexity Novelty Limitations
(1) KnownGapGeneralizedSmoothLowerBound (Ours) (⋆⋆⋆) (review) Ω(L0R2/ε+min{(qΛ)2/3,q}log⁡(2+q))
(2) KnownGapGeneralizedSmoothUpperBound (Ours) (review) O(L0R2/ε+min{q2/3Λ,qlog⁡(2+q)})
(3) (Rudomanov et al. 2026), Thm. B.3 Ω(L0R2/ε+[qlog⁡(2+q2/A)]2/3); deterministic (f,∇f) oracle; hard instances have gap <4ε. (1): randomized expected-gap hardness; stronger q-term for log⁡(2+q)≪Λ≤q. At Λ=q1/3: q8/9/log⁡(2+q) instead of at most q2/3. (1): gradient-only hardness; stated large-q, gap and polynomial-dimension restrictions, versus dimension 2n for n−1 calls.
(4) (LongTails, n.d.-b), radius-only lower bound Ω(q/log⁡(2+q)); randomized gradient oracle; L0/L12≤ε≤L0R2/16, q≥220, d≥⌈244(1+q)5⌉. (1): adds L0R2/ε and known-gap interpolation, including Δ≤εeq/log⁡(2+q). Radius-only hardness does not establish hardness at prescribed Δ. (1): stronger dimension restriction. Rates are not comparable without a common gap restriction on hard instances.

Abbr: q=L1R, Λ=log⁡(Δ/ε), ℓ=log⁡(2+L0R2/ε+L1R); log is natural. Costs count all primitive oracle calls, including line-search trials. Ω denotes a necessary budget, O a sufficient budget; (f,∇f) returns a value and gradient together. n is the chain-length parameter in (3).

GeneralizedSmoothConvexKnownGapPolynomialDimension (continued).
Result Oracle complexity Novelty Limitations
(5) (Rudomanov et al. 2026), Thm. B.7(b) O((L0R2/ε+q2/3Λ2/3)ℓ) on the shared regime; gradients, known Δ. (2): removes ℓ from L0R2/ε; gap-branch term decreases when Λ1/3<ℓ. Gains already hold in (7). (2): gap branch can lose Λ1/3/ℓ when Λ1/3>ℓ; narrower stated regime.
(6) (Rudomanov et al. 2026), Thm. 3.7 O(L0R2/ε+qlog⁡(2+q)) on the shared regime; gradients, no gap bound. (2): matches radius-branch rate; smaller total order if L0R2/ε=o(qlog⁡(2+q)) and Λ=o(q1/3log⁡(2+q)). (2): selection additionally uses Δ; narrower stated regime.
(7) Derived bound (LongTails, n.d.-a, n.d.-c) O(L0R2/ε+min{q2/3Λ,qlog⁡(2+q)}) on the shared regime; select the cheaper existing gradient budget. (2): matches known rate; formal upper-bound companion to (1). (2): narrower finite-dimensional regime; selection uses R,ε, which radius-only updates do not require.

Abbr: q=L1R, Λ=log⁡(Δ/ε), ℓ=log⁡(2+L0R2/ε+L1R); log is natural. Costs count all primitive oracle calls, including line-search trials. Ω denotes a necessary budget, O a sufficient budget; (f,∇f) returns a value and gradient together. n is the chain-length parameter in (3).

LongTails: GeneralizedAcceleratedConvex. n.d.-a. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/GeneralizedAcceleratedConvex.lean.
LongTails: PolynomialDimensionGeneralizedSmoothLowerBound. n.d.-b. Repository lower-bound theorem and necessary oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/PolynomialDimensionGeneralizedSmoothLowerBound.lean.
LongTails: RadiusFreeGeneralizedAccelerated. n.d.-c. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/RadiusFreeGeneralizedAccelerated.lean.
Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026. Descending Everest, Part I: Oracle Complexity of Convex Optimization Under (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2610.21461.

Lean setup