Course Description

The practical applicability of data analysis to sciences and decision-making is often limited by individual privacy concerns. Some of the most interesting data sets - medical studies, genetic data, movie reviews, search logs, social network connections - contain sensitive information about people represented in the data set. If individuals do not think their privacy concerns are addressed, they may refuse to participate in data collection, or not answer surveys truthfully. These issues limit the validity of the data analysis results, and make balancing privacy and usefulness essential to many applications of big data. In this course we will study privacy in data analysis from a rigorous theoretical perspective. We will focus on Differential Privacy: a recent approach to achieving strong provable privacy guarantees in the analysis of sensitive data. Informally, a data analysis algorithm is differentially private if changing the data of a single individual changes the output distribution of the algorithm only slightly. This guarantee ensures that the privacy risk to any individual increases only slightly by participating in data collection. Our focus will be on the design of efficient differentially private algorithms, but we will also look at some negative results that show the limits of private data analysis. In the process, we will learn about fascinating connections between differential privacy and game theory, learning theory, and geometry.

This is a theoretical, proof-based course. It will require mathematical maturity and a solid background in probability theory, and the design and analysis of algorithms.

Scribe Notes

Use this template for your scribe notes. Do not forget to fill in the lecture number, the date, and your name. The notes should read like a self-contained text and include everything that was covered in class (rather than just record what was on the board). Please contact me if anything in the lecture you are scribing was not clear. I expect the first draft of the notes the Sunday before the meeting of the next class, so that people who have missed a lecture can look over them.

Problem Set and Papers for Presentation

Problem set for homework. The problem set is due on the last day of class.

Here is a suggested list of papers. You can use the list to choose a paper to present. The presentation will be 20 minutes, with 5 minutes for questions. You do not have to use a paper from the list: it's meant as resource, not a constraint. Please email me the paper you choose to present by March 25th.

Doodle poll for a make up class: https://beta.doodle.com/poll/m9i5dkfpus8cc65k. The plan is to meet for an hour and have two presentations. The other four presentations will be on the last day of class.