# Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension

arXiv: https://arxiv.org/abs/2607.12938 · HTML: https://mlsanity.com/paper/2607.12938/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 14 Jul 2026.

## Builds on (most cited first, 7 of 7)

- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)
- [A simple and improved algorithm for noisy, convex, zeroth-order optimisation](https://mlsanity.com/paper/2406.18672/) (2024)

## Abstract (arXiv)

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 Omega(1/√T) lower bound, even in the one-dimensional case. In this work, we study the problem of minimizing a convex function f : [0,1] → [0,1] using a zero-order oracle with subGaussian noise. We propose a computationally efficient algorithm that achieves the optimal O(1/√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.