Princeton University 
Computer Science 598A 
Spring

This syllabus is constantly evolving as the semester progresses, so check back often (and let me know if it seems not to be up to date).
# 
Date 
Topic 
Readings

1  Tu, 2/7  General introduction to boosting 
1 slides 
2 3 
Th, 2/9 Tu, 2/14 
Foundations of machine learning; methods of analysis; PAC learning  2 
4  Th, 2/16  Training error of AdaBoost; sufficient conditions for weak learning; relation to Chernoff bounds  3.13.3 
5  Tu, 2/21 
Design of weak learning algorithms; direct bounds on generalization error 
3.4; 4.1 
6  Th, 2/23  Compressionbased bounds; equivalence of strong and weak learning  4.24.3 
7  Tu, 2/28  Margins; analysis of generalization error 
5.15.2 margins movie 
8  Th, 3/1  Rademacher complexity; effect of boosting on margins  5.35.4 
9  Tu, 3/6  Maximizing minimum margin; SVMs; other margin topics  5.55.7 
10  Th, 3/8  Classical game theory; repeated games; MW algorithm and analysis  6.16.2.3 
Tu, 3/13  MIDTERM (in class)  
11  Th, 3/15  Finish MW analysis; minmax theorem; online learning  6.2.46.3 
12  Tu, 3/27 
Game theory and boosting; begin boosting as loss minimization 
6.46.5; begin 7 
13 14 
Th, 3/29 Tu, 4/3 
boosting as loss minimization  7 
15  Th, 4/5 
Finish boosting as loss minimization; begin iterative projection algorithms 
begin 8 
16 17 
Tu, 4/10 Th, 4/12 
Iterative projection algorithms; information geometry  8 
18  Tu, 4/17 
Quick look at confidencerated weak hypotheses (and other topics); Bayes error and minimum risk 
9.1; 9.2.6; 12.1 
19  Tu, 4/24 
Consistency of AdaBoost; "breaking" AdaBoost with just a little noise 
12.2; 12.3 
20 21 
Th, 4/26 Tu, 5/1 
Optimal boosting  13 
22  Th, 5/3  Boosting in continuous time  14 