Theoretical Machine Learning (Fall 2024)

Overview

This course focuses on the theoretical foundation of machine learning. The first half of the course 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 course focuses on algorithm design for sequential prediction problems, especially for those that require learning under limited feedback. A concrete schedule can be found here.

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 writing in LaTeX, collaboration, and presentation.

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% of grade) 4 problem sets, each of which consists of several theory questions.

• (60% of grade) A final project on a short survey of an assigned topic, which includes an in-class presentation and a report.

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

• Akshay Krishnamurthy's ML theory class at UMass