Lecture Schedule and Notes

  • 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 and Privacy

  • 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-20 (draft): Cryptographic lower bounds, ruling out polynomial time adaptive statistical estimators approaching non-adaptive bounds, and dimension-independent bounds.