This course is open to graduate students, as well as advanced undergraduates with sufficient mathematical maturity. Undergraduate registration requires approval---please submit your consent request online and contact Nati (email@example.com) via email to secure approval. This course is also offered as part of the IDEAL Special Quarter on Theory of Deep Learning ( https://www.ideal.northwestern.edu/special-quarters/fall-2020/ ). If you are not a UChicago or TTIC student, you may request registration by registering for the special quarter (this includes Northwestern students, TTIC, UChicago and Northwestern post-docs and other scholars, and students and other scholars from other institutions).
TTIC Students: in order to register for the class you must register through the UChicago system. It is not sufficient to register on populi.
If you are a University of Chicago or TTIC student and would like to register for the class, but cannot because the class is full, please email us at firstname.lastname@example.org to be (temporarily) added manually to canvas and gain access to the class. We expect registration spots will open up. Additional seats are now available---please register through the course registration system, requesting consent if required.
Note: This course is not intended as an introductory machine learning course, and is recommended mostly for students familiar with machine learning problems and methods. Although all formulations and methods are carefully introduced and defined, very few examples of empirical behavior are explored, as the students will be assumed to have seen this previously. However, mathematically inclined students that prefer learning about concepts through definitions and theorems rather then examples and experimentation, and are interested in exploring the mathematical aspects of machine learning, might choose to take this course even without having previously completed an introductory machine learning course.
Lectures: Tuesday and Thursday - 2:40-4:00pm (Zoom Details)
Instructor: Nati Srebro (email@example.com).
TAs: Omar Montasser (firstname.lastname@example.org), Akilesh Tangella (email@example.com)
Office hours: Tuesdays 12-1PM (Akilesh), Thursdays 4-5pm (Omar), . You will find us at gather.town (Classroom A), see this page for instructions.
Office hours for Nati: Tuesday and Thursday after lecture.
Contact: Please use the alias firstname.lastname@example.org for queries about registration, special arrangements, extensions, conflicts, and other individual circumstances. If you have any question about class material or homework please use the Canvas forum.
The purpose of this course is to gain a deeper understanding of machine learning by formalizing learning mathematically, studying both statistical and computational aspects of learning, and understanding how these two aspects are inseparable. The course is intended both for students interested in using machine learning methods and that would like to understand such methods better so as to use them more effectively, as well as for students interested in the mathematical aspects of learning or that intend on rigorously studying or developing learning algorithms.
We will discuss classic results and recent advances in statistical learning theory, touch on computational learning theory, and explore the relationship with stochastic optimization and online regret analysis. Our emphasis will be on concept development and on obtaining a rigorous quantitative understanding of machine learning. We will also study techniques for analyzing and proving performance guarantees for learning methods.
- Mathematical maturity, as obtain, e.g., in a rigorous analysis course.
- Discrete Math (specifically combinatorics and asymptotic notation)
- Probability Theory
- Introduction to Machine Learning
- Algorithms; Basic Complexity Theory (NP-Hardness)
Familiarity with Convex Optimization, Computational Complexity and background in Statistics can be helpful, but is not required.
The Statistical Model (Learning Based on an IID Samples):
- The PAC (Probably Approximately Correct) and Agnostic PAC models.
- Generalized Learning and relationship to Stochastic Optimization
- VC Theory: Cardinality, VC dimension, a the growth function
- Description Length Bounds, Structural Risk Minimization
- Uniform Learning and No-Free Lunch Theorems
- Compression Bounds
- Scale sensitive classes: Fat Shattering Dimension, Covering Numbers and Radamacher Averages
- Tight Characterization of Learning in terms of the VC and Fat Shattering Dimensions
- Relative bounds, "Optimistic" rates, and Local Rademacher Analysis
- Boosting, including three different views of AdaBoost (traditional PAC view; learning a linear predictor with coordinate descent; boosting the margin and l1 as its dual)
Online Learning, Online Optimization and Online Regret:
- The Perceptron Rule and Online Gradient Descent
- Experts and the Winnow Rule
- Strong convexity, stability, and online learning in Banach spaces as a unifying theory.
- Bregman Divergence and Online Mirror Descent
- Online to Batch Conversion
Computational Lower Bounds:
- Computational Hardness of Proper Learning
- Cryptographic Hardness of Learning
Deep Learning through the lens of Learning Theory
Requirements and Grading
- Problem sets. About 5 problem sets, some of which introducing additional material not covered in class.
- Final Exam.
- Scribing or editing a scribed lecture or topic is required, will be graded, and will be 30% of the grade.
- Peer-grading: Each student is required to participate in grading one problem set throughout the quarter. This should roughly take about 2-3 hours in total.
- Optional challenge problems on some problem sets.
Additional information and links: Grading, Requirement and Problem Sets
We will not be following a specific text, but some of the material is covered in:
- Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. (Links to an external site.) Cambridge University Press, 2014.
- Shai Shalev-Shwartz. Online Learning and Online Convex Optimization (Links to an external site.) Foundations and Trends® in Machine Learning: Vol. 4: No. 2, pp 107-194. 2012.
- O. Bousquet, S. Boucheron, and G. Lugosi. Introduction to statistical learning theory. (Links to an external site.) Advanced Lectures on Machine Learning, pp. 169-207. Springer Berlin Heidelberg, 2004.
- Michael J. Kearns and Umesh Virkumar Vazirani. An Introduction to Computational Learning Theory. (Links to an external site.) MIT Press, 1994.
- Dmitry Panchenko's course on Statistical Learning Theory (Links to an external site.). Lecture notes (Links to an external site.).
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.