Online Newton Method for Bandit Convex Optimisation

arXiv (Cornell University)

Abstract

We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation and prove that in the adversarial setting its regret is at most $d^{3.5} \sqrt{n} \mathrm{polylog}(n, d)$ with high probability where $d$ is the dimension and $n$ is the time horizon. In the stochastic setting the bound improves to $M d^{2} \sqrt{n} \mathrm{polylog}(n, d)$ where $M \in [d^{-1/2}, d^{-1 / 4}]$ is a constant that depends on the geometry of the constraint set and the desired computational properties.

Authors 4

1. Hidde Fokkema

   Academic Center for Dentistry Amsterdam · University of Amsterdam

   Affiliation as printed

   Institute for Mathematics University of Amsterdam

2. Dirk van der Hoeven Aachen

   Leiden University

   Affiliation as printed

   Mathematical Institute Leiden University

3. Tor Lattimore
4. Jack J. Mayo