Overview: This course focuses on the theoretical foundation of machine learning.
The first half of the course is devoted to study fundamental learning problems in statistical learning and online learning, and to answer the core question: what determines the complexity of learning?
The second half of the course focuses on algorithm design for sequential prediction problems, especially for those that require learning under limited feedback.
Learning Objectives:
The goal of this course is to understand when and why machine learning works from a mathematical aspect. The hope is that through the training of this course you will think about machine learning in a more rigorous and principled way and have the skills to design provable and practical machine learning algorithms.
Requirements:
 Four problem sets (40%).
Collaboration is allowed but must be stated. Grades are based on correctness. Must be written in Latex.
Please hand in your homework by emailing our TA.
 One final project on a short survey of a particular topic in learning theory (60%). The project includes two parts: one 3040 minutes presentation near the end of the semester (20%), and a final report written in Latex (40%). More details can be found here.
Late homework policy: You are given 4 late days for the problem sets (no late days for the final project),
to be used in integer amounts and distributed as you see fit.
Additional late days will each result in a deduction of 10% of the grade of the corresponding assignment.
Piazza: You have to enroll in Piazza since important announcements (regarding homework, project, course scheduling, etc) will be made there. You are also very welcome to ask and/or answer questions on Piazza.
Prerequisites: familiarity with probability, linear algebra, convex analysis, calculus, and analysis of algorithms. Some basic understandings of machine learning would be very helpful.
Readings: There is no official textbook for this course. Lecture notes will be posted on this website after each class. Other recommended reading is mostly from the following books/lecture notes:
Schedule: (subject to minor adjustments)
Date 
Topics 
Recommended Reading 
Homework 
08/29 
Introduction; statistical learning; online learning; no free lunch theorem; onlinetobatch conversion; 
Lecture notes 1;
Sections 3, 4, 5 of R&S


09/05 
Uniform convergence; Rademacher complexity; finite class
Classification: growth function; VC dimension; Sauer's lemma 
Lecture notes 2;


09/12 
Finish Sauer's lemma's proof;
Regression: covering number; chaining technique; Dudley entropy integral;

Lecture notes 3;
Sections 12.4 and 12.9 of R&S

HW 1

09/19 
Pseudodimension; fatshattering dimension;
Online learning: empirical process with dependent data; sequential Rademacher complexity 
Lecture notes 4;
Section 12.8 of R&S
Proof for bounding covering number with fatshattering dimension


09/26 
Contraction and finite class bound for sequential Rademacher complexity;
Online classification: zerocovering number, Littlestone dimension 
Lecture notes 5;
Section 13.5 of R&S


10/03 
Online regression: covering number, chaining, fatshattering dimension;
Online algorithms: Halving, Hedge, generalized Halving 
Lecture notes 6;
Section 14.5 of R&S

HW 2 
10/10 
perceptron; Online Convex Optimization; FollowtheRegularizedLeader; from values to algorithms 
Lecture notes 7;
Proposition 22.2, Sections 22.1.2, 22.2 and 23 of R&S


10/17 
Fall Recess 

HW 3 
10/24 
Learning with partial information; multiarmed bandits; Exp3; UCB; lower bound 
Lecture notes 8;


10/31 
Partial monitoring: classification theorem, minimax regret bounds, and algorithms 
Lecture notes 9;
Section 37 of L&S


11/07 
Partial monitoring: lower bounds;
Reinforcement learning: episodic Markov decision processes; Bellman equations; Qlearning 
Lecture notes 10;
More details on optimistic Qlearning and its improved variant can be found in the original paper

HW 4 
11/14 
Student presentations (see schedule here) 


11/21 
Student presentations (see schedule here) 


11/28 
Thanksgiving 


12/05 
Student presentations (see schedule here) 


