Stochastic Zeroth-Order Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Zeroth-Order Convex Minimization
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function
Assumption 2 (Initial distance). There exists
Assumption 3 (Stochastic function values). There are
a probability measure
Queries may be made at any point of
Results
A real Hilbert space is linearly isometric to
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedTwoPointZerothOrderConvex
(Ours) |
|||
| (2) AcceleratedZerothOrderConvex (Ours) (review) | |||
| (3) Derived bound:
retuned two-point SGD (Bach and Perchet 2016),
Prop. 7, |
(1): |
||
| (4) Derived bound: box smoothing and AC-SA (Lan 2008), Cor. 3 | Independent coordinate differences; all |
(1): |
|
| (5) Two-point SGD (Bach and Perchet 2016), Prop. 7, published tuning | Rescaled unconstrained |
(2): better bound for
|
(2): needs |
Abbr: Costs count individual function-value calls,
including all batches.
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (6) Accelerated random search (Nesterov and Spokoiny 2017), Thm. 9 | Exact-value restriction: |
(1): matches noiseless
rate and extends to independent finite-variance noise.
(2): matches for |
|
| (7) (Loginov et al.
2026), Thm. 4(b), |
Additional Hölder smoothness |
(1): |
(1), (2): require unbiased values without systematic or adversarial errors. |
| (8) (Lattimore and György 2023), Thm. 1; high-probability conversion | Globally |
(1), (2): permit finite-variance noise and non-Lipschitz objectives, including quadratics. Rates are not directly comparable across expected and high-probability criteria. | (1), (2): need smoothness; give expected accuracy only, rather than a high-probability guarantee. |
Abbr: Costs count individual function-value calls,
including all batches.