Introduction to Online Learning

I have published the lecture notes of my class “Introduction to Online Learning” I taught at Boston University during Fall 2019. The class covers the basics on Online Learning in the adversarial setting, i.e., regret minimization.

I tried to present the latest results in the field, keeping the proofs as simple as possible.
I strongly suggest to go over the lectures in order: I have introduced the required math tools slowly over the lectures, rather than all at once in single lectures.

Index

  1. Introduction to Online Learning
  2. Online Gradient Descent
  3. Subgradients and Online-to-Batch Conversion
  4. More Online-to-Batch Examples and Strong Convexity
  5. Adaptive Algorithms: L* bounds and AdaGrad
  6. Lower Bounds for Online Linear Optimization
  7. Online Mirror Descent I: Bregman version
  8. Online Mirror Descent II: Regret and Mirror Version
  9. Online Mirror Descent III: Examples and Learning with Expert Advice
  10. Follow-The-Regularized-Leader I: Regret Equality
  11. Follow-The-Regularized-Leader II: Applications
  12. Follow-The-Regularized-Leader III: More Logarithmic Bounds
  13. Online Linear Classification
  14. Parameter-free Online Learning I: Coin-Betting and 1-d OCO
  15. Parameter-free Online Learning II: Reductions
  16. Parameter-free Online Learning III: from Coins to Experts
  17. Optimistic Follow-The-Regularized-Leader
  18. Multi-Armed Bandit I
  19. Multi-Armed Bandit II
  20. Multi-Armed Bandit III: Stochastic Bandits
  21. Multi-Armed Bandit IV: UCB
  22. From Online Learning to Statistical Learning