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

Lecture: Recorded videos will be released once or twice a week.
Instructor: Gautam Kamath
Office Hours: See calendar
Piazza: Link here. Contact instructor for the code.

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: Nikolov, Some Useful Probability Facts, 2020. Recommended: Pandurangan, On Taxis and Rainbows, 2014. Narayanan and Shmatikov, Robust De-anonymization of Large Sparse Datasets, 2008. Carlini, Liu, Erlingsson, Kos, and Song, The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks, 2019. Optional: Whong, FOILing NYC's Taxi Trip Data, 2014. Homer et al., Resolving Individuals Contributing Trace Amounts of DNA to Highly Complex Mixtures Using High-Density SNP Genotyping Microarrays, 2008. Samarati and Sweeney, Generalizing Data to Provide Anonymity when Disclosing Information, 1998. Ganta, Kasiviswanathan, and Smith, Composition Attacks and Auxiliary Information in Data Privacy, 2008.
2	Reconstruction Attacks	9/10/2020	Part 1 Part 2 Part 3	PDF	PDF	Highly Recommended: Section 8.1 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Garfinkel, Abowd, Martindale, Understanding Database Reconstruction Attacks on Public Data, 2019. Dinur and Nissim, Revealing Information while Preserving Privacy, 2003. Cohen and Nissim, Linear Program Reconstruction in Practice, 2020. Recommended: Abowd, Tweetorial: Reconstruction-abetted re-identification attacks and other traditional vulnerabilities, 2019. Optional: Dwork, McSherry, and Talwar, The Price of Privacy and the Limits of LP Decoding, 2007. Hanson, To Reduce Privacy Risks, the Census Plans to Report Less Accurate Data, 2018.
3	Intro to Differential Privacy, Part 1	9/15/2020	Part 1 Part 2	PDF	PDF	Recommended: Section 1.4-1.6 of Vadhan, The Complexity of Differential Privacy, 2017. Sections 2, 3.1-3.2 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Optional: Dwork, McSherry, Nissim, and Smith, Calibrating Noise to Sensitivity in Private Data Analysis, 2006.
4	Intro to Differential Privacy, Part 2	9/17/2020	Part 1 Part 2	PDF	PDF	Recommended: Section 2 of Vadhan, The Complexity of Differential Privacy, 2017. Section 3.3 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Optional: Dwork, McSherry, Nissim, and Smith, Calibrating Noise to Sensitivity in Private Data Analysis, 2006.
5	Approximate Differential Privacy	9/23/2020	Part 1 Part 2	PDF	PDF	Recommended: Appendix A of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Optional: Dwork, Kenthapadi, McSherry, Mironov, and Naor, Our Data, Ourselves: Privacy via Distributed Noise Generation, 2006.
6	Advanced Composition	9/24/2020	Part 1 Part 2	PDF	PDF	Recommended: Smith, Lecture 13: Strong Composition, 2017. Optional: Sections 3.5.1-3.5.2 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Dwork, Rothblum, Vadhan, Boosting and Differential Privacy, 2010. Kairouz, Oh, Viswanath, The Composition Theorem for Differential Privacy, 2015.
7	Exponential Mechanism	9/30/2020	Part 1 Part 2	PDF	PDF	Recommended: Sections 3.4, 10.1-10.2 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Section 8.1 of Vadhan, The Complexity of Differential Privacy, 2017. McSherry, Talwar, Mechanism Design via Differential Privacy, 2007.
8	Private Multiplicative Weights	10/6/2020	Part 1 Part 2 Part 3	PDF	PDF	Recommended: Roth, Lecture 5 and 6, 2020. Hardt, Rothblum, A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis, 2010. Hardt, Ligett, McSherry, A Simple and Practical Algorithm for Differentially Private Data Release, 2012. Section 4.2 of Vadhan, The Complexity of Differential Privacy, 2017. Sections 4.2 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014.
9	Sparse Vector Technique	10/9/2020	Part 1 Part 2	PDF	PDF	Recommended: Section 3.6 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014.
10	Beyond Global Sensitivity	10/21/2020	Part 1	PDF	PDF	Recommended: Section 3 of Vadhan, The Complexity of Differential Privacy, 2017. Section 7 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Nissim, Raskhodnikova, Smith, Smooth Sensitivity and Sampling in Private Data Analysis, 2007.
11	Packing Lower Bounds	10/23/2020	Part 1	PDF	PDF	Recommended: Section 5.2 of Vadhan, The Complexity of Differential Privacy, 2017. Section 8.2 of Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014. Hardt and Talwar, On the Geometry of Differential Privacy, 2010.
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: Bassily, Smith, Thakurta, Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds, 2014.
14	Modern Machine Learning	11/7/2020	Part 1 Part 2 Part 3	PDF	PDF	Recommended: Abadi, Chu, Goodfellow, McMahan, Mironov, Talwar, Zhang, Deep Learning with Differential Privacy, 2016. Papernot, Abadi, Erlingsson, Goodfellow, Talwar, Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data, 2017. Bassily, Thakkar, Thakurta, Model-Agnostic Private Learning via Stability, 2018.
15	Private Mean Estimation	11/12/2020	Part 1 Part 2 Part 3	PDF	PDF	Recommended: Biswas, Dong, Kamath, Ullman, CoinPress: Practical Private Mean and Covariance Estimation, 2020. Kamath, Singhal, Ullman, Private Mean Estimation of Heavy-Tailed Distributions, 2020. Karwa, Vadhan, Finite Sample Differentially Private Confidence Intervals, 2018.
16	Adaptive Data Analysis	11/18/2020	Part 1 Part 2	See notes by: Sasho Nikolov Thomas Steinke	PDF	Recommended: Jung, Ligett, Neel, Roth, Sharifi-Malvajerdi, Shenfeld, A New Analysis of Differential Privacy's Generalization Guarantees, 2020. Bassily, Nissim, Smith, Steinke, Stemmer, Ullman, Algorithmic Stability for Adaptive Data Analysis, 2016. Dwork, Feldman, Hardt, Pitassi, Reingold, Roth, Preserving Statistical Validity in Adaptive Data Analysis, 2015.
17	Deployments of DP 1: Local Differential Privacy	11/24/2020	Part 1 Part 2	PDF	PDF	Recommended: Erlingsson, Pihur, Korolova, RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response, 2014. Differential Privacy Team, Learning with Privacy at Scale, 2017. Ding, Kulkarni, Yekhanin, Collecting Telemetry Data Privately, 2017.
18	Deployments of DP 2	12/5/2020	Part 1	N/A	N/A	Recommended: Bittau et al., Prochlo: Strong Privacy for Analytics in the Crowd, 2017 Cheu, Smith, Ullman, Zeber, Zhilyaev, Distributed Differential Privacy via Shuffling, 2018 Erlingsson, Feldman, Mironov, Raghunathan, Talwar, Thakurta, Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity, 2018 Rogers et al., LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale, 2020. Rogers et al., A Members First Approach to Enabling LinkedIn's Labor Market Insights at Scale, 2020. Aktay et al., Google COVID-19 Community Mobility Reports: Anonymization Process Description, 2020. Messing et al., Facebook Privacy-Protected Full URLs Data Set, 2020.
19	Differential Privacy in the 2020 US Census	11/30/2020	Part 1, by John Abowd Part 2 (14:25-26:35), by Philip Leclerc	N/A	N/A	Recommended: Disclosure Avoidance and the 2020 Census. Protecting the Confidentiality of America’s Statistics: Adopting Modern Disclosure Avoidance Methods at the Census Bureau. Memorandum 2019.13: Disclosure Avoidance System Design Parameters and Global Privacy-Loss Budget for the 2018 End-to-End Census Test. Memorandum 2019.12: 2020 Disclosure Avoidance System Design Requirement – State Resident Population and the Federally Affiliated Count Overseas (FACO).

Assignments

Problem Set 1, due October 5 by 11:59 PM Waterloo time.
Problem Set 2, due October 27 by 11:59 PM Waterloo time.

Books and References

Don't buy a textbook for this course. But we'll be going off the following resources, and others.

The Algorithmic Foundations of Differential Privacy, by Cynthia Dwork and Aaron Roth
The Complexity of Differential Privacy, by Salil Vadhan

Also check out the Resources page on DifferentialPrivacy.org.

Grading

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

Weekly Quizzes: 5%. These will consist of one or two easy questions, just to make sure you're keeping up with the content.
Two Assignments: 25%. These will be mathematical/proof based.
Paper Summary: 30%. You will be required to carefully and critically read a paper, and provide a "lecture notes" or "expository-focused" style summary. There will be a proposal (not graded) and a final submission. More details forthcoming. Some of the best submissions may be invited to be refined into a post on DifferentialPrivacy.org.
Final Project: 40%. A project may be theoretical, experimental, or a mix of the two. There will be a proposal (not graded) and a final submission. More details forthcoming.

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.