Improved Strongly Adaptive Online Learning using Coin Betting

Kwang-Sung Jun, Francesco Orabona, Stephen Wright, Rebecca Willett
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:943-951, 2017.

Abstract

This paper describes a new parameter-free online learning algorithm for changing environments. In comparing against algorithms with the same time complexity as ours, we obtain a strongly adaptive regret bound that is a factor of at least $\sqrt\log(T)$ better, where $T$ is the time horizon. Empirical results show that our algorithm outperforms state-of-the-art methods in learning with expert advice and metric learning scenarios.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-jun17a, title = {{Improved Strongly Adaptive Online Learning using Coin Betting}}, author = {Jun, Kwang-Sung and Orabona, Francesco and Wright, Stephen and Willett, Rebecca}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {943--951}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/jun17a/jun17a.pdf}, url = {https://proceedings.mlr.press/v54/jun17a.html}, abstract = {This paper describes a new parameter-free online learning algorithm for changing environments. In comparing against algorithms with the same time complexity as ours, we obtain a strongly adaptive regret bound that is a factor of at least $\sqrt\log(T)$ better, where $T$ is the time horizon. Empirical results show that our algorithm outperforms state-of-the-art methods in learning with expert advice and metric learning scenarios. } }
Endnote
%0 Conference Paper %T Improved Strongly Adaptive Online Learning using Coin Betting %A Kwang-Sung Jun %A Francesco Orabona %A Stephen Wright %A Rebecca Willett %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-jun17a %I PMLR %P 943--951 %U https://proceedings.mlr.press/v54/jun17a.html %V 54 %X This paper describes a new parameter-free online learning algorithm for changing environments. In comparing against algorithms with the same time complexity as ours, we obtain a strongly adaptive regret bound that is a factor of at least $\sqrt\log(T)$ better, where $T$ is the time horizon. Empirical results show that our algorithm outperforms state-of-the-art methods in learning with expert advice and metric learning scenarios.
APA
Jun, K., Orabona, F., Wright, S. & Willett, R.. (2017). Improved Strongly Adaptive Online Learning using Coin Betting. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:943-951 Available from https://proceedings.mlr.press/v54/jun17a.html.

Related Material