In plain words: A textbook on online learning — making repeated decisions and minimizing regret against the best fixed choice in hindsight — showing that most known algorithms are versions of two core update rules. It stresses variants that set their own parameters instead of needing hand-tuning, with short simple proofs.
Abstract · Online Learning: A Modern Introduction Using Convex Optimization
In this book, I introduce the concepts of online learning through a modern view based on convex optimization. Here, online learning refers to the framework of regret minimization under worst-case assumptions. I attempted to unify all the literature as instantiations of Online Mirror Descent and Follow-the-Regularized-Leader (and their variants). I paid particular attention to the issue of tuning the parameters of the algorithms, through adaptive and parameter-free online learning algorithms. The bandit setting is also briefly discussed, touching on the problem of adversarial and stochastic multi-armed bandits. Building on fundamental algorithms and concepts, I also cover advanced topics, including black-box reductions, saddle-point optimization, sequential investment, and non-stationary forms of regret analysis. Finally, I conclude with a selection of applications of online learning to domains far from it, such as generalization theory and concentration inequalities. I attempted to maintain an informal, yet mathematically rigorous, tone throughout the book. Moreover, all the included proofs have been carefully chosen to be as simple and as short as possible. This also means that sometimes I have added one or two additional assumptions, just to simplify the proofs.
Francesco Orabona
arXiv:1912.13213 · cs.LG, math.OC, stat.ML · submitted Dec 31, 2019 · updated Jun 21, 2026
abstract · pdf · Final version, to be published by Cambridge University Press. Changed title; added foreword by Nicolò Cesa-Bianchi; more exercises; general clean-up
