A Modern Introduction to Online Learning

By Francesco Orabona. arXiv.org, 2019

559 citations recorded by the source corpus.

In this monograph, I introduce the basic concepts of Online Learning through a modern view of Online Convex Optimization. Here, online learning refers to the framework of regret minimization under worst-case assumptions. I present first-order and second-order algorithms for online learning with convex losses, in Euclidean and non-Euclidean settings. All the algorithms are clearly presented as instantiation of Online Mirror Descent or Follow-The-Regularized-Leader and their variants. Particular attention is given to the issue of tuning the parameters of the algorithms and learning in unbounded domains, through adaptive and parameter-free online learning algorithms. Non-convex losses are dealt through convex surrogate losses and through randomization. The bandit setting is also briefly discussed, touching on the problem of adversarial and stochastic multi-armed bandits. These notes do not require prior knowledge of convex analysis and all the required mathematical tools are rigorously explained. Moreover, all the proofs have been carefully chosen to be as simple and as short as possible.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/bf96d01b4d1be851fbe4a84a354dc856607ee550

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

User-friendly introduction to PAC-Bayes bounds (2021, background): “We refer the reader to [178, 153] for more up to date introductions to online learning.”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, background): “Online learning with point-wise loss has been studied extensively [65, 131, 147].”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “[40] and Orabona [41] presented lower bounds of static regret, that is, β = 0 and D0 = 0.”
Locality Sensitive Sparse Encoding for Learning World Models Online (2024, methodology): “…representational advantage of our encoding over other non-linear features, and demonstrate that our method outperforms NNs in the online supervised learning setting (Orabona, 2019; Hoi et al., 2021) as well as the model-based reinforcement learning setting (Sutton, 1990) with models learned online.”
Continual Backprop: Stochastic Gradient Descent with Persistent Randomness (2021, background): “In online supervised learning (Orabona, x 1 x f x m ... ... x f +1 flipping bits i.i.d. bits 2019), there is a stream of samples ( x t , y t ) , and the predictions have to be made sequentially.”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, methodology): “Let ψ : D → R be a strictly convex function such that X ⊆ D , we require either one of the following to hold: The first requirement from Orabona (2019) amounts to assuming ψ is a Legendre function ( i . e ., essentially smooth and strictly convex), which implies that x t +1 ∈ int D (Cesa-Bianchi &…”