CS 860 - Algorithms for Private Data Analysis - Fall 2020

Course Description

This course is on algorithms for differentially private analysis of data. As necessitated by the nature of differential privacy, this course will be theoretically and mathematically based. References to practice will be provided as relevant, especially towards the end of the course. Prerequisites include an undergraduate understanding of algorithms, comfort with probability, and mathematical maturity.

Logistics

This course has a Piazza (for discussion), Google Groups email list (for announcements), and a Microsoft Teams (for live sessions and/or office hours). Please contact the instructor if you are not in all of these.

Weekly Schedule

There will be two lectures posted each week, tentatively on Tuesday and Thursday.
There will be a quiz posted each week, simultaneously with the second lecture. It will be due by the first lecture of the following week (no earlier than Tuesday).

Lectures

Lecture Number Topic Release Date Video Link Lecture Notes Written Notes References and Readings
1 Some Attempts at Data Privacy 9/8/2020 Part 1
Part 2
PDF PDF Required: Recommended: Optional:
2 Reconstruction Attacks 9/10/2020 Part 1
Part 2
Part 3
PDF PDF Highly Recommended: Recommended: Optional:
3 Intro to Differential Privacy, Part 1 9/15/2020 Part 1
Part 2
PDF PDF Recommended: Optional:
4 Intro to Differential Privacy, Part 2 9/17/2020 Part 1
Part 2
PDF PDF Recommended: Optional:
5 Approximate Differential Privacy 9/23/2020 Part 1
Part 2
PDF PDF Recommended: Optional:
6 Advanced Composition 9/24/2020 Part 1
Part 2
PDF PDF Recommended: Optional:
7 Exponential Mechanism 9/30/2020 Part 1
Part 2
PDF PDF Recommended:
8 Private Multiplicative Weights 10/6/2020 Part 1
Part 2
Part 3
PDF PDF Recommended:
9 Sparse Vector Technique 10/9/2020 Part 1
Part 2
PDF PDF Recommended:
10 Beyond Global Sensitivity 10/21/2020 Part 1
PDF PDF Recommended:
11 Packing Lower Bounds 10/23/2020 Part 1
PDF PDF Recommended:
12 What is a Privacy Violation? 10/28/2020 Part 1
PDF None None
13 Differentially Private ERM 11/4/2020 Part 1
Part 2
Part 3
PDF PDF Recommended:
14 Modern Machine Learning 11/7/2020 Part 1
Part 2
Part 3
PDF PDF Recommended:
15 Private Mean Estimation 11/12/2020 Part 1
Part 2
Part 3
PDF PDF Recommended:
16 Adaptive Data Analysis 11/18/2020 Part 1
Part 2
See notes by:
Sasho Nikolov
Thomas Steinke
PDF Recommended:

Assignments

Books and References

Don't buy a textbook for this course. But we'll be going off the following resources, and others. Also check out the Resources page on DifferentialPrivacy.org.

Grading

Grades for this course will be determined with the following breakdown:

Acknowledgments

This course has been greatly improved via conversations with and guidance from many individuals, including Sasho Nikolov, Aaron Roth, Adam Smith, Thomas Steinke, and Jonathan Ullman.