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

In this paper, we study the problem of noisy, convex, zeroth-order optimisation of a function f over a bounded convex set X 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 x X such that f (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 (x) - ₗ ₗf (x) is of smaller order than d^2/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/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/n under mild conditions on 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.