← All setups

Abc Noise Sgd Upper Bound — Nonconvex Optimization with ABC Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with ABC Noise · Lean proof

Nonconvex Optimization with ABC Noise

We consider a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E, with L-Lipschitz gradient for L>0 and finite infimum f⋆. A given point x0∈E satisfies f(x0)−f⋆≤Δ, where Δ≥0. At x, the oracle returns an unbiased vector g(x,ξ) using fresh independent samples ξ with common law ν; its noise second moment is at most 2A(f(x)−f⋆)+B∥∇f(x)∥2+C, where A,B,C≥0. For ε>0, the goal is a measurable output x¯∈E with EP∥∇f(x¯)∥≤ε, where P is the joint law of oracle and independent algorithm randomness.

The underlying optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Let Ω be a measurable sample space. The algorithm receives E, Ω, L>0, A,B,C,Δ≥0, ε>0, and x0; the objective and its oracle distribution are accessed through oracle replies.

Our assumptions:

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

Assumption 2 (Finite infimum and initial gap). There exists f⋆∈R such that f⋆=infx∈Ef(x),f(x0)−f⋆≤Δ.

Assumption 3 (Independent unbiased oracle with ABC noise). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤2A(f(x)−f⋆)+B∥∇f(x)∥2+C. The sample sequence (ξk)k≥0 has a joint probability law Q on ΩN: its coordinate maps are measurable, mutually independent, and each has law ν. At the kth query x∈E, the oracle returns g(x,ξk). Algorithm randomness is independent of this sample sequence.

Queries may be made at any point of 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

⌈144⋅L⋅Δ⋅(1+B+A⋅Δε2+Cε2)ε2⌉++1

OracleTemplate.Convergence LongTails.Setups.AbcNoiseNonconvex.spec LongTails.Theorems.AbcNoiseSgdUpperBound.budget

Relevant previous results

  • Ahmed Khaled and Peter Richtárik. Better Theory for SGD in the Nonconvex World. 2020 (preprint v3). Complexity: O(1+LΔε2max{1+B,AΔε2,Cε2}) stochastic-gradient oracle calls with a fixed budget, using SGD, for E∥∇f(xout)∥≤ε.