Theoretical Machine Learning

CSCI 699, Fall 2019

Haipeng Luo

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.

• 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 30-40 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:

• Statistical Learning and Sequential Prediction by Alexander Rakhlin and Karthik Sridharan
• Foundations of Machine Learning by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar
• Bandit Algorithms by Tor Lattimore and Csaba Szepesvari

Schedule: (subject to minor adjustments)

Date	Topics	Recommended Reading	Homework
08/29	Introduction; statistical learning; online learning; no free lunch theorem; online-to-batch 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	Pseudo-dimension; fat-shattering 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 fat-shattering dimension
09/26	Contraction and finite class bound for sequential Rademacher complexity; Online classification: zero-covering number, Littlestone dimension	Lecture notes 5; Section 13.5 of R&S
10/03	Online regression: covering number, chaining, fat-shattering dimension; Online algorithms: Halving, Hedge, generalized Halving	Lecture notes 6; Section 14.5 of R&S	HW 2
10/10	perceptron; Online Convex Optimization; Follow-the-Regularized-Leader; 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; multi-armed 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; Q-learning	Lecture notes 10; More details on optimistic Q-learning 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)