A simple and improved algorithm for noisy, convex, zeroth-order optimisation
<|reference_start|>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 $\bar{\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 \bar{\mathcal 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\in \bar{\mathcal X}} f(x)$ is of smaller order than $d^2/\sqrt{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}/\sqrt{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.<|reference_end|>
@article{carpentier2024a,
    title={A simple and improved algorithm for noisy, convex, zeroth-order
  optimisation},
    author={Alexandra Carpentier},
    journal={arXiv preprint arXiv:2406.18672},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.18672},
    primaryClass={math.OC cs.LG stat.ML}
}