← All setups

Nonconvex Optimization with ABC Noise

Descriptions may be stale. Consult the linked Lean sources.

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¯)∥]≤ε.

Results

A differentiable, possibly nonconvex function f on a separable real Hilbert space with its Borel measurable structure has L-Lipschitz gradient, finite infimum f∗, and f(x0)−f∗≤Δ. Samples are IID with probability law p; the jointly measurable oracle satisfies ∫g(x,ω)dp(ω)=∇f(x) and ∫∥g(x,ω)−∇f(x)∥2dp(ω)≤2A(f(x)−f∗)+B∥∇f(x)∥2+C, with integrable oracle values and squared errors. Here L,ε>0 and A,B,C,Δ≥0. The target is ∫∥∇f(xout(ω))∥dP(ω)≤ε.

Sufficient stochastic-gradient budgets for AbcNoiseNonconvex.
Result Oracle complexity Novelty Limitations
(1) AbcNoiseSgdUpperBound (Ours) (review) O(1+LΔ(1+B)ε2+LΔ(AΔ+C)ε4); constant-step SGD, uniformly sampled iterate.
(2) SGD (Khaled and Richtárik 2020), Cor. 1 and Lemma 2; E=Rd. O(1+LΔ(1+B)ε2+LΔ(AΔ+C)ε4); Bpaper=1+B. (1): Matches known rate and tuning knowledge; Hilbert-space formalization. Uniform sampling already follows from Lemma 2 at constant cost. (1): Larger displayed constants on the (1+B) and C terms.
(3) RSG (Ghadimi and Lan 2013), Cor. 2.2; special case E=Rd, A=B=0, C=σ2. O(1+LΔε2+LΔσ2ε4). (1): Scope: ABC noise instead of bounded variance, already covered by (2). Matches known rate on A=B=0.

Abbr: P is the execution probability law, including output randomization; xout is the returned point; σ2=C in (3). Costs count individual stochastic-gradient calls; O hides only universal constants.

Ghadimi, Saeed, and Guanghui Lan. 2013. “Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming.” SIAM Journal on Optimization 23 (4): 2341–68. https://doi.org/10.1137/120880811.
Khaled, Ahmed, and Peter Richtárik. 2020. Better Theory for SGD in the Nonconvex World. https://doi.org/10.48550/arXiv.2002.03329.

Lean setup