Online Linear Optimization via Smoothing
  We present a new optimization-theoretic approach to analyzing
Follow-the-Leader style algorithms, particularly in the setting where
perturbations are used as a tool for regularization. We show that adding a
strongly convex penalty function to the decision rule and adding stochastic
perturbations to data correspond to deterministic and stochastic smoothing
operations, respectively. We establish an equivalence between "Follow the
Regularized Leader" and "Follow the Perturbed Leader" up to the smoothness
properties. This intuition leads to a new generic analysis framework that
recovers and improves the previous known regret bounds of the class of
algorithms commonly known as Follow the Perturbed Leader.
