The Many Faces of Exponential Weights in Online Learning - VVSOR - VVSOR

Vereniging voor Statistiek en Operations Research
02 November 2018

The Many Faces of Exponential Weights in Online Learning

This is a kind reminder that the next meeting of the Thematic Statistics Seminar will on Friday, November 2 in Leiden before the Bayes Club:

 

Speaker: Dirk van der Hoeven (Leiden University)
Title: The Many Faces of Exponential Weights in Online Learning
Time: 15:00-16:00, November 2, 2018
Location: Room 403, Snellius Building, Leiden University, Niels Bohrweg 1, Leiden

 

Abstract: A standard introduction to online learning might place Online Gradient Descent at its center and then proceed to develop generalizations and extensions like Online Mirror Descent and second-order methods. We explore the alternative approach of putting Exponential Weights (EW) first. We show that many standard methods and their regret bounds then follow as a special case by plugging in suitable surrogate losses and playing the EW posterior mean. For instance, we easily recover Online Gradient Descent by using EW with a Gaussian prior on linearized losses, and, more generally, all instances of Online Mirror Descent based on regular Bregman divergences also correspond to EW with a prior that depends on the mirror map. Furthermore, appropriate quadratic surrogate losses naturally give rise to Online Gradient Descent for strongly convex losses and to Online Newton Step. We further interpret several recent adaptive methods (iProd, Squint, and a variation of Coin Betting for experts) as a series of closely related reductions to exp-concave surrogate losses that are then handled by Exponential Weights. Finally, a benefit of our EW interpretation is that it opens up the possibility of sampling from the EW posterior distribution instead of playing the mean. As already observed by Bubeck and Eldan, this recovers the best-known rate in Online Bandit Linear Optimization.

For the list of upcoming talks and further information about the seminar please visit the seminar webpage: https://mschauer.github.io/StructuresSeminar/