Skip to content
Section I: Introduction
- Lecture 1: Introduction, tail bounds for one statistical query
- Lecture 2: Many nonadaptive queries, uniform convergence, and stochastic optimization.
- Lecture 3: Interactive data analysis, and the dangers of adaptivity.
Section II: Description Length
- Lecture 4 (draft): Description length bounds I: Compressibility and generalization
- Lecture 5 (draft): Description length bounds II: Rounding, AboveThreshold and the Ladder algorithm for a leaderboard
- Lecture 6 (draft): The “median mechanism” and the “reusable holdout” with description length bounds
Section III: Distributional Stability, Privacy, and Information Theory
- Lectures 7-10 (draft): Distributional Stability and Adaptive Data Analysis, part I
- Algorithmic stability
- Expectation bounds on generalization error
- The monitor technique, v1
- Notions of distance on probability measures (TV, KL, multiplicative metric)
- The monitor argument and adaptive statistical queries
- Expected error bounds for the Gaussian mechanism
- Lecture 11 (draft): Differential Privacy and Basic Mechanisms
- Additive noise
- Exponential mechanism and report noisy max
- Lecture 12 (draft): Sparse vector and some applications
- The sparse vector mechanism
- A distributionally stable “guess and check” mechanism
- Application: the median mechanism for modestly-size domains
- Lecture 13 (draft): Strong Composition for Differential Privacy
- Lecture 14 (draft): High-probability guarantees on accuracy
- Amplification via multiple imaginary data sets
- The monitor technique, v2
- Lecture 15-16 (draft): Analysis of Follow the Perturbed Leader using differential privacy, the Multiplicative Weights algorithm, and using no regret algorithms to answer statistical queries.
- Lecture 17-18 (draft): Compression Schemes.
- Lecture 19 (draft): Cryptographic lower bounds, ruling out polynomial time adaptive statistical estimators approaching non-adaptive bounds, and dimension-independent bounds.
- Lecture 20 (draft): Analyzing tracing attacks
- Lecture 21: Information Theoretic Approaches.
- We analyzed an approach based on mutual information on Homework 1 (question 2).
- In class, we discussed generalizations, following the presentation in