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. Also, it covers the so-called parameter-free online algorithms, i.e., algorithms without learning rates.

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.

I also compiled these posts in a cleaner and expanded pdf that is periodically updated.

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