← All setups

Gd Nonconvex — Smooth Nonconvex Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Smooth Nonconvex Stationarity · Lean proof

Smooth Nonconvex Stationarity

We consider a differentiable, possibly nonconvex function f:E→R on a real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given starting point x0∈E satisfies f(x0)−ℓ≤Δ for a global lower bound ℓ∈R and Δ≥0. The oracle returns ∇f(x) at x. For a tolerance ε>0, the goal is a measurable output x¯∈E with integrable squared gradient norm satisfying EP[∥∇f(x¯)∥2]≤ε2, where P is the law of the algorithm’s randomness.

We seek approximate stationarity for the optimization problem infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with a measurable structure. The algorithm receives E, L, Δ, ε, and x0; the objective is accessed through the oracle.

Our assumptions:

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

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

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable with respect to the given measurable structure on E, and must satisfy EP[∥∇f(x¯)∥2]<∞,EP[∥∇f(x¯)∥2]≤ε2.

Proved result

max{1,⌈2⋅L⋅Δε2⌉+}

OracleTemplate.Convergence LongTails.Setups.SmoothNonconvex.spec OracleTemplate.NonconvexGradient.budget

Relevant previous results