COS 511


Can the mechanism of learning be automated and implemented by a machine?
In this course we formally define and study various models that have been proposed for learning. The course will present and contrast the statistical, computational and gametheoretic models for learning. We will present and rigorously analyze some of the most successful algorithms in machine learning that are extensively used today. Likely topics include: intro to statistical learning theory and bounds on the number of random examples needed to learn; learning in adversarial settings and the online learning model; using convex optimization to model and solve learning problems; learning with partial observability; how to boost the accuracy of a weak learning algorithm; universal portfolio selection; learning in games.
Professor: Elad Hazan, CS building 407, Reception hours: Tue 1112, or by appointment.
Teaching Assistant: Kevin Lai, CS building 003, Reception hours: Mon 15:3016:30, Wed 15:3016:30
Requirements: This is a graduatelevel course that requires mathematical background. Recommended background courses: probability, discrete math, calculus, analysis, linear algebra, algorithms and data structures, theory of computation / complexity theory, linear programming.
Attendance and the use of electronic devices: Attendance is expected at all lectures. The use of laptops and similar devices for notetaking is permitted.
Topic  Lecture notes  Extra reading  Problem sets 

Introduction to Learning Theory Statistical Learning model 
lecture1  chapters 12 in books 13  
PAC learning start VCtheory 
lecture2  hw1  
finish VCtheory, efficient linear classification  lecture 3 part1 lecture 3 part 2 
hw2  
special guest talk (the juggling professor) + + decision making, multiplicative updates 
lecture4Jake part 2 = chapter1 
MW survey  
online convex optimization, convex modelling  chapter 23 (5) lecture 5 (unedited) 
Zinkevich's paper  hw3 
portfolio selection, second order methods  chapter 4 (5) lecture 6 (unedited) 
Cover's paper simpler analysis here 
hw4 
regularization, perturbation and stability  chapter 5 (5) lecture 7 (unedited) 
Kalai and Vempala's paper Hannan's original paper 
none this week 
online 2 batch, bandits  chapters 6,9 (5) lecture 8 (unedited) 
Flaxman, Kalai, Mcmahan competing in the dark 
hw5 
special guest lecture: Prof. Arora  lecture 9 (unedited) 
Prof. Arora's course  
bandits cont. , Boosting  chapters 6,10 (5) lecture 10 (unedited) 
Boosting: Foundations and Algorithms, by R. E. Schapire and Y. Freund Schapire survey 
hw6 
Games, Duality and Regret  chapter 8 (5) lecture 11 (unedited) 
convergence of regret minimization dynamics in concave games  
Computational aspects of learning  research paper lecture 12 (unedited) 
Blum's hardness result 