← All setups

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 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.

Results

A real Hilbert space is linearly isometric to Rd, d≥1. The differentiable convex function f has L-Lipschitz gradient and a minimizer x⋆ with ∥x0−x⋆∥≤R. Each value query uses a fresh IID seed ξ∼p: jointly measurable g satisfies ∫g(x,ξ)dp(ξ)=f(x) and ∫(g(x,ξ)−f(x))2dp(ξ)≤σ2, with these integrands integrable. Known d,L,R,σ,ε satisfy L,ε>0, R,σ≥0. Target: measurable output x^ with integrable gap and ∫[f(x^(ω))−f(x⋆)]dP(ω)≤ε, where P is the execution law.

Noisy value-oracle convex optimization under ZerothOrderSmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedTwoPointZerothOrderConvex (Ours) (⋆⋆) (review) O(1+dLR2/ε+d2LR2σ/ε2+d2LR2σ2/ε3)
(2) AcceleratedZerothOrderConvex (Ours) (review) O(d+dLR2/ε+d2LR2σ/ε2+d3LR2σ2/ε3)
(3) Derived bound: retuned two-point SGD (Bach and Perchet 2016), Prop. 7, β=2 O(1+dLR2/ε+d2LR2σ2/ε3+d2LR2min{σε2,dσ2ε3}) (1): O(dT) instead of O(dT) when T≥1, σ≤ε/(dT). Matches order for T≥1, σ≥ε/d; unchanged quadratic-noise term.
(4) Derived bound: box smoothing and AC-SA (Lan 2008), Cor. 3 O(d+dLR2/ε+d2LR2σ/ε2+d3LR2σ2/ε3)
Independent coordinate differences; all 2d values per gradient included.
(1): d2 instead of d3 in the quadratic-noise term. (2): matches known rate; Lean formalization.
(5) Two-point SGD (Bach and Perchet 2016), Prop. 7, published tuning O(d2+d2(LR2+σ2/(LR2))3ε3)
Rescaled unconstrained β=2 guarantee; T≥1.
(2): better bound for σ≤LR2/d; at σ=0, O(dT) instead of O(d2T3). (2): needs σ for tuning; up to d times worse near σ=LR2 in the noise-dominated regime LR2/d<σ<d1/4LR2.

Abbr: Costs count individual function-value calls, including all batches. T=LR2/ε; σ bounds noise standard deviation. In (7), M is the Lipschitz constant of systematic error and δ bounds adversarial error. In (8), G is a global Lipschitz constant, S=σ+GR/d, ℓ=1+log⁡max{1,d,GR,S/ε}, and ψ2 denotes the sub-Gaussian Orlicz norm.

ZerothOrderSmoothAndConvex (continued).
Result Oracle complexity Novelty Limitations
(6) Accelerated random search (Nesterov and Spokoiny 2017), Thm. 9 O(1+dLR2/ε)
Exact-value restriction: σ=0.
(1): matches noiseless rate and extends to independent finite-variance noise. (2): matches for T≥1 and extends to noisy values.
(7) (Loginov et al. 2026), Thm. 4(b), V=L (subsequent work) O(d+dLR2/ε+d2LR2σ2/ε3)
Additional Hölder smoothness β>2; R>0. Allows M≲ε/R, δ≲ε3/2/(RdL), with sufficiently small constants.
(1): O(dT) instead of O(dT) when T≥1, σ≤ε/(dT), M=δ=0. (1), (2): no β>2 requirement. (1), (2): require unbiased values without systematic or adversarial errors.
(8) (Lattimore and György 2023), Thm. 1; high-probability conversion N=O(1+d3S2ℓ8/ε2+d3Sℓ4/ε)
Globally G-Lipschitz f, GR≥1; sub-Gaussian noise of ψ2 norm ≤σ. Averaged-point gap ≤ε with probability ≥1−7/N.
(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. T=LR2/ε; σ bounds noise standard deviation. In (7), M is the Lipschitz constant of systematic error and δ bounds adversarial error. In (8), G is a global Lipschitz constant, S=σ+GR/d, ℓ=1+log⁡max{1,d,GR,S/ε}, and ψ2 denotes the sub-Gaussian Orlicz norm.

Bach, Francis, and Vianney Perchet. 2016. “Highly-Smooth Zero-Th Order Online Optimization.” 29th Annual Conference on Learning Theory, Proceedings of machine learning research, vol. 49: 257–83. https://proceedings.mlr.press/v49/bach16.html.
Lan, Guanghui. 2008. Efficient Methods for Stochastic Composite Optimization. School of Industrial; Systems Engineering, Georgia Institute of Technology. https://optimization-online.org/2008/08/2061/.
Lattimore, Tor, and András György. 2023. “A Second-Order Method for Stochastic Bandit Convex Optimisation.” Proceedings of Thirty Sixth Conference on Learning Theory, Proceedings of machine learning research, vol. 195: 2067–94. https://doi.org/10.48550/arXiv.2302.05371.
Loginov, Timofei, Darina Dvinskikh, Nazarii Tupitsa, Osman Osmanov, Yuriy Dorn, and Alexander Gasnikov. 2026. Minimax Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions. https://doi.org/10.48550/arXiv.2610.05517.
Nesterov, Yurii, and Vladimir Spokoiny. 2017. “Random Gradient-Free Minimization of Convex Functions.” Foundations of Computational Mathematics 17 (2): 527–66. https://doi.org/10.1007/s10208-015-9296-2.

Lean setup