← All setups

Known Gap Generalized Smooth Lower Bound — Known-Gap Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Known-Gap Generalized Smooth Convex Minimization · Lean proof

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⋆)]≤ε.

Proved result

⌊max{L0⋅R2ε8192,min{(L1⋅R⋅log⁡(Δε))23,L1⋅R}2048⋅log⁡(2+L1⋅R)}⌋+

OracleTemplate.NonConvergence LongTails.Setups.GeneralizedSmoothConvexKnownGapPolynomialDimension.spec
  LongTails.Theorems.KnownGapGeneralizedSmoothLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.