Theoretical Machine Learning (Fall 2026)

Overview

This course focuses on the theoretical foundation of machine learning. The first half of the lectures is devoted to the fundamentals of statistical/online learning and the core question: what determines the sample complexity of learning? The second half of the lectures focuses on algorithm design for sequential prediction problems, especially for those that require learning under limited feedback. A concrete schedule can be found here. The final three classes will feature student presentations, with an emphasis on recent ML theory papers related to ongoing developments in AI.

Learning Objectives

The goal of this course is to understand when and why machine learning works from a mathematical perspective. Specifically, you will learn about classical complexity measures in statistical learning such as Rademacher complexity, VC dimension, covering number, fat-shattering dimension, and others, as well as their sequential version dedicated for the task of online learning. You will also learn how to design algorithms for online learning problems such as the classical multi-armed bandit problem. At a higher level, a more general objective of the course is to train you to think about machine learning in a more rigorous and principled way so you will be able to design theoretically sound machine learning algorithms after this course. Finally, through this course you will also obtain training on some basic but important research skills, such as presentation and collaboration.

Prerequisites

Familiarity with probability, convex analysis, calculus, linear algebra, and analysis of algorithms. Some basic understanding of machine learning would be very helpful.

Requirements

• (40%) 4 problem sets, each of which consists of several theory questions.

• (30%) A couple short in-class quizzes.

• (30%) A final presentation on an assigned ML theory paper.

Communications

The main communication tool for this course is Piazza. Please sign up via this link. All announcements of this course will be made there, so you have to sign up. You are also encouraged to ask and/or answer questions on Piazza.

Readings

There are no official textbooks for this course. In addition to the lecture notes, the following books/surveys/notes are all good resources for extra reading.

• 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 Szepesvári

• Vatsal Sharan's ML theory class at USC