| Date | Topics | Lecture Notes and Recommended Reading |
| 08/28 | Introduction, statistical learning, online learning,
no free lunch theorem, online-to-batch conversion | Lecture notes 1
Sections 3-5 of R&S |
| 09/04 | Uniform convergence, Rademacher complexity, finite class
Classification: growth function, VC dimension, Sauer's lemma | Lecture notes 2
|
| 09/11 | Regression: covering number, Dudley entropy integral,
chaining technique, Pseudo-dimension | Lecture notes 3
Sections 12.4 and 12.9 of R&S |
| 09/18 | Regression: fat-shattering dimension
Case study on neural nets: dimension-independent covering number
spectral complexity, margin | Lecture notes 4
Section 12.8 of R&S
Proof for bounding covering number with fat-shattering dimension
Zhang-Bengio-Hardt-Recht-Vinyals’17
Bartlett-Foster-Telgarsky’17 |
| 09/25 | Online learning: empirical process with dependent data,
sequential Rademacher complexity | Lecture notes 5
Section 13.5 of R&S |
| 10/02 | Online learning with a finite class
Online classification: zero-covering number and Littlestone dimension
Online regression: covering number, chaining, fat-shattering dimension | Lecture notes 6
Section 14.5 of R&S |
| 10/09 | Fall Recess | |
| 10/16 | Online algorithms for finite classes: Halving and Hedge
Online algorithms for infinite classes with bounded Littlestone dimension
Perceptron | Lecture notes 7 |
| 10/23 | Online Convex Optimization, Follow-the-Regularized-Leader
From values to algorithms
Learning with partial information, multi-armed bandits,
EXP3, Explore-then-Exploit | Lecture notes 8
More on OCO and FTRL from this note |
| 10/30 | UCB, Lower bound for multi-armed bandits
Partial monitoring: classification theorem | |
| 11/06 | Partial monitoring: algorithms and lower bounds | |
| 11/13 | Student presentations | |
| 11/20 | Student presentations | |
| 11/27 | Thanksgiving | |
| 12/04 | Student presentations |
|