Online Learning Crash Course – Part 0: Setting & Motivation
An introduction to the online learning paradigm, its core principles, motivations, and the sequential decision-making framework.
Collection-landing
Online Learning Crash Course
A foundational journey into sequential decision-making, regret minimization, and adaptive optimization algorithms.
This crash course provides a self-contained introduction to the fundamental principles and algorithms of online learning. We explore how to make optimal sequential decisions in the face of uncertainty, quantify performance using regret, and develop algorithms like Online Gradient Descent, Follow-The-Regularized-Leader, Mirror Descent, and adaptive methods such as AdaGrad.
The series emphasizes the mathematical underpinnings and geometric interpretations, laying the groundwork for understanding advanced optimization techniques in machine learning. Key topics include:
- The Online Learning Protocol & Motivation
- Regret Analysis & Performance Benchmarks
- Gradient-Based Methods (OGD)
- The Power of Regularization (FTRL)
- Geometric Generalizations (Mirror Descent)
- Adaptive Learning Rates (AdaGrad & Beyond)
- Online-to-Batch Conversions & Generalization
This course is designed for readers comfortable with linear algebra, multivariable calculus, and basic mathematical notation. It serves as an essential prerequisite for deeper dives into optimization theory within machine learning, particularly for understanding adaptive optimizers and their connections to online methods.
Online Learning Crash Course – Part 1: Regret & Benchmarks
Defining regret, the core performance metric in online learning, and discussing benchmarks for evaluating sequential decision-making algorithms.
Online Learning Crash Course – Part 2: Online Gradient Descent
Introducing Online Gradient Descent (OGD), a fundamental algorithm for online convex optimization, its update rule, and regret analysis.
Online Learning Crash Course – Part 3: FTL & FTRL
Exploring Follow-The-Leader (FTL), its limitations, and the Follow-The-Regularized-Leader (FTRL) framework for stable and effective online learning.
Online Learning Crash Course – Part 4: Mirror Descent & Geometry
Exploring Online Mirror Descent (OMD), its use of Bregman divergences for non-Euclidean geometries, and its relationship to OGD and FTRL.
Online Learning Crash Course – Part 5: Adaptivity (AdaGrad & Beyond)
Discussing adaptive online learning algorithms like AdaGrad, which tailor learning rates per-coordinate based on observed gradient statistics.
Online Learning Crash Course – Part 6: Online-to-Batch Conversions
Connecting online learning algorithms and their regret bounds to batch and stochastic optimization settings, and discussing generalization.
Online Learning Crash Course – Part 7: Beyond Convexity (Teaser)
A brief look into online learning scenarios beyond convex optimization, including bandit feedback and non-convex losses.
Online Learning Crash Course – Part 8: Summary & Guidance
Summarizing the online learning crash course, offering practical guidance, reflection points, and connecting to further topics in optimization.
Online Learning Crash Course – Cheat Sheet
A consolidated cheat sheet of key concepts, algorithms, and formulas from the Online Learning Crash Course for quick reference.