Tim van Erven, Leiden University, the Netherlands

MetaGrad: Multiple Learning Rates in Online Learning

In online convex optimization (known as prediction with individual sequences in information theory) it is well known that certain subclasses of loss functions are much easier than arbitrary convex functions. We are interested in designing adaptive methods that can automatically get fast rates in as many such subclasses as possible, without any manual tuning. Previous adaptive methods are able to interpolate between strongly convex and general convex functions. We present a new method, MetaGrad, that adapts to a much broader class of functions, including exp-concave and strongly convex functions, but also various types of stochastic and non-stochastic functions without any curvature. For instance, MetaGrad can achieve logarithmic regret on the unregularized hinge loss, even though it has no curvature, if the data come from a favourable probability distribution, which satisfies a Bernstein/margin-type condition. MetaGrad's main feature is that it simultaneously considers multiple learning rates, which control the amount of regularization. Unlike all previous methods with provable regret guarantees, however, its learning rates are not monotonically decreasing over time and are not tuned based on a theoretically derived bound on the regret. Instead, they are weighted directly proportional to their empirical performance on the data using a tilted exponential weights master algorithm.

- T. van Erven and W.M. Koolen. MetaGrad: Multiple Learning Rates in Online Learning. Neural Information Processing Systems (NIPS) 2016.
- W.M.Koolen, P. Grünwald and T. van Erven. Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning. Neural Information Processing Systems (NIPS) 2016.