← All setups

Gap Smooth Strong Growth High Probability — Gap-Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Gap-Smooth Convex Minimization · Lean proof

Gap-Smooth Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. A local quadratic upper model has curvature controlled by the gap to a global minimizer x⋆, and a given starting point has bounded distance and objective gap to that minimizer. The oracle returns independent-sample, unbiased stochastic gradients whose variance is bounded proportionally to the squared gradient norm. For tolerance ε>0 and failure probability δ∈(0,1), the goal is a measurable output x¯∈E satisfying P{f(x¯)−f(x⋆)>ε}≤δ, where P is the joint law of sampling and independent algorithm randomness.

The optimization problem is minx∈Ef(x). Equip E with its Borel sigma-algebra, and write ∥⋅∥ for the norm induced by its inner product. Let Ω be a measurable sample space and x0∈E the given starting point. The parameters satisfy H0≥0,H1≥0,R>0,Δ>0,ρ≥1,0<ε≤Δ,0<δ<1. The algorithm receives E, Ω, x0, and all seven parameters H0,H1,R,Δ,ρ,ε,δ.

Our assumptions:

Assumption 1 (Convexity and initialization). The function f is Fréchet differentiable everywhere on E and satisfies f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,t∈[0,1]. There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 2 (Gap-dependent upper model). For every x,y∈E satisfying (23+6)H1∥y−x∥≤1, the objective obeys f(y)≤f(x)+⟨∇f(x),y−x⟩+(H0+H1(f(x)−f(x⋆)))∥y−x∥2.

Assumption 3 (Strong-growth stochastic oracle). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−∇f(x)∥2 is integrable under ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤(ρ−1)∥∇f(x)∥2. At call k≥0, a query x∈E receives g(x,ξk), where the measurable samples (ξk)k≥0 are mutually independent with common law ν. Algorithm randomness is independent of the entire sample sequence.

After the allotted oracle calls, the algorithm must return a measurable output x¯∈E with P{f(x¯)−f(x⋆)>ε}≤δ.

Proved result

⌈134217728⋅(1+−log⁡(δ))⋅((1+R⋅H1)⋅log⁡(1+Δε)+R⋅H0ε)⌉+⋅⌈ρ⌉+

OracleTemplate.Convergence LongTails.Setups.GapSmoothStrongGrowth.spec OracleTemplate.GapStrongGrowth.budget

Relevant previous results

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