Online Learning: A Modern Introduction Using Convex Optimization

Abstract

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.

Final version, to be published by Cambridge University Press. Changed title; added foreword by Nicolò Cesa-Bianchi; more exercises; general clean-up

References in corpus (16)

• On the Convergence of Adam and Beyond
• Adaptive Bound Optimization for Online Convex Optimization
• Online Learning with Predictable Sequences
• A parameter-free hedging algorithm
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• Minimax Policies for Combinatorial Prediction Games
• Optimistic Rates for Learning with a Smooth Loss
• Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
• No-Regret Algorithms for Unconstrained Online Convex Optimization
• Online Linear Optimization via Smoothing
• Less Regret via Online Conditioning
• Fighting Bandits with a New Kind of Smoothness
• Parameter-Free Online Convex Optimization with Sub-Exponential Noise
• A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds
• Combining Online Learning Guarantees
• Comparator-adaptive Convex Bandits

Cited by in corpus (45)

• User-friendly introduction to PAC-Bayes bounds
• Exploration-Exploitation in Constrained MDPs
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Online Caching with Optimistic Learning
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Optimistic Policy Optimization with Bandit Feedback
• Asymptotically Optimal Information-Directed Sampling
• Online learning in MDPs with linear function approximation and bandit feedback
• Temporal Variability in Implicit Online Learning
• Prediction with Corrupted Expert Advice
• Stochastic Regret Minimization in Extensive-Form Games
• Spectral risk-based learning using unbounded losses
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• Improved Learning Rates for Stochastic Optimization
• A closer look at temporal variability in dynamic online learning
• Non-exponentially weighted aggregation: regret bounds for unbounded loss functions
• Online DR-Submodular Maximization with Stochastic Cumulative Constraints
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
• Stochastic Approximation versus Sample Average Approximation for population Wasserstein barycenters
• Online Convex Optimization with Continuous Switching Constraint
• Parameter-free Stochastic Optimization of Variationally Coherent Functions
• Graph Belief Propagation Networks
• Scale Free Adversarial Multi Armed Bandits
• Understanding Bandits with Graph Feedback
• Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
• Universal Online Convex Optimization Meets Second-order Bounds
• Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
• Optimistic and Adaptive Lagrangian Hedging
• On the Last Iterate Convergence of Momentum Methods
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• Robust learning with anytime-guaranteed feedback
• Continual Backprop: Stochastic Gradient Descent with Persistent Randomness
• Improved Regret Bounds for Online Submodular Maximization
• Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff
• LeadCache: Regret-Optimal Caching in Networks
• Locally-Adaptive Nonparametric Online Learning
• Explaining Fast Improvement in Online Imitation Learning
• Parameter-free Gradient Temporal Difference Learning
• Low-Regret Active learning
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Online Learning with Optimism and Delay
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory
• Towards Online Optimization for Power Grids
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers
• Multitask Online Mirror Descent