CSC2412 Algorithms for Private Data Analysis (Fall 2020)

Schedule of Lectures

This year the course will be Quercus (needs U of T access). For those outside U of T who are interested, I will be posting updated reading materials below.

Check out this short list of useful probability theory facts.

[V] denotes Vadhan's notes, and [DR] denotes Dwork and Roth's monograph.

  1. Attacks: reconstruction and tracing attacks against privacy;
    Reading: Notes on Attacks (updated). Also check this survey. Slides.
  2. Differential Privacy: definition; equivalent formulations; Randomized Response;
    Reading: Section 1 of [V], Chapter 2 of [DR]. Slides.
  3. Properties of DP: composition; group privacy; 
    Reading: Section 2 of [V], Sections 3.1-3.2 and beginning of 3.5. Slides.
  4. Laplace and Gaussian noise mechanisms. 
    Reading: Sections 3.3 and Appendix A of [DR]. Slides for Laplace. Slides for Gaussian.
  5. Exponential mechanism: Private PAC learning
    Reading: Sections 3.4, 11.1 of [DR], Section 8.1. of [V]. Slides.
  6. Empirical Risk Minimization: Private Gradient Descent;
    Reading:Lecture notes. Slides.
  7. Privacy and Adaptive Data Analysis: why private data analysis on the sample generalizes to the population;
    Reading: Lecture notes. Slides.
  8. Learning the Database: the multiplicative weight update algorithm;
    Reading: Sections 4.2. of [DR], and Lecture notes (old, wait for an updated version). Slides.
  9. The Projection Mechanism;
    Reading: Section 12.4. of [DR], Sections 7.3. of [V], and Lecture notes.
  10. Class Presentations.