A Second-Order Method for Stochastic Bandit Convex Optimisation

Tor Lattimore, András György
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2067-2094, 2023.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-lattimore23a, title = {A Second-Order Method for Stochastic Bandit Convex Optimisation}, author = {Lattimore, Tor and Gy{\"o}rgy, Andr{\'a}s}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {2067--2094}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/lattimore23a/lattimore23a.pdf}, url = {https://proceedings.mlr.press/v195/lattimore23a.html}, 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.} }
Endnote
%0 Conference Paper %T A Second-Order Method for Stochastic Bandit Convex Optimisation %A Tor Lattimore %A András György %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-lattimore23a %I PMLR %P 2067--2094 %U https://proceedings.mlr.press/v195/lattimore23a.html %V 195 %X 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.
APA
Lattimore, T. & György, A.. (2023). A Second-Order Method for Stochastic Bandit Convex Optimisation. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:2067-2094 Available from https://proceedings.mlr.press/v195/lattimore23a.html.

Related Material