Adaptive Algorithms and Data-Dependent Guarantees for Bandit Convex Optimization

Scott Yang Courant Institute of Mathemati, Mehryar Mohri Courant Institute of Mathematical Sciences
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:395-404, 2016.

Abstract

We present adaptive algorithms with strong data-dependent regret guarantees for the problem of bandit convex optimization. In the process, we develop a general framework from which all previous main results in this setting can be recovered. The key method is the introduction of adaptive regularization. By appropriately adapting the exploration scheme, we show that one can derive regret guarantees which can be significantly more favorable than those previously known. Moreover, our analysis also modularizes the problematic quantities in achieving the conjectured minimax optimal rates in the most general setting of the problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-mathemati16a, title = {Adaptive Algorithms and Data-Dependent Guarantees for Bandit Convex Optimization}, author = {Mathemati, Scott Yang Courant Institute of and Sciences, Mehryar Mohri Courant Institute of Mathematical}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {395--404}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/mathemati16a/mathemati16a.pdf}, url = {https://proceedings.mlr.press/r14/mathemati16a.html}, abstract = {We present adaptive algorithms with strong data-dependent regret guarantees for the problem of bandit convex optimization. In the process, we develop a general framework from which all previous main results in this setting can be recovered. The key method is the introduction of adaptive regularization. By appropriately adapting the exploration scheme, we show that one can derive regret guarantees which can be significantly more favorable than those previously known. Moreover, our analysis also modularizes the problematic quantities in achieving the conjectured minimax optimal rates in the most general setting of the problem.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Adaptive Algorithms and Data-Dependent Guarantees for Bandit Convex Optimization %A Scott Yang Courant Institute of Mathemati %A Mehryar Mohri Courant Institute of Mathematical Sciences %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-mathemati16a %I PMLR %P 395--404 %U https://proceedings.mlr.press/r14/mathemati16a.html %V R14 %X We present adaptive algorithms with strong data-dependent regret guarantees for the problem of bandit convex optimization. In the process, we develop a general framework from which all previous main results in this setting can be recovered. The key method is the introduction of adaptive regularization. By appropriately adapting the exploration scheme, we show that one can derive regret guarantees which can be significantly more favorable than those previously known. Moreover, our analysis also modularizes the problematic quantities in achieving the conjectured minimax optimal rates in the most general setting of the problem. %Z Reissued by PMLR on 04 October 2026.
APA
Mathemati, S.Y.C.I.o. & Sciences, M.M.C.I.o.M.. (2016). Adaptive Algorithms and Data-Dependent Guarantees for Bandit Convex Optimization. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:395-404 Available from https://proceedings.mlr.press/r14/mathemati16a.html. Reissued by PMLR on 04 October 2026.

Related Material