Online Newton Method for Bandit Convex Optimisation

  • 2024-06-10 18:44:11
  • Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, Jack J. Mayo
  • 0


We introduce a computationally efficient algorithm for zeroth-order banditconvex optimisation and prove that in the adversarial setting its regret is atmost $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 thebound 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 theconstraint set and the desired computational properties.


Quick Read (beta)

loading the full paper ...