Date 
Topics 
Lecture Notes and Problem Sets 
Additional reading 




9/5 
Course overview; Introduction; Mistake bound model 
Lecture 1

9/9 
Halving algorithm; Learning linear separators 
Lecture 2

9/12 
Perceptron; Consistency model; PAC learning 
Lectures 3 & 4

(SSBD): Section 3.1

9/16 
Connections between learning models 

Intro to statistical learning theory (Boucheron, Bousquet, Lugosi).
(SSBD): Chapter 5 for NoFreeLunch theorem

9/19 
Agnostic learning; Error decompositions; Concentration inequalities; Uniform convergence for finite classes 
Lectures 5 & 6
Problem Set 1

(SSBD): Chapter 4

9/23 
Growth function, Uniform convergence for infinite classes 


9/26 
VC dimension; Sauer's Lemma; Uniform convergence for infinite classes under the realizability assumption 
Lectures 7 & 8


9/30 
VC dimension; Sauer's Lemma 


10/3 
Uniform convergence for infinite classes under the realizability assumption Lower bounds based on the VC dimension 
Lecture 9


10/7 
Bounded differences inequality; Rademacher complexity Bounds based on Rademacher complexity 
Lectures 10, 11, & 12


10/10 
Bounds based on Rademacher complexity; Connection to VC dimension 
Problem Set 2


10/17 
Properties of Rademacher complexity 


10/21 
Support vector machines; Margin bounds 
Lecture 13


10/24 
Weak and Strong Learnability; Boosting Training error bound for AdaBoost 
Lecture 14
Problem Set 3

Rob Schapire's lecture notes.
A short introduction to boosting (Freund and Schapire)

10/28 
Compression schemes; Generalization error bounds for AdaBoost Proof that weak learnability implies strong learnability 
Lecture 15

10/31 
Margin bounds for AdaBoost 
Lecture 16

11/4 
Decisiontheoretic online learning; Hedge Analysis of Hedge 
Lecture 17

11/7 
Game theory; Connection to AdaBoost 
Lectures 18 & 19

11/14 
Game theory; Connection to AdaBoost 
11/18 
Prediction with expert advice (maybe) Expconcave loss functions 
Lecture 20
Problem Set 4

11/21 
Stochastic multiarmed bandits; UCB 
Shivani Agarwal's lecture notes

11/25 
Nonstochastic multiarmed bandits; EXP3 
Lecture 22

Sébastien Bubeck and Nicolò CesaBianchi's bandits monograph

11/28 
Nonstochastic multiarmed bandits; EXP3 


12/2 
Project presentations 
