← All setups

Dyadic Variance Reduction Holder — Mean-Squared Hölder Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Mean-Squared Hölder Nonconvex Optimization · Lean proof

Mean-Squared Hölder Nonconvex Optimization

We consider finding an approximate stationary point of a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. At a pair x,y∈E, the oracle returns unbiased gradient estimates g(x,ξ),g(y,ξ) using one shared sample ξ, with independent samples across calls. Their variance is bounded by σ2, and their mean-squared difference by M∥x−y∥2ν, where σ,M≥0 and ν∈[1/2,1]. For ε>0, the goal is a measurable output x¯∈E with E∥∇f(x¯)∥≤ε, averaging over oracle and independent algorithm randomness.

The underlying optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, the measurable sample space Ω, x0, and all parameters L,M,ν,σ,Δ,ε.

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 (Unbiased stochastic gradients). There exist a probability measure p on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼p, with Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤σ2.

Assumption 3 (Mean-squared Hölder continuity). For every x,y∈E, the random variable ∥g(x,ξ)−g(y,ξ)∥2 is integrable under ξ∼p, and Eξ∼p[∥g(x,ξ)−g(y,ξ)∥2]≤M∥x−y∥2ν.

At call k≥0, a query (xk,yk)∈E×E receives the pair (g(xk,ξk),g(yk,ξk)). The measurable samples (ξk)k≥0 are mutually independent with common law p, and are independent of the algorithm’s randomness. Both evaluations within a pair use the same sample; one returned pair counts as one oracle call. Queries may depend on preceding replies.

After the allotted calls, the output x¯ must be measurable, its gradient norm must be integrable, and it must satisfy EP[∥∇f(x¯)∥]≤ε, where P is the joint law of the oracle samples and the algorithm’s randomness.

Proved result

⌈800⋅(1+log2⁡(2+16⋅L⋅Δε2))2⋅(1+L⋅Δ+σ2ε2+Δ⋅M1ν⋅12⋅σ2−1νε3)⌉+

OracleTemplate.Convergence LongTails.Setups.MeanSquaredHolderNonconvex.spec OracleTemplate.DyadicHolder.budget

Relevant previous results

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