Online Newton Method for Bandit Convex Optimisation
<|reference_start|>Online Newton Method for Bandit Convex Optimisation: 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.<|reference_end|>
@article{fokkema2024online,
    title={Online Newton Method for Bandit Convex Optimisation},
    author={Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, Jack J. Mayo},
    journal={arXiv preprint arXiv:2406.06506},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.06506},
    primaryClass={math.OC cs.LG stat.ML}
}