A Second-Order Method for Stochastic Bandit Convex Optimisation

Abstract

We introduce a simple and efficient algorithm for unconstrained zeroth-order stochastic convex bandits and prove its regret is at most $(1+r/d)[d^{1.5}\sqrt{n}+d^3]polylog(n,d,r)$ where $n$ is the horizon, $d$ the dimension and $r$ is the radius of a known ball containing the minimiser of the loss.

27 pages