TY - CONF
T1 - Improved strongly adaptive online learning using coin betting
AU - Jun, Kwang Sung
AU - Orabona, Francesco
AU - Wright, Stephen
AU - Willett, Rebecca
N1 - Funding Information:
Among a number of interesting directions, we are interested in reducing the time complexity in the online learning within a changing environment. For LEA, Fixed Share has the best time complexity. However, Fixed Share is inherently not parameter-free; especially, it requires the knowledge of the number of shifts m. Achieving the best m-shift regret bound without knowing m or the best SA-Regret bound in time O(NT) would be an interesting future work. The same direction is interesting for the online convex optimization (OCO) problem. It would be interesting if an OCO algorithm such as online gradient descent can have the same SA-Regret as CBCEÈOGDÍ without paying extra order of computation. Acknowledgements This work was supported by NSF Award IIS-1447449 and NIH Award 1 U54 AI117924-01. The authors thank András György for providing constructive feedback and Kristjan Greenewald for providing the metric learning code.
Publisher Copyright:
Copyright 2017 by the author(s).
PY - 2017
Y1 - 2017
N2 - 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 √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.
AB - 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 √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.
UR - http://www.scopus.com/inward/record.url?scp=85083937416&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85083937416&partnerID=8YFLogxK
M3 - Paper
AN - SCOPUS:85083937416
T2 - 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017
Y2 - 20 April 2017 through 22 April 2017
ER -