Lecture Schedule and Notes

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.)
• 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
    • Rogers et al: https://arxiv.org/abs/1604.03924
    • Smith: https://arxiv.org/abs/1706.00820