# A simple and improved algorithm for noisy, convex, zeroth-order optimisation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 15 references that are in the map.
- First posted on arXiv 26 Jun 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Highly-Smooth Zero-th Order Online Optimization Vianney Perchet](https://mlsanity.com/paper/1605.08165/) (2016)
- [Bandit Convex Optimisation](https://mlsanity.com/paper/2402.06535/) (2024)
- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)

## Built on by (most cited first, 1 of 1)

- [Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension](https://mlsanity.com/paper/2607.12938/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of noisy, convex, zeroth order optimisation of a function f over a bounded convex set barmathcal Xsubset ℝd. Given a budget n of noisy queries to the function f that can be allocated sequentially and adaptively, our aim is to construct an algorithm that returns a point hat x∈ barmathcal X such that f(hat x) is as small as possible. We provide a conceptually simple method inspired by the textbook center of gravity method, but adapted to the noisy and zeroth order setting. We prove that this method is such that the f(hat x) - min_x∈ barmathcal X f(x) is of smaller order than d2/√n up to poly-logarithmic terms. We slightly improve upon existing literature, where to the best of our knowledge the best known rate is in [Lattimore, 2024] is of order d2.5/√n, albeit for a more challenging problem. Our main contribution is however conceptual, as we believe that our algorithm and its analysis bring novel ideas and are significantly simpler than existing approaches.