← All setups

Normalized Storm Expected Smoothness — Nonconvex Optimization with Expected Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Expected Smoothness · Lean proof

Nonconvex Optimization with Expected Smoothness

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is Lipschitz, and a given starting point has bounded objective gap above a global lower bound. The oracle returns two unbiased stochastic gradients evaluated at queried points using a shared sample, with independent samples across calls. Their mean-square difference is bounded by squared query distance, and their variance grows at most linearly with the objective gap. For ε>0, the goal is a measurable output x¯∈E satisfying EP[∥∇f(x¯)∥]≤ε, where P is the joint law of sampling and independent algorithm randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which carries its Borel sigma-algebra. Fix a measurable sample space Ω, a starting point x0∈E, and parameters L>0,A≥0,C≥0,Δ≥0,ε>0. The algorithm receives E, Ω, L, A, C, Δ, ε, and x0; the objective, sampling distribution, and lower bound are accessible only through the stated oracle information.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Lower bound and initial gap). There exists flow∈R such that flow≤f(x)for every x∈E,f(x0)−flow≤Δ.

Assumption 3 (Unbiasedness and expected smoothness). 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 Eξ∼ν[g(x,ξ)]=∇f(x). For every x,y∈E, both ∥g(x,ξ)−∇f(x)∥2 and ∥g(x,ξ)−g(y,ξ)∥2 are integrable under ν, with Eξ∼ν[∥g(x,ξ)−g(y,ξ)∥2]≤L2∥x−y∥2,Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤2A(f(x)−flow)+C.

At call k, a query (x,y)∈E×E returns (g(x,ξk),g(y,ξk)). The measurable random variables (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness. Both replies within a call use the same sample. Each such paired query counts as one oracle call.

After the allotted calls, the output x¯ must be measurable, its gradient norm must be integrable under P, and it must satisfy EP[∥∇f(x¯)∥]≤ε.

Proved result

⌈192⋅(4⋅A⋅Δ+C)+80⋅L⋅Δε2+384⋅AL+1600⋅L⋅Δ⋅4⋅A⋅Δ+2⋅A⋅ε2L+Cε3⌉++3

OracleTemplate.Convergence LongTails.Setups.ExpectedSmoothnessNonconvex.spec OracleTemplate.NormalizedStorm.budget

Relevant previous results

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