← All setups

Holder Noise Minimax Upper — Nonconvex Optimization with Hölder Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Hölder Noise · Lean proof

Nonconvex Optimization with Hölder Noise

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, with Δ≥0. Each oracle call returns unbiased gradients at two queried points using one shared sample, with independent samples across calls. The centered noise has variance at most σ2 and mean-square Hölder increments bounded by M∥x−y∥2ν, where σ,M≥0 and 0<ν≤1. The goal is a measurable output x¯∈E satisfying E∥∇f(x¯)∥≤ε, where ε>0 and expectation includes sampling and algorithm randomness.

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

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is Fréchet differentiable everywhere, and 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 (Hölder noise increments). Define the centered noise by ζ(x,ξ)=g(x,ξ)−∇f(x). For every x,y∈E, the squared increment ∥ζ(x,ξ)−ζ(y,ξ)∥2 is integrable under ξ∼p and satisfies Eξ∼p[∥ζ(x,ξ)−ζ(y,ξ)∥2]≤M∥x−y∥2ν.

At call k, a query (xk,yk)∈E×E receives (g(xk,ξk),g(yk,ξk)). The sample sequence (ξk)k≥0 consists of measurable, mutually independent random variables with common law p. Algorithm randomness is independent of the entire sample sequence. Queries may depend on earlier replies, and each paired reply counts as one oracle call.

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

Proved result

⌈min{600⋅(1+L⋅Δ+σ2ε2+L⋅Δ⋅σ2ε4),3200⋅(1+log2⁡(2+16⋅L⋅Δε2))2⋅(1+L⋅Δ+σ2ε2+Δε3⋅max{M⋅(Lε)1−2⋅ν,M1ν⋅12⋅σ2−1ν})}⌉+

OracleTemplate.Convergence LongTails.Setups.HolderNoiseNonconvex.spec OracleTemplate.HolderNoiseMinimaxUpper.budget

Relevant previous results

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