CPSC 532D: Modern Statistical Learning Theory – Fall 2024 (24W1)

Instructor: Danica Sutherland (she): dsuth@cs.ubc.ca but use Piazza, ICICS X563.
Instructor: Also Bingshan Hu (she) for a section of the course in October, exact details to come.
TA: Tina Behnia (she).
Lecture info: Mondays/Wednesdays, 13:00 - 14:30, Ponderosa Commons 1011.
Office hours: TBD, hybrid in ICICS X563 + Zoom unless announced otherwise.
Piazza (or more-direct link); Canvas; Gradescope.

Previously offered in 23W1, 22W1, and (with the name 532S) 21W2; this instance will be broadly similar.

This is a course on the mathematical foundations of machine learning. When should we expect ML algorithms to work (or not work), and what kinds of assumptions do we need to make to rigorously prove this?

Schedule

Italicized entries are tentative. The lecture notes are self-contained, but the supplements column also refers to the following books (all available as free pdfs) for more details / other perspectives: Lecture notes are available as individual chapters linked below, or as one big frequently-updated file.
DateTopicSupplements
M Sep  2No class: Labour Day
W Sep  4Course intro, ERMSSBD 1-2; MRT 2; Bach 2
ThSep  5Assignment 1 posted (pdf, tex) — loss functions, finite classes
M Sep  9Uniform convergence with finite classesSSBD 2-4; MRT 2
W Sep 11Concentration inequalitiesSSBD B; MRT D; Bach 1.2
Zhang 2; Wainwright 2
M Sep 16Assignment 1 due at noon
M Sep 16PAC learning; covering numbersSSBD 3, MRT 2
Bach 4.4.4, Zhang 3.4/4/5
M Sep 16Drop deadline
W Sep 18Finish covering numbers; start Rademacher
M Sep 23Rademacher complexityMRT 3.1; SSBD 26
Bach 4.5; Zhang 6
M Sep 23Assignment 2 posted (pdf, tex) — PAC, concentration, covering numbers
W Sep 25Finish Rademacher
SuSep 29Assignment 3 posted (pdf, tex) — Rademacher, VC
M Sep 30No class: National Day for Truth and Reconciliation
W Oct  2VC dimensionSSBD 6; MRT 3.2-3.3
M Oct  7Finish VC; Online learning
W Oct  9More online learning; maybe start bandits
F Oct 11Assignment 2 due at 11:59pm
M Oct 14No class: Thanksgiving Day
W Oct 16Bandits
M Oct 21More bandits; maybe start no free lunch
W Oct 23No free lunch / “fundamental theorem”SSBD 5; MRT 3.4
Bach 4.6 / 12; Zhang 12
F Oct 25Withdrawal deadline
F Oct 25Assignment 3 due at 11:59pm
F Oct 25Assignment 4 posted — online learning, bandits, no free lunch
M Oct 28
W Oct 30
M Nov  4
W Nov  6
F Nov  8Assignment 4 due at 11:59pm
F Nov  8Assignment 5 posted — topics TBD
F Nov  8Paper-reading assignment: choice of papers posted
M Nov 11No class: midterm break / Remembrance Day
W Nov 13No class: midterm break
M Nov 18
W Nov 20
M Nov 25
W Nov 27
F Nov 29Assignment 5 due at 11:59pm
M Dec  2
W Dec  4
? Dec ??Final exam (in person, handwritten) — sometime Dec 10-21, likely Dec 16-21 to avoid NeurIPS
? Dec ??Paper-reading assignment oral presentations, to be individually scheduled

Logistics

The course meets in person in Ponderosa Commons North Oak/Cedar House 1011, with possible rare exceptions (e.g. if I get sick but can still teach, I'll move it online). Note that this room does not have a recording setup, but if you need to miss class for some reason and would prefer some form of a janky recording to just reading the lecture notes, talk to me.

Grading scheme: 70% assignments, 30% final.

Overview

Definitely covered: PAC learning, VC dimension, Rademacher complexity, concentration inequalities, margin bounds, stability. Also, most of: PAC-Bayes, analysis of kernel methods, limitations of uniform convergence, analyzing deep nets via neural tangent kernels, provable gaps between kernel methods and deep learning, online learning, feasibility of private learning, compression-based bounds.

Prerequisites

There are no formal prerequisites. TL;DR: if you've done well in CS 340/540 or 440/550, didn't struggle with the probability stuff there, and are also pretty comfortable with proofs, you'll be fine. If not, keep reading.

I will roughly assume the following; if you're missing one of them, you can probably get by, but if you're missing multiple, talk to me about it.

If you have any specific questions about your background, please ask.

Resources

If you need to refresh your linear algebra or other areas of math:

In addition to the books above, some other points of view you might like:

Measure-theoretic probability is not required for this course, but there are instances and related areas where it could be helpful:

Similar courses:

Policies

Academic integrity

The vast majority of you are grad students. One of the primary things about grad school is that the point of classes is to learn things; grades are not the point. If you're a PhD student, they're almost totally irrelevant to your life; if you're a master's student, they barely matter if at all. Cheating, or skirting the boundaries of cheating, does not assist with your learning, but it does potentially set you down a slippery slope towards research miscoduct, which undermines the whole enterprise of science. So, don't cheat; talk to me about what you're struggling with that's making you feel like you need to cheat, and we can figure something out. (Or just take the lower grade.)

You can read more about general UBC policies: Academic Honesty, Academic Misconduct, and Disciplinary Measures. You should also read the Student Declaration and Responsibility to which you've already implicitly agreed.

For the purposes of this class specifically:

Penalties for academic dishonesty can be quite severe (including failing the course or being expelled from the program), and the process is very unpleasant for everyone involved. Please don't.

Positive Space

This course, including class / Piazza / office hours / etc, is a positive space both in the specific sense linked there and also in that I truly hope everyone can feel safe and supported in the class. If anyone other than me is making you feel uncomfortable in any way, please let me know immediately. If I'm the one causing the issue and you would rather speak to someone other than me, please immediately talk to your departmental advisor or a CS department head (currently Margo Seltzer and Joanna McGrenere; email head@cs.ubc.ca.)