Accelerated 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 on a -dimensional real Hilbert space , where . Its gradient is -Lipschitz, with , and a given point satisfies for a global
minimizer and . At each query , the oracle returns an unbiased scalar
estimate of with variance at
most , where , using an independent sample.
For , the goal is a
measurable output with
integrable objective gap satisfying ,
averaging over algorithm and oracle randomness.
The optimization problem is The space is
linearly isometric to
with its Euclidean norm;
denotes the induced norm on . Let
be the measurable sample
space. The algorithm receives ,
, , , , , , and ; the objective and the oracle’s
sampling distribution are accessed only through oracle replies.
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is Fréchet
differentiable everywhere on . For
every and ,
Assumption 2 (Initial distance). There exists such that
Assumption 3 (Stochastic function values). There are
a probability measure on and a jointly measurable map . For every
, both and are -integrable, and At call , a query receives the scalar reply . Under their joint law on , the samples are independent and each
has distribution . Algorithm
randomness is independent of this entire sample sequence.
Queries may be made at any point of . After the allotted oracle calls, the
output must be measurable
and satisfy
with
integrable under , where is the joint law of the algorithm’s
randomness and the oracle sample sequence.
Proved result
OracleTemplate.Convergence LongTails.Setups.ZerothOrderSmoothAndConvex.spec
OracleTemplate.ZerothOrder.AcceleratedZerothOrderConvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.