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

Abstract

In this paper, we study the problem of noisy, convex, zeroth-order optimisation of a function $f$ over a bounded convex set $\overline{\mathcal{X}}\subset {\mathbb{R}}^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}\in \overline{\mathcal{X}}$ such that $f(\hat{x})$ is as small as possible. We provide a conceptually simple method inspired by the textbook centre 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\in \overline{\mathcal{X}}}f(x)$ is of smaller order than $d^2/\sqrt{n}$ up to poly-logarithmic terms. We slightly improve upon literature preceding this work, where the best-known rate was in Lattimore (2019) and was of order $d^{2.5}/\sqrt{n}$, albeit for a more challenging problem – yet in the literature contemporaneous to our work, the remarkable work of Fokkema et al. (2024) attains the faster rate of $d^{1.5}/\sqrt{n}$ under mild conditions on $\overline{\mathcal{X}}$. Our main contribution is, however, conceptual, as we believe that our algorithm and its analysis bring novel ideas and are significantly simpler than the existing approaches.