← All setups

Holder Noise Minimax Lower Bound — 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 a differentiable, possibly nonconvex function f:Rd→R with L-Lipschitz gradient, where d≥1 and L>0. A given point x0 satisfies f(x0)−infxf(x)≤Δ, where Δ≥0. Each oracle call at (x,y) returns (g(x,ξ),g(y,ξ)) using a fresh independent binary sample ξ. The estimator g is unbiased, with variance at most σ2 and centered increments of mean square at most M∥x−y∥2ν, where σ,M≥0, 0<ν≤1, and ∥⋅∥ is the Euclidean norm. For ε>0, the goal is a measurable output x¯ satisfying EP∥∇f(x¯)∥≤ε, where P is the joint law of sampling and independent algorithm randomness.

The underlying optimization problem is infx∈Rdf(x). The algorithm receives d,L,M,ν,σ,Δ,ε, and x0∈Rd. We restrict these parameters further to 64ε2≤LΔ,d≥⌈230(1+LΔε2)3(1+σ2ε2)⌉.

Our assumptions:

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

Assumption 2 (Unbiased gradients and Hölder noise). There exist a probability distribution p on {0,1} and a jointly measurable map g:Rd×{0,1}→Rd. Define the centered error by e(x,ξ)=g(x,ξ)−∇f(x). For every x,y∈Rd, Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p∥e(x,ξ)∥2≤σ2,Eξ∼p∥e(x,ξ)−e(y,ξ)∥2≤M∥x−y∥2ν. Here g(x,⋅) is Bochner integrable, and both squared norms in these expectations are integrable under p.

The sample sequence (ξk)k≥0 consists of measurable, mutually independent random variables with common law p, independent of the algorithm’s randomness. On call k, the algorithm may query any pair (xk,yk)∈Rd×Rd, based on its randomness and previous replies. The oracle returns (g(xk,ξk), g(yk,ξk)). Thus the two replies share a sample, and each such pair counts as one oracle call.

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

Proved result

⌊L⋅Δ+σ2ε2+min{L⋅Δ⋅σ2ε4,Δε3⋅max{M⋅(Lε)1−2⋅ν,M1ν⋅12⋅σ2−1ν}}280⌋+

OracleTemplate.NonConvergence LongTails.Setups.HolderNoiseNonconvexLower.spec
  OracleTemplate.HolderNoiseMinimaxLowerBound.budget

Relevant previous results

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