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]

References and Related Courses

[AD20] Paper

Hilal Asi and John C. Duchi. Instance-Optimality in Differential Privacy via Approximate Inverse Sensitivity Mechanisms. 2020. [Link]
[AUZ23] Paper

Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From Robustness to Privacy and Back. 2023. [Link]
[BGHILPSS23] Paper

Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. 2023. [Link]
[BUV18] Paper

Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan. Fingerprinting Codes and the Price of Approximate Differential Privacy. 2018. [Link]
[Cat12] Paper

Olivier Catoni. Challenging the Empirical Mean and Empirical Variance: A Deviation Study. 2010 preprint; published 2012. [Link]
[CHLLN23] Paper

Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, and Shyam Narayanan. The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. 2023. [Link]
[CL25] Paper

Yeshwanth Cherapanamjeri and Daniel Lee. Heavy-tailed Estimation is Easier than Adversarial Contamination. 2025. [Link]
[DKP20] Paper

Ilias Diakonikolas, Daniel M. Kane, and Ankit Pensia. Outlier Robust Mean Estimation with Subgaussian Rates via Stability. 2020. [Link]
[DL09] Paper

Cynthia Dwork and Jing Lei. Differential Privacy and Robust Statistics. 2009. [Link]
[DR14] Book

Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. 2014. [Link]
[Duc25] Course

John Duchi. Lecture Notes on Statistics and Information Theory. 2025. [Link]
[HKMN23] Paper

Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness Implies Privacy in Statistical Estimation. 2023. [Link]
[HLZ20] Paper

Samuel B. Hopkins, Jerry Li, and Fred Zhang. Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization. 2020. [Link]
[Hop20] Paper

Samuel B. Hopkins. Mean Estimation with Sub-Gaussian Rates in Polynomial Time. 2018 preprint; published 2020. [Link]
[ILPS22] Paper

Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in Learning. 2022. [Link]
[LM19] Survey

Gábor Lugosi and Shahar Mendelson. Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey. Foundations of Computational Mathematics, 19(5):1145–1190, 2019. [Link]
[LV20] Paper

Jasper C. H. Lee and Paul Valiant. Optimal Sub-Gaussian Mean Estimation in R. 2020. [Link]
[PP25] Paper

Thanasis Pittas and Ankit Pensia. Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error. 2025. [Link]
[SU2x] Course

Adam Smith and Jonathan Ullman. Differential Privacy Course. [Link]