Improved Regret for Zeroth-Order Stochastic Convex Bandits

Tor Lattimore, Andras Gyorgy
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2938-2964, 2021.

Abstract

We present an efficient algorithm for stochastic bandit convex optimisation with no assumptions on smoothness or strong convexity and for which the regret is bounded by O(d^(4.5) sqrt(n) polylog(n)), where n is the number of interactions and d is the dimension.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-lattimore21a, title = {Improved Regret for Zeroth-Order Stochastic Convex Bandits}, author = {Lattimore, Tor and Gyorgy, Andras}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {2938--2964}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/lattimore21a/lattimore21a.pdf}, url = {https://proceedings.mlr.press/v134/lattimore21a.html}, abstract = {We present an efficient algorithm for stochastic bandit convex optimisation with no assumptions on smoothness or strong convexity and for which the regret is bounded by O(d^(4.5) sqrt(n) polylog(n)), where n is the number of interactions and d is the dimension.} }
Endnote
%0 Conference Paper %T Improved Regret for Zeroth-Order Stochastic Convex Bandits %A Tor Lattimore %A Andras Gyorgy %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-lattimore21a %I PMLR %P 2938--2964 %U https://proceedings.mlr.press/v134/lattimore21a.html %V 134 %X We present an efficient algorithm for stochastic bandit convex optimisation with no assumptions on smoothness or strong convexity and for which the regret is bounded by O(d^(4.5) sqrt(n) polylog(n)), where n is the number of interactions and d is the dimension.
APA
Lattimore, T. & Gyorgy, A.. (2021). Improved Regret for Zeroth-Order Stochastic Convex Bandits. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:2938-2964 Available from https://proceedings.mlr.press/v134/lattimore21a.html.

Related Material