Abstract:
|
In this talk, I will describe a new parameter-free online learning algorithm for changing environments. Our algorithm, Coin Betting for Changing Environments (CBCE), leverages elements of Sleeping Bandits methods and coin betting algorithms for parameter-free online learning. CBCE admits a strongly adaptive regret bound that is a factor of at least \sqrt{log(T)} better than competing algorithms with the same time complexity as ours, where T is the time horizon. In addition, CBCE is "parameter free" -- that is, it is unnecessary to know a priori how often the environment changes to set tuning parameters. Empirical results show that our algorithm outperforms state-of-the-art methods in learning with expert advice and metric learning scenarios.
|