← All setups

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

Descriptions may be stale. Consult the linked Lean sources.

Gap-Constrained Generalized Smooth Convex Minimization · Lean proof

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.

Proved result

⌊L0⋅R2ε+min{L1⋅R1+log⁡(2+L1⋅R),(L1⋅R⋅log⁡(Δ8⋅ε)1+log⁡(2+L1⋅R))23}16777216⌋+

OracleTemplate.NonConvergence LongTails.Setups.GapGeneralizedSmoothConvex.spec
  LongTails.Theorems.GapGeneralizedSmoothConvexLowerBound.budget

Relevant previous results

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