Theoretical Machine Learning

CSCI 699, Fall 2019

Haipeng Luo

When: Thu 2:00-5:20
Where: LVL 13
Office Hours: by appointment (haipengl at usc)

TA: Chung-Wei Lee
Office Hours: by appointment (leechung at usc)

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:

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)