| Date | Topics | Lecture Notes and Recommended Reading |
| 08/30 | Introduction, statistical learning, online learning
no free lunch theorem, online-to-batch conversion | Lecture notes 1
Sections 3-5 of R&S |
| 09/06 | Uniform convergence, Rademacher complexity, finite class
Classification: growth function, VC dimension, Sauer's lemma | Lecture notes 2
|
| 09/13 | Regression: covering number, Dudley entropy integral
chaining technique, Pseudo-dimension | Lecture notes 3
Sections 12.4 and 12.9 of R&S |
| 09/20 | 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/27 | Online learning: empirical process with dependent data
sequential Rademacher complexity, finite class bound
Online classification: zero-covering number | Lecture notes 5
Section 13.5 of R&S |
| 10/04 | Online classification: Littlestone dimension
Online regression: covering number, chaining, fat-shattering dimension
Online algorithms for finite classes: Halving and Hedge | Lecture notes 6
Section 14.5 of R&S |
| 10/11 | Fall Recess | |
| 10/18 | Online algorithms for infinite classes with bounded Littlestone dimension
Perceptron, Online Convex Optimization
Follow-the-Regularized-Leader | Lecture notes 7
More on OCO and FTRL from this note |
| 10/25 | From values to algorithms
Learning with partial information, multi-armed bandits
EXP3, Explore-then-Exploit | Lecture notes 8
Proposition 22.2, Sections 22.1.2, 22.2 and 23 of R&S |
| 11/01 | UCB, Lower bound for multi-armed bandits
Partial monitoring: classification theorem | Lecture notes 9
Sections 37.1-37.3 of L&S |
| 11/08 | Partial monitoring: algorithms and lower bounds | Lecture notes 10
The ‘‘Exploration by Optimization’’ paper by L&S
Sections 37.4-37.9 of L&S |
| 11/15 | Student presentations | |
| 11/22 | Student presentations | |
| 11/29 | Thanksgiving | |
| 12/06 | Student presentations |
|