Regularization, Perturbations, and Stability in Online Learning
summary
Shows that adding Gumbel perturbations to past losses yields sampling probabilities proportional to e^{-theta}, so FTPL with those perturbations is exactly the exponential-weights algorithm whose implicit entropy regularizer produces the same update. Claims eta scales like sqrt(T), achieving regret about sqrt(T log N); Hannan’s 1956 uniform-perturbation idea predates this. Proves: any perturbation gives a convex regularizer via Fenchel duality, but not every regularizer has an exact perturbation; FTPL stays attractive for efficient combinatorial or shortest-path oracles.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:37Pipeline
- 5:42Gumbel lemma
- 9:39Online Learning
- 11:19Experts Problem
- 14:25History
- 23:48Multiplicative weights
- 27:18Exponential weights
- 28:13Entropy
- 29:48Regularization
- 34:23Nonsmooth functions
- 37:28Smooth functions
- 39:33Nonlinearity
related talks
01h 05mOptimization for Machine Learning I
38mBest of Both World Algorithms from I.I.D. to Adversarial Data
42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors
53mDesigning Robust Learners
44mParsimonious Learning-Augmented Algorithms
01h 01mRobustness, Stochastics, Uncertainty 2
30mLarge Scale Private Learning on Data Streams, and the BLTs
45mFollow the Leader with Dropout Perturbations