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

Algorithmic Stability course schedule and readings
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]