## Section I: Introduction

- Lecture 1: Introduction, tail bounds for one statistical query
- Reading: Gelman and Loken, “The Garden of Forking Paths” (a.k.a. The Statistical Crisis in Science,
*American Scientist*, v. 102, p. 460–465, 2014.)

- Reading: Gelman and Loken, “The Garden of Forking Paths” (a.k.a. The Statistical Crisis in Science,
- 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

- Amplification via multiple imaginary data sets
- 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
- Rogers et al: https://arxiv.org/abs/1604.03924
- Smith: https://arxiv.org/abs/1706.00820