← All setups

Accelerated Two Point Zeroth Order Convex — Stochastic Zeroth-Order Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Zeroth-Order Convex Minimization · Lean proof

Stochastic Zeroth-Order Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a d-dimensional real Hilbert space E, where d≥1. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E satisfies ∥x0−x⋆∥≤R for a global minimizer x⋆ and R≥0. At each query x, the oracle returns an unbiased scalar estimate of f(x) with variance at most σ2, where σ≥0, using an independent sample. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). The space E is linearly isometric to Rd with its Euclidean norm; ∥⋅∥ denotes the induced norm on E. Let Ω be the measurable sample space. The algorithm receives E, Ω, d, L, R, σ, ε, and x0; the objective and the oracle’s sampling distribution are accessed only through oracle replies.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 2 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Stochastic function values). There are a probability measure ν on Ω and a jointly measurable map g:E×Ω→R. For every x∈E, both g(x,⋅) and (g(x,⋅)−f(x))2 are ν-integrable, and Eξ∼ν[g(x,ξ)]=f(x),Eξ∼ν[(g(x,ξ)−f(x))2]≤σ2. At call k≥0, a query x∈E receives the scalar reply g(x,ξk). Under their joint law Q on ΩN, the samples (ξk)k≥0 are independent and each has distribution ν. Algorithm randomness is independent of this entire sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable and satisfy EP[f(x¯)−f(x⋆)]≤ε, with f(x¯)−f(x⋆) integrable under P, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Proved result

max{1,⌈64⋅d⋅L⋅R2ε+512⋅L⋅d2⋅R2⋅σε2+256⋅L⋅d2⋅R2⋅σ2ε3+1⌉+}⋅2

OracleTemplate.Convergence LongTails.Setups.ZerothOrderSmoothAndConvex.spec
  OracleTemplate.ZerothOrder.AcceleratedTwoPointZerothOrderConvex.budget

Relevant previous results

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