Timezone: »
Most methods for decision-theoretic online learning are based on the Hedge algorithm, which takes a parameter called the learning rate. In most previous analyses the learning rate was carefully tuned to obtain optimal worst-case performance, leading to suboptimal performance on easy instances, for example when there exists an action that is significantly better than all others. We propose a new way of setting the learning rate, which adapts to the difficulty of the learning problem: in the worst case our procedure still guarantees optimal performance, but on easy instances it achieves much smaller regret. In particular, our adaptive method achieves constant regret in a probabilistic setting, when there exists an action that on average obtains strictly smaller loss than all other actions. We also provide a simulation study comparing our approach to existing methods.
Author Information
Tim van Erven (University of Amsterdam)
Peter Grünwald (CWI and Leiden University)
Wouter M Koolen (Centrum Wiskunde & Informatica)
Steven D Rooij (CWI)
More from the Same Authors
-
2019 Poster: PAC-Bayes Un-Expected Bernstein Inequality »
Zakaria Mhammedi · Peter Grünwald · Benjamin Guedj -
2016 Poster: Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning »
Wouter Koolen · Peter Grünwald · Tim van Erven -
2016 Poster: MetaGrad: Multiple Learning Rates in Online Learning »
Tim van Erven · Wouter Koolen -
2016 Oral: MetaGrad: Multiple Learning Rates in Online Learning »
Tim van Erven · Wouter Koolen -
2015 Workshop: Learning Faster from Easy Data II »
Tim van Erven · Wouter Koolen -
2014 Workshop: From Bad Models to Good Policies (Sequential Decision Making under Uncertainty) »
Odalric-Ambrym Maillard · Timothy A Mann · Shie Mannor · Jeremie Mary · Laurent Orseau · Thomas Dietterich · Ronald Ortner · Peter Grünwald · Joelle Pineau · Raphael Fonteneau · Georgios Theocharous · Esteban D Arcaute · Christos Dimitrakakis · Nan Jiang · Doina Precup · Pierre-Luc Bacon · Marek Petrik · Aviv Tamar -
2014 Poster: Efficient Minimax Strategies for Square Loss Games »
Wouter M Koolen · Alan Malek · Peter Bartlett -
2014 Poster: Learning the Learning Rate for Prediction with Expert Advice »
Wouter M Koolen · Tim van Erven · Peter Grünwald -
2013 Workshop: Learning Faster From Easy Data »
Peter Grünwald · Wouter M Koolen · Sasha Rakhlin · Nati Srebro · Alekh Agarwal · Karthik Sridharan · Tim van Erven · Sebastien Bubeck -
2013 Workshop: Large Scale Matrix Analysis and Inference »
Reza Zadeh · Gunnar Carlsson · Michael Mahoney · Manfred K. Warmuth · Wouter M Koolen · Nati Srebro · Satyen Kale · Malik Magdon-Ismail · Ashish Goel · Matei A Zaharia · David Woodruff · Ioannis Koutis · Benjamin Recht -
2013 Poster: The Pareto Regret Frontier »
Wouter M Koolen -
2012 Poster: Mixability in Statistical Learning »
Tim van Erven · Peter Grünwald · Mark Reid · Robert Williamson -
2012 Poster: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2012 Spotlight: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2011 Poster: Learning Eigenvectors for Free »
Wouter M Koolen · Wojciech Kotlowski · Manfred K. Warmuth -
2007 Spotlight: Catching Up Faster in Bayesian Model Selection and Model Averaging »
Tim van Erven · Peter Grünwald · Steven de Rooij -
2007 Poster: Catching Up Faster in Bayesian Model Selection and Model Averaging »
Tim van Erven · Peter Grünwald · Steven de Rooij