A Second-Order Method for Stochastic Bandit Convex Optimisation
This work addresses optimization in bandit settings for researchers in machine learning and optimization, presenting an incremental improvement with a specific theoretical guarantee.
The paper tackles the problem of unconstrained zeroth-order stochastic convex bandits by introducing a simple and efficient algorithm, achieving a regret bound of $(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 minimizer.
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.