← All setups

Nonconvex Optimization with Symmetric Noise

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

f:Rd→R is differentiable with L-Lipschitz gradient and f(x0)−inff≤Δ; L,ε>0 and Λ,σ,Δ≥0. The jointly measurable, integrable oracle g is unbiased. IID samples supply paired evaluations (g(x,ξ),g(y,ξ)) with the same sample. For ζ(x,ξ)=g(x,ξ)−∇f(x), E∥ζ(x,ξ)∥≤σ, E∥ζ(x,ξ)−ζ(y,ξ)∥≤Λ∥x−y∥, and every coordinate of ζ(x,ξ) has a symmetric marginal law. Target: E∥∇f(xout)∥≤ε. Costs count primitive stochastic-gradient evaluations, including all median samples and batches; each paired query costs two evaluations.

Comparison for SymmetricFirstMomentNonconvex.
Result Oracle complexity Novelty Limitations
(1) MedianFirstMomentNonconvex (Ours) (⋆⋆) (review) O(ℓ2[1+LΔ+σ2ε2+ΛσΔε3])
(2) Median-of-three SGD; derived bound from (Ghadimi and Lan 2013, Cor. 2.2) O(1+LΔε2+LΔσ2ε4) (1): Stochastic term LΔσ2/ε4 becomes ℓ2ΛσΔ/ε3; smaller when εℓ2≪Lσ/Λ, σ2≳ε2. Median replacement plus centered dyadic analysis enables this gain. (1): Extra ℓ2 overhead and σ2/ε2 initialization; worse stochastic term when Λ≫Lσ/ε.
(3) NSGD-MVR (Fradin et al. 2026, Thm. 4.2, q=1) O(1+(σpε)p/(p−1)+(L+Λ)Δε2+ΛΔε2(σpε)p/(p−1)) (1): Scope extends to first moments only. On symmetric overlap, σ≤σp: accuracy exponent 2+p/(p−1)≥4 becomes 3, up to ℓ2, for fixed positive parameters and ε→0. (1) requires coordinatewise symmetry. (3) requires E∥ζ(x,ξ)∥p≤σpp, 1<p≤2, but permits asymmetric noise.
(4) Median-of-three SPIDER; derived bound from (Fang et al. 2018, Thm. 1)

O(1+L¯σΔε3+σ2ε2+σε), 0<ε≤σ.

Special case: E∥g(x,ξ)−g(y,ξ)∥2≤L¯2∥x−y∥2.

(1): Scope includes infinite second-moment increments. On overlap, L≤L¯, Λ≤2L¯: matches the ε−3 power; coupling term improves when Λℓ2≪L¯. (1) pays ℓ2 overhead on the common setup; no uniform total-cost improvement.

Abbr: ℓ=log⁡(2+LΔ/ε2); expectations use the sampling law and any output randomization. σp is the pth central-moment scale; L¯ is the raw mean-squared smoothness constant. Median-of-three means the coordinatewise median of three independent samples.

Fang, Cong, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. 2018. “SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator.” Advances in Neural Information Processing Systems 31. https://proceedings.neurips.cc/paper_files/paper/2018/hash/1543843a4723ed2ab08e18053ae6dc5b-Abstract.html.
Fradin, Adrien, Abdurakhmon Sadiev, Laurent Condat, and Peter Richtárik. 2026. Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2512.18713.
Ghadimi, Saeed, and Guanghui Lan. 2013. Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming. https://doi.org/10.48550/arXiv.1309.5549.

Lean setup