Source-linked AI summary
Online Learning: A Modern Introduction Using Convex Optimization
Francesco Orabona
TL;DR
The book addresses how to guarantee low regret in online decision-making under worst-case feedback and unknown future losses. It develops convex-optimization-based algorithms and their variants, including optimistic and bandit methods, and presents regret guarantees alongside applications beyond online learning. Its scope is broad, but several simplified proofs rely on bounded-domain or parameter-tuning assumptions, and some improved guarantees use improper predictors.
Problem
Online learning must minimize regret against arbitrary loss sequences despite unknown future losses and, in bandit settings, observing only the selected action's loss.
Method
The book develops Online Mirror Descent and Follow-the-Regularized-Leader variants, including stochastic loss estimation for bandit feedback and optimism based on predicted future losses.
Results
The presented methods provide regret bounds, including local-norm bounds for constrained settings and bounds for optimistic online mirror descent under decreasing learning rates.
Takeaways & Limitations
The framework unifies online-learning algorithms while extending analysis to bandit feedback, improper prediction, and parameter-free settings.
Takeaways & Limitations
Some guarantees depend on tight upper bounds or bounded domains, while parameter-free tuning can incur a logarithmic factor and simplified proofs may add assumptions.
Abstract
from arXiv · showhide
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.
1. What is Online Learning?
This section is titled “Online Subgradient Descent.”
- The section introduces Online Subgradient Descent.
- It concerns an online descent method based on subgradients.
- The supplied passage provides no further details about its algorithm or guarantees.
16. From Online Learning to X
The book develops online learning as regret minimization against arbitrary competitors, then connects this framework to learning, optimization, and broader applications. It motivates sublinear regret through simple guessing games and presents Follow-the-Leader as a way to track changing hindsight optima.
- Foundations: For i.i.d. guessing data, the best fixed prediction is the distribution mean, with expected squared loss σ^2T when the distribution is known.The variance σ^2 measures the irreducible expected loss of predicting with the mean.
- Online learning framework: Online learning designs algorithms that minimize regret against an arbitrary competitor over a sequence of loss functions.The framework does not require the algorithm to know the competitor or its eventual regret.
- Applications: The regret framework applies beyond fixed-distribution data, including machine learning, optimization, repeated games, network routing, and stochastic gradient methods.The cited applications include click prediction, routing, convergence to equilibrium, and stochastic optimization.
- Foundations: In the guessing game, Follow-the-Leader uses the best choice from past rounds because the optimal guess cannot change too much between consecutive rounds.The strategy tracks the past optimum rather than assuming future data will resemble the past.
- Foundations: For arbitrary sequences, the strategy achieves sublinear regret, with the basic analysis giving a logarithmic dependence on time while not establishing minimax optimality.The text notes that logarithmic dependence is unavoidable for this problem, even though the presented strategy is not shown minimax optimal.
Exercises
The exercises develop regret guarantees for online optimization and connect them to stochastic optimization and statistical learning. They also emphasize parameter tuning, reductions, and assumptions that shape the guarantees.
- Sublinear regret means average performance approaches that of any fixed strategy, including under a fixed stochastic distribution of losses.
- The guarantees account for prediction-before-loss observation, initial distance to the competitor, and cases where an optimal solution does not exist.
- Learning-rate choices matter: some OGD rates are suboptimal, while adaptive and parameter-free algorithms can achieve similar rates without fixed tuning.
- Online convex optimization can be reduced to online linear optimization by linearizing convex losses, enabling linear-loss algorithms to solve many OCO problems.
- Online-to-batch conversion transforms regret guarantees into convergence rates, including the optimal O(1/√T) rate for stochastic optimization of convex Lipschitz functions.
- Online learning can guarantee agnostic PAC learnability, and predictor-selection procedures can match ERM sample complexity up to polylogarithmic factors.
A.1 More Convex Analysis
This section develops foundational convex-analysis results, including the fundamental theorem of calculus for extended-real-valued convex functions, Hausdorff spaces, and attainment of minima on compact sets.
- Fundamental results: For a proper convex function, subgradients along line segments support the fundamental theorem of calculus for extended-real-valued convex functions.The result applies to points in the interior of the function’s domain and subgradients evaluated along the segment.
- Topological foundations: A Hausdorff space separates any two distinct points with disjoint open neighborhoods.Euclidean spaces are given as an example of Hausdorff spaces.
- Existence of minimizers: A lower semicontinuous function on a compact set with a nonempty effective domain attains its infimum.The theorem assumes the ambient space is Hausdorff.
A.2 Inequalities for Transcendental Functions
This section collects inequalities and auxiliary results for transcendental, special, combinatorial, and probabilistic functions. It includes bounds for the Lambert W function, convexity-based extrema, gamma and digamma properties, norm constants, binomial coefficients, and binomial tails.
- Lambert function: The Lambert function satisfies the lower bound W(x) ≥ 0.6321 ln(x + 1), with the lower-bound construction using b = 1.71825 . . . .The upper-bound discussion invokes a general logarithmic inequality for W(x).
- Special functions: The appendix states definitions and properties for the gamma and digamma functions, including gamma log-convexity and strict monotonicity and concavity of the digamma function.Additional inequalities bound the digamma function and its derivative.
- Convexity and extrema: For a convex function on a simplex, the maximum is attained at an extreme point, so one coordinate equals T and the others equal 0.The argument establishes convexity after extending the function continuously to the simplex.
- Norm inequalities: The section records piecewise constants for norm inequalities and attributes the constants to Haagerup (1981).The displayed constants vary across ranges of p and include gamma-function expressions.