← All setups

Gap-Constrained Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Gap-Constrained Generalized Smooth Convex Minimization

We consider minimizing a convex function f:Rd→R in a prescribed high-dimensional regime. The function f is (L0,L1)-smooth, with L0>0 and L1≥0, and has a differentiable gradient. A given point x0∈Rd satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆, where R,Δ>0. The oracle returns ∇f(x) at x. Given ε>0, the goal is an output x¯∈Rd 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, and ∥⋅∥op denotes its induced operator norm. The parameters satisfy d∈N,L0>0,L1≥0,R>0,0<ε≤L0R216,16ε≤Δ,d≥⌈280(1+L1R+L0R2ε)10⌉. The algorithm receives d,L0,L1,x0,R,Δ, and ε.

Our assumptions:

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

Assumption 2 (Generalized smoothness). The function f is Fréchet differentiable everywhere, its gradient is Fréchet differentiable everywhere, and ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈Rd.

Assumption 3 (Initial distance and objective gap). There exists 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 oracle calls, the output must have an integrable objective gap and satisfy EP[f(x¯)−f(x⋆)]≤ε. The minimizer x⋆ is fixed independently of the algorithm’s randomness; all global minimizers have the same objective value.

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⋆)≤Δ. Here L0,R,ε>0, L1≥0, ε≤L0R2/16, Δ≥16ε, and d≥⌈280(1+L1R+L0R2/ε)10⌉. Unrestricted randomized algorithms receive exact gradients. The target is integrable loss with ∫[f(x^(ω))−f(x⋆)]dP(ω)≤ε, for the algorithm’s probability law P. All rows are lower bounds (necessary budgets).

Necessary query budgets for GapGeneralizedSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) GapGeneralizedSmoothConvexLowerBound (Ours) (⋆⋆⋆) (review) Necessary: Ω(s+min{q/w,(qh/w)2/3}) gradient queries.
(2) (Rudomanov et al. 2026), Thm. B.3 Ω(s+[qlog⁡(2+q2/s2)]2/3) value–gradient queries. Deterministic; hard-instance gap <4ε, hence valid for every Δ≥4ε. (1): Randomized hardness with gap dependence. For fixed s, Δ/ε=eqβ, 0<β<1/2, strengthens Ω(q2/3/w2/3) to Ω(q2(1+β)/3/w2/3). Polynomial Δ/ε gives only logarithmic gains; none when s dominates. (1): gradients only; larger dimension instead of 2n for n−1 queries; weaker leading constant.
(3) (Rudomanov et al. 2026), Thm. 4.10 Ω(s+q/w) value–gradient queries. Deterministic, radius-only class; no prescribed initial-gap bound. (1): Scope covers prescribed Δ≥16ε and randomized algorithms. (3) transfers only when Δ admits its hard instances; no moderate-gap rate comparison. On that common large-gap regime, (1) has q/w instead of q/w: weaker by w when transient terms dominate. Gradients only; larger dimension.
(4) (LongTails, n.d.-a) Ω(s+q/w) gradient queries. Randomized, radius-only class; d≥⌈244(1+q+s)5⌉. (1): Scope establishes bounded-gap hardness for every Δ≥16ε; matches (4) when h≳q/w. (4) supplies no moderate-gap guarantee. (1) requires dimension exponent 10 instead of 5.
(5) (LongTails, n.d.-b) Ω(s) gradient queries. Randomized, L0-smooth radius-only subclass; ε≤L0R2/218, d≥216(⌊s/512⌋+1)5. (1): Adds generalized-smooth bounded-gap hardness: min{q/w,(qh/w)2/3} strengthens s when larger, including constant Δ/ε. At L1=0, matches known rate. (1) requires larger dimension.

Abbr: s=L0R2/ε, q=L1R, w=1+log⁡(2+q), h=log⁡(Δ/ε); n is the prior chain length; Ω denotes a necessary query budget up to universal factors; log is natural.

LongTails: FullGeneralizedSmoothConvexLowerBound. n.d.-a. Repository lower-bound theorem and necessary oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/FullGeneralizedSmoothConvexLowerBound.lean.
LongTails: SmoothConvexExpectedLowerBound. n.d.-b. Repository lower-bound theorem and necessary oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/SmoothConvexExpectedLowerBound.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