AISTATS 2017poster85 citations
Improved Strongly Adaptive Online Learning using Coin Betting
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, Rebecca Willett
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.
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. }
}