← All setups

Median First Moment Nonconvex — Nonconvex Optimization with Symmetric Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Symmetric Noise · Lean proof

Nonconvex Optimization with Symmetric Noise

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R, where d is a nonnegative integer. Its gradient is L-Lipschitz, with L>0, and a given point x0∈Rd satisfies f(x0)−infxf(x)≤Δ, with Δ≥0. Each oracle call returns unbiased stochastic gradients at two queried points using one shared sample, independently across calls. The noise has symmetric coordinate marginals, a bounded first moment, and Lipschitz dependence on the query in mean norm. For ε>0, the goal is a measurable output x¯∈Rd with E∥∇f(x¯)∥≤ε, averaging over sampling and algorithm randomness.

The optimization problem is infx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. Let Ω be a measurable sample space, and let Λ,σ≥0 denote the noise regularity and first-moment bounds, respectively. The algorithm receives d, Ω with its measurable structure, L, Λ, σ, Δ, ε, and x0; the objective is accessed through the oracle.

Our assumptions:

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

Assumption 2 (Symmetric first-moment noise). There exist a probability measure p on Ω and a jointly measurable map g:Rd×Ω→Rd. For every x∈Rd, the map g(x,⋅) is Bochner integrable under p. Define the noise by e(x,ω)=g(x,ω)−∇f(x). For all x,y∈Rd, Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p∥e(x,ξ)∥≤σ,Eξ∼p∥e(x,ξ)−e(y,ξ)∥≤Λ∥x−y∥. Each coordinate marginal of the noise is symmetric about zero: for every x∈Rd and i∈{1,…,d}, ei(x,ξ)=law−ei(x,ξ),ξ∼p.

At call k≥0, the algorithm may query any pair (xk,yk)∈Rd×Rd, and the oracle returns (g(xk,ξk),g(yk,ξk)). The sample variables (ξk)k≥0 are measurable, mutually independent, and each has law p. They are independent of the algorithm’s randomness. Both replies in a pair use the same sample, and one such paired query counts as one oracle call.

After the allotted calls, the output x¯ must be measurable and ∥∇f(x¯)∥ must be integrable, with EP[∥∇f(x¯)∥]≤ε, where P is the joint law of the samples and the independent algorithm randomness.

Proved result

3⋅⌈14400⋅(1+log2⁡(2+16⋅L⋅Δε2))2⋅(1+L⋅Δ+σ2ε2+Λ⋅σ⋅Δε3)⌉+

OracleTemplate.Convergence LongTails.Setups.SymmetricFirstMomentNonconvex.spec OracleTemplate.MedianGradient.budget

Relevant previous results

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