Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed
Two-Point Zeroth-Order Optimization
We consider minimizing a differentiable, possibly nonconvex function
, where
, with a lower bound and given starting
point satisfying , where . The oracle returns two
scalar values and using a shared sample , with independent samples
across calls. Each sample function has an -Lipschitz gradient, where ; these gradients are unbiased for
and have centered th moments bounded by , where and . For , the goal is a
measurable output
satisfying , with expectation over sampling and
independent algorithm randomness.
The optimization problem is where
denotes the Euclidean
norm. The algorithm receives , the
measurable sample space ,
, , , , , and .
Our assumptions:
Assumption 1 (Objective and initial gap). The
function is differentiable
everywhere. There exists such that
Assumption 2 (Sample smoothness). There exist a
probability measure on and jointly measurable maps For every , the function is differentiable
everywhere, and for every ,
Assumption 3 (Unbiased gradients and heavy-tailed
noise). For every ,
the map is Bochner
integrable under , and is
integrable under . They satisfy
At call , the algorithm
queries any pair
and receives
The sample variables 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 must be
measurable, its gradient norm must be integrable, and it must satisfy
where is the joint law of the samples and the
independent algorithm randomness.