← All setups

Clipped Spsa Heavy Tailed — Heavy-Tailed Two-Point Zeroth-Order Optimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Two-Point Zeroth-Order Optimization · Lean proof

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.

Proved result

⌈220⋅132pp−1⋅L⋅d⋅Δε2⋅(1+(σε)pp−1)⌉++1

OracleTemplate.Convergence LongTails.Setups.HeavyTailedTwoPointZerothOrder.spec
  OracleTemplate.ClippedSpsaHeavyTailed.budget

Relevant previous results

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