← All setups

Recursive Momentum Affine Variance — Stationarity with Affine Gradient Variance

Descriptions may be stale. Consult the linked Lean sources.

Stationarity with Affine Gradient Variance · Lean proof

Stationarity with Affine Gradient Variance

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is Lipschitz, and its objective gap from a given point is bounded. Stochastic gradients are unbiased, have variance bounded by an affine function of the squared gradient norm, and satisfy mean-squared Lipschitz continuity. At queried points x,y∈E, the oracle returns (g(x,ξ),g(y,ξ)), where g is the stochastic gradient map and ξ is a fresh sample shared within the pair. For ε>0, the goal is a measurable output x¯∈E with EP∥∇f(x¯)∥≤ε, where P is the joint law of algorithm and oracle randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which carries its Borel sigma-algebra. Let Ω be a measurable sample space. The algorithm receives E, Ω, the given point x0∈E, and the parameters L>0,L―,Γ,Λ,Δ≥0,ε>0. It accesses the objective through the oracle described below.

Our assumptions:

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

Assumption 2 (Unbiasedness and affine variance). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For each x∈E, the map g(x,⋅) is Bochner integrable under ν, and ∥g(x,⋅)−∇f(x)∥2 is integrable under ν. They satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤Γ2∥∇f(x)∥2+Λ2.

Assumption 3 (Mean-squared smoothness). For every x,y∈E, the function ∥g(x,⋅)−g(y,⋅)∥2 is integrable under ν, and Eξ∼ν[∥g(x,ξ)−g(y,ξ)∥2]≤L―2∥x−y∥2.

The oracle uses a sequence (ξk)k≥0 of measurable, independent samples, each with law ν, independent of the algorithm’s randomness. On call k, a query (x,y)∈E×E receives (g(x,ξk),g(y,ξk)). Each such paired reply counts as one oracle call; both evaluations use the same sample. Queries may be chosen adaptively anywhere in E×E.

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

Proved result

⌈16+131⋅Γ2+5⋅Γ4+516⋅Λ2ε2+64⋅(L+Lbar)⋅(1+3⋅Γ)⋅Δε2+384⋅(L+Lbar)⋅Λ⋅Δε3⌉++2

OracleTemplate.Convergence LongTails.Setups.AffineVarianceMeanSquaredSmooth.spec OracleTemplate.RecursiveMomentum.budget

Relevant previous results

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