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 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.