← All setups

Heavy-Tailed Two-Point Zeroth-Order Optimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Two-Point Zeroth-Order Optimization

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R, where d≥1, with a lower bound ℓ∈R and given starting point x0 satisfying f(x0)−ℓ≤Δ, where Δ≥0. The oracle returns two scalar values F(x,ξ) and F(y,ξ) using a shared sample ξ∼ν, with independent samples across calls. Each sample function F(⋅,ξ) has an L-Lipschitz gradient, where L>0; these gradients are unbiased for ∇f and have centered pth moments bounded by σp, where 1<p≤2 and σ≥0. For ε>0, the goal is a measurable output x¯ satisfying E∥∇f(x¯)∥≤ε, with expectation over sampling and independent algorithm randomness.

The optimization problem is infx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. The algorithm receives d, the measurable sample space Ω, L, Δ, σ, p, ε, and x0∈Rd.

Our assumptions:

Assumption 1 (Objective and initial gap). The function f is differentiable everywhere. There exists ℓ∈R such that f(x)≥ℓfor every x∈Rd,f(x0)−ℓ≤Δ.

Assumption 2 (Sample smoothness). There exist a probability measure ν on Ω and jointly measurable maps F:Rd×Ω→R,G:Rd×Ω→Rd. For every ω∈Ω, the function F(⋅,ω) is differentiable everywhere, and for every x,y∈Rd, ∇xF(x,ω)=G(x,ω),∥G(x,ω)−G(y,ω)∥≤L∥x−y∥.

Assumption 3 (Unbiased gradients and heavy-tailed noise). For every x∈Rd, the map G(x,⋅) is Bochner integrable under ν, and ∥G(x,⋅)−∇f(x)∥p is integrable under ν. They satisfy Eξ∼ν[G(x,ξ)]=∇f(x),Eξ∼ν[∥G(x,ξ)−∇f(x)∥p]≤σp.

At call k≥0, the algorithm queries any pair (xk,yk)∈Rd×Rd and receives (F(xk,ξk),F(yk,ξk)). The sample variables (ξk)k≥0 are measurable, mutually independent, and each has law ν. They are independent of the algorithm’s randomness. Thus both values in a reply use the same sample, while distinct calls use independent samples. One oracle call returns this pair of scalar values; the budget counts such paired calls.

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

Results

Differentiable f:Rd→R, d≥1, has a lower bound f∗ with f(x0)−f∗≤Δ. Samples F(⋅;ξ) have L-Lipschitz gradients G, with F,G jointly measurable, ∫G(x;ξ)dν=∇f(x) and ∫∥G(x;ξ)−∇f(x)∥pdν≤σp, with the corresponding integrability, 1<p≤2. Each oracle call returns two values sharing one sample; successive samples are IID with law ν. Target: ∫∥∇f(xout)∥dP≤ε. The setup imposes no algorithm restriction.

Heavy-tailed two-point zeroth-order optimization: HeavyTailedTwoPointZerothOrder.
Result Oracle complexity Novelty Limitations
(1) ClippedSpsaHeavyTailed (Ours) (review) O(1+132qdLΔε2[1+(σε)q])
(2) Derived bound: RS-NSGD + finite differences (Omiya et al. 2026), Thm. 5.4/C.3, r=1 Op(1+dLΔε2[1+(σε)q])
Sample-smooth two-point emulation; all minibatch calls counted.
(1): Matches known rate for fixed p; new batch-free scalar-clipped SPSA analysis. Same tuning knowledge L,Δ,σ,p,ε. (1): Worse explicit constant.
(3) RSC-ZO (El Bakkali et al. 2026), Thm. 2.3, Rem. 2.4 Op([1+LΔε2](1+Aq)⋅log⁡2+LΔ/ε2δ[1+log⁡(1+A)]q/2)
Pr{T−1∑t<T∥∇f(xt)∥2≤ε2}≥1−δ; ε2≤32LΔ.
(1): On bounded p-moments, fixed p<2, expected accuracy costs d instead of dq/2, removing LΔ and logarithms; not an identical-output speedup. (1): Expectation only; requires bounded p-moments instead of weak-Lp tails.

Abbr: q=p/(p−1); A=d(LΔ+σ)/ε; Δ is the initial-gap bound; σ is the noise scale; δ∈(0,1) is the failure probability; T is the iteration count. Costs count shared-sample two-point calls (two scalar evaluations each), including batches. Op allows unquantified dependence on p. Weak-Lp: Pr(∥G−∇f∥>t)≤(σ/t)p. P is the output probability law, including algorithmic randomness.

El Bakkali, Taha, El Mahdi Chayti, Qiuyi Zhang, Imane Rahali, and Omar Saadi. 2026. Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2605.17394.
Omiya, Gaku, Pierre-Louis Poirion, and Akiko Takeda. 2026. Convergence Analysis of Randomized Subspace Normalized SGD Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2601.20399.

Lean setup