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 online 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; unsupervised learning; spectral methods in learning.
Wed, 16:3017:50 Friend Center, 008.
Professor: Roi Livni, CS building 219, Reception hours: Wed 11:0012:00, or by appointment.
Teaching Assistants:
Kiran Vodrahalli, CS building 402 , Reception hours: Mon 15:0016:30, or by appointment.
Requirements:
This is a graduatelevel course that requires significant mathematical
background.
Required background: probability, discrete math, calculus, analysis,
linear algebra, algorithms and data structures, theory of computation /
complexity theory
Recommended: linear programming, mathematical optimization, game theory
Attendance and the use of electronic devices: Attendance is expected at all lectures. The use of laptops and similar devices for notetaking is permitted.
Number  Topic  Lecture notes  Extra reading  Problem sets 

1  Introduction to Learning Theory The PAC Model 
Lecture 1  Chapters 15 in book 4  
2  Agnostic PAC, ERM Learnability of Finite Classes 
Lecture 2  Chapters 15 in book 4  
3  VC dimension The Fundemental Theorem 
Lecture 3  Chapters 15 in book 4  
4  No Free Lunch Sauer's Lemma 
Lecture 4  Chapters 15 in book 4 The probablistic method  N. Alon & J. Spencer 
Exercise 1 
5  Proof of Fund. Thm. Neural Networks 
Lecture 5  Chapters 15, and 20 in book 4 The probablistic method  N. Alon & J. Spencer 

6  Neural Networks. Expressiveness and Sample Complexity 
Lecture 6  Chapter 20 in book 4 Neural Network Learning: Theoretical Foundations M. Anthony & P. Bartlett 
Exercise 2 
7  Generalized PAC Model Computational Learning Theory 
Lecture 7  Chapter 8 in book 4 Santosh Vempala's lecture notes on LP:The Ellipsoid Algorithm 

8  Perceptron Algorithm Hardness of Learning 
Lecture 8  A, Klivans A. Sherstov (2009) Cryptographic Hardness of Learning Intersections of Halfspaces 

9  Boosting 
Lecture 9  Y. Freund; R. Schapire (1997). "A decisiontheoretic generalization of online learning and an application to boosting" 

10  Boosting Cont Convex Learning Problems 
Lecture 10  Book 5  
11  Surrogate Loss Rademacher Complexity 
Lecture 11  Cahpter 26 in Book 4  Exercise 3 
12  Rademacher Bounds and Calculus 
Lecture 12  Chapter 26 in Book 4  
13  The Sample Complexity of Linear Classes Stochastic Gradient Descent 
Lecture 13  Chapter 26 in Book 4 S. Shalev Shwatz, O. Shamir, N. Srebro, K. Sridharan (2009). "Stochastic Convex Optimization" 

14  Analysis of SGD 
Lecture 14  
15  Kernel Methods 
Lecture 15  Exercise 4  
16  Neural Network 2 & Backpropogation 
Lecture 16  
17  Online Learning 
Lecture 17  
18  Expert Advice (Hedge Algorithm) Online to Batch 
Lecture 18  
19  Strong Convexity (Logarithmic Regret) Second Order Methods 
Lecture 19  
20  Online Newton Step Analysis 
Lecture 20  
21  Follow The Regulerized Leader 
Lecture 21  Exercise 5  
22  Learning with Partial Feedback 
Lecture 22  
23  Bandit Convex Optimization 
Lecture 23 