The Many Faces of Exponential Weights in Online Learning
  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. Here 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.
