36-763 · Spring 2026 · Mini-course
Algorithmic Stability
Overview
Description
A natural property that we want from an estimation procedure is stability: a small change in the training data should not lead to a drastic change in the algorithm’s output. Over the years, various notions of algorithmic stability have been proposed, including robustness to outliers, robustness to heavy-tailed data, differential privacy, replicability, replace-one stability, and adaptive generalization. Although these notions appear different at first, they are intimately related. In this theory-oriented course, we will study these notions and the formal connections among them, following many recent papers in the area.
Logistics
Instructor: Ankit Pensia
Course number: 36-763 (Mini-course, Spring 2026)
Times: MW, 10 AM – 11:20 AM
Office hours: M 11:30 AM-12:30 PM (additional appointments are available by email request)
Schedule
| Date | Topic | Reading |
|---|---|---|
| Mar 9 | Course overview: notions of algorithmic stability and their connections | |
| Mar 11 | High-probability estimation I: scalar mean estimation, median-of-means, and Catoni’s estimator | [Cat12][LM19] |
| Mar 16 | High-probability estimation II: multivariate mean estimation, sub-Gaussian rates, and robustness | [LM19][LV20][Hop20][DKP20][HLZ20][PP25][CL25] |
| Mar 18 | Introduction to differential privacy: motivation, definition, post-processing, and composition | [DR14][Duc25, Ch. 8][SU2x] |
| Mar 23 | Basic differential privacy mechanisms: randomized response, Laplace and exponential mechanisms, and approximate DP | [DR14, Ch. 3][Duc25, Ch. 8][SU2x] |
| Mar 25 | Advanced composition, privacy-loss random variables, Gaussian mechanism, and uniform stability | [DR14, Ch. 3][Duc25, Ch. 8] |
| Apr 1 | Differential privacy and robustness I: group privacy, privacy-to-robustness, and propose-test-release | [DL09] |
| Apr 6 | Differential privacy and robustness II: inverse sensitivity and robustness-to-privacy transformations | [AD20][AUZ23][HKMN23] |
| Apr 8 | Differential privacy and robustness III: pure and approximate DP, transformation guarantees, and limits of the equivalence | [AUZ23][HKMN23][CHLLN23] |
| Apr 13 | Differential privacy lower bounds I: packing lower bounds and private mean estimation | [Duc25, Ch. 11] |
| Apr 15 | Differential privacy lower bounds II: fingerprinting arguments and high-dimensional separations | [BUV18][Duc25, Ch. 11] |
| Apr 20 | Replicability I: definitions, statistical-query algorithms, hypothesis testing, and sample-complexity lower bounds | [ILPS22] |
| Apr 22 | Replicability II and privacy: TV indistinguishability, transformations, canonical outputs, stable histograms, and correlated sampling | [BGHILPSS23] |