Improved Strongly Adaptive Online Learning using Coin Betting
By Kwang-Sung Jun, Francesco Orabona, Stephen J. Wright, Rebecca M. Willett. 2016
95 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Management Science and Operations Research
Citations in the corpus
- Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “…is usually termed as shifting regret or tracking regret [Herbster and Warmuth, 1998, Gy¨orgy et al., 2005, Gyorgy et al., 2012, Gy¨orgy and Szepesv´ari, 2016, Mourtada and Maillard, 2017, Adamskiy et al., 2016, Wei et al., 2016, Cesa-Bianchi et al., 2012, Mohri and Yang, 2018, Jun et al., 2017].”
- Dynamic Regret of Strongly Adaptive Methods (2017, methodology): “Theorem 4 Under Assumption 1, the meta-algorithm of Jun et al. (2017) is strongly adaptive with”
- Efficient tracking of a growing number of experts (2017, background): “In addition, building on the recent work of Jun et al. (2017) might bring further improvements in this case.”
- Estimating means of bounded random variables by betting (2020, methodology): “5 Online Newton Step (ONS-m) Betting algorithms play an essential role in online learning as several optimization problems can be framed in terms of coin-betting games [47, 48, 49, 23].”
- Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “In particular, by restricting { y t } Tt =1 in the region 1 , our upper bound for dynamic regret implies that the shifting regret is bounded by √ KT , which is consistent with the result in [ Jun et al., 2017].”
- Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “This result slightly improves the existing result for shifting regret in [6] up to a logarithmic factor.”
- Adaptive Online Learning in Dynamic Environments (2018, background): “Later, the adaptive regret of convex functions is improved [Daniely et al., 2015, Jun et al., 2017].”
- Online Learning with Gated Linear Networks (2017, methodology): “w O(s p T) regret guarantees with respect to data sequences composed of spieces (Mattern, 2013). More rened algorithms based on coin betting allow the sto be moved inside the square root as shown by Jun et al. (2017). The -exp-concavity also allows second order techniques such as Online Newton Step ”