Date 
Topics 
Lecture Notes 
Additional reading 




9/8 
Course overview; Introduction 
Lecture 1

9/10 
Mistake bound model; Halving algorithm 
Lecture 2

9/14 
Learning linear separators 
Lecture 3


9/15 
Perceptron 
Lecture 4


9/17 
Consistency model 
Lecture 5

(SSBD): Section 3.1

9/21 
PAC learning; Connections between learning models 
Lectures 6 & 7

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

9/22 
Connections between learning models continued 

(SSBD): Chapter 4

9/24 
Agnostic learning; Error decompositions 
Lectures 8 & 9


9/28 
Concentration inequalities; Uniform convergence for finite classes 


9/29 
Growth function, Uniform convergence for infinite classes

Lectures 10 & 11


10/1 
Uniform convergence for infinite classes continued



10/5 
VC dimension

Lectures 12 & 13


10/6 
Sauer's Lemma; Uniform convergence for infinite classes under the realizability assumption



10/8 
Compression schemes

Lecture 14

(SSBD): Chapter 30

10/12 
Bounded differences inequality; Rademacher complexity

Lectures 15–18


10/13 
Bounds based on Rademacher complexity



10/15 
Connection to VC dimension



10/19 
Properties of Rademacher complexity



10/20 
Support vector machines

Lectures 19 & 20


10/22 
Margin bounds



10/26 
Margin bounds continued
Littlestone dimension

See Section 21.1.1 of SSBD


10/27 
Littlestone dimension continued



10/29 
Decisiontheoretic online learning; Hedge

Lectures 23 & 24


11/2 
Analysis of Hedge



11/3 
Prediction with expert advice

Lectures 25 & 26


11/5 
Prediction with expert advice and expconcave losses



11/9 
Game theory 
Lecture 27


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

11/17 
Analysis of UCB 

11/19 
Nonstochastic multiarmed bandits; EXP3 
Lecture 30

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

11/23 
Nonstochastic multiarmed bandits; EXP3 


11/24 
Nonstochastic multiarmed bandits; EXP3 


11/26 
Extra topic! Online portfolio selection 

(CBL): Chapter 10
(Kalai and Vempala, 2002)

11/30 
Project presentations 

12/1 
Project presentations 

12/3 
Project presentations 
