Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension
Alexandra Carpentier, Chloé Rouyer, Alexandre Tsybakov, Arya Akhavan
Abstract
Stochastic convex optimization is a classical problem with well-understood guarantees under first-order feedback. In contrast, for zero-order optimization with noisy function evaluations, a logarithmic gap has persisted between known upper bounds and the $Ω(1/\sqrt{T})$ lower bound, even in the one-dimensional case. In this work, we study the problem of minimizing a convex function $f : [0,1] \to [0,1]$ using a zero-order oracle with subGaussian noise. We propose a computationally efficient algorithm that achieves the optimal $O(1/\sqrt{T})$ convergence rate, matching the lower bound. The result closes the existing gap in one dimension, providing the first sharp rate guarantee in this setting.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.