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ᵈ. 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 center 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²/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 d^2. 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.