Course site: OSU Carmen.
Course syllabus here.
One of the most salient features of Big Data is the dissemination of huge amounts of personal and sensitive data. Despite their enormous societal benefits, new powerful tools of machine learning such as deep learning pose real threats to personal privacy. Heuristic approaches to deal with the privacy problem such as data anonymization are at best unreliable: the last decade has seen a string of attacks that recover personal information from supposedly "anonymized" data.
The last decade has witnessed the rise of a rigorous theory to deal with this challenge. This theory is centered around a meaningful and robust mathematical definition for privacy, known as Differential Privacy. Differential privacy is a rigorous mathematical framework whose goal is to enable designing new algorithms that can provide provable privacy guarantees for their input sensitive data sets while producing highly accurate analyses and models based on such sensitive data. A powerful algorithmic framework for differential privacy has been developed over the years, and led to numerous practical and efficient algorithms with strong and provable privacy guarantees for various applications in machine learning, data mining, and statistics. Differential privacy has recently made it to the industrial domain with several successful adoptions, notably by Google, Apple, and Uber. Differential privacy will also be adopted by the U.S. Census starting in 2020. On the other hand, there are several limitations with the existing tools in differential privacy that call for a new creative solutions.
This class will start by demonstrating the need for a rigorous privacy framework via several examples that led to high-profile privacy breaches. I will then introduce differential privacy, discuss the semantics of its guarantees, and discuss powerful algorithmic techniques in the literature of differential privacy for design efficient, scalable algorithms satisfying this solid privacy guarantee for several important applications in machine learning and statistical data analysis. This includes discussion of algorithms that have been deployed in industry (e.g., by Google and Apple). We will also highlight some limitations with the existing tools and discuss several new efforts to fully extend the power of differential privacy to various areas of data analysis and machine learning.
The goal of this course is to introduce students to the burgeoning area of privacy-preserving data analysis, and mainly to differential privacy. This course aim to help students take up a research career in data privacy. At the end of this course, students are expected to have a solid understanding of the foundational concepts of private data analysis, and have a good grasp of the design principles of practical and useful algorithms that provide strong and provable privacy guarantees for various modern data applications.
The course will involve mathematical abstractions, rigorous analyses, and proofs. The course requires certain prior knowledge and skills together with a decent level of mathematical maturity:
Solid background in probability and statistics is STRICTLY required (STAT 3470 or above)
Solid background in Linear Algebra (MATH 2568) and Advanced Calculus (MATH 3345 or above) is STRICTLY required.
Strong background in principles of algorithm design and analysis (e.g., CSE 2331/5331).
Prior exposure to machine learning (e.g., CSE 5522 or CSE 5523) is recommended.
Mathematical maturity: Comfort in working with mathematical abstractions and proofs is EXTREMELY CRUCIAL to succeed and to enjoy this class.
10% Active participation.
20% HWs. (Tentatively 3-4 HW assignments in total. Problems will involve proofs and theoretical analyses. HWs will be posted on Carmen).
20% Presentation of a research paper in class. (Specific suggestions for papers will be announced on Carmen).
50% Project.
Semester-long project on a topic in privacy
could be either (i) an implementation of a differentially private algorithm for one of the applications/problems discussed in class (or a new application/problem), or (ii) a technical report that either solves a well-defined research problem, or provides a decent survey of existing research on one of the problems in the area of differential privacy.
Depending on the size of the class and the scope of the project, students may be allowed to collaborate with at most 2 of their peers on their project. Groups involving more than one student must take my permission before forming the group.
Project components:
– Mid-term check (discussion with groups during office hours before Spring break).
– Final Report: a) Introduction: literature review + motivation, b) Problem statement, c) Proposed solution/implementation and Results.
Various useful references, survey articles, videos, workshops materials, and other related courses can be found at DifferentialPrivacy.org
Cynthia Dwork and Aaron Roth, "The Algorithmic Foundations of Differential Privacy,” Foundations and Trends in Theoretical Computer Science .
Nissim et al., "Differential Privacy: A Primer for a Non-technical Audience," (This is meant to be understood by a general audience, and may serve as a gentle introduction to differential privacy. It also sheds some light on the legal issues of privacy).
Salil Vadhan, "The Complexity of Differential Privacy" (a nice survey with some emphasis on the computational aspects of differentially private algorithms.)
Attacks on Privacy:
[NS06] : Narayanan and Shmatikov, Robust De-anonymization of Large Datasets: How to Break Anonymity of the Netflix Prize Dataset.
[CKNFS11] : Calandrino et al., “You Might Also Like:” Privacy Risks of Collaborative Filtering.
[Korolova11] : Korolova, Privacy Violations Using Microtargeted Ads: A Case Study.
[CCPS15] : Conti et al., TRAP: using TaRgeted Ads to unveil Google personal Profiles.
[SSSS17] : Shokri et al., Membership Inference Attacks Against Machine Learning Models.
Early papers: definitions, basic mechanisms, properties
[DN03] : Dinur, Nissim, Revealing Information while Preserving Privacy.
[DMNS06] : Dwork, McSherry, Nissim, Smith, Calibrating Noise to Sensitivity in Private Data Analysis.
[DKMMN06] : Dwork, Kenthapadi, McSherry, Mironov, Noar, Our Data, Ourselves: Privacy via Distributed Noise Generation.
More tools and algorithmic techniques
[MT07] : McSherry, Talwar, Mechanism Design via Differential Privacy.
[NRS07] : Nissim, Raskhodnikova, Smith, Smooth Sensitivity and Sampling in Private Data Analysis.
[DL09] : Dwork, Lei, Differential Privacy and Robust Statistics.
[RR10] : Roth, Roughgarden, Interactive Privacy via the Median Mechanism.
[HR10] : Hardt, Rothblum, A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis.
[DRV10] : Dwork, Rothblum, Vadhan, Boosting and Differential Privacy.
[NTZ12] : Nikolov, Talwar, Zhang, The Geometry of Differential Privacy: The Sparse and Approximate Cases.
[ST13] : Smith, Thakurta, Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso.
Differentially private machine learning
[KLNRS08]: Kasiviswanathan, Lee, Nissim, Raskhodnikova, Smith, What can we learn privately?
[CMS11]: Chaudhuri, Monteleoni, Sarwate, Differentially private empirical risk minimization.
[BKN13]: Beimel, Kasiviswanathan, Nissim, Bounds on the Sample Complexity for Private Learning and Private Data Release.
[BNS13]: Beimel, Nissim, Stemmer, Characterizing the Sample Complexity of Private Learners.
[ST13] : Smith, Thakurta, Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso.
[BST14]: Bassily, Smith, Thakurta, Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds.
[BNSV15]: Bun, Nissim, Stemmer, Vadhan, Differentially Private Release and Learning of Threshold Functions.
[SS15]: Shokri, Shmatikov, Privacy-Preserving Deep Learning.
[ACG+16]: Papernot, Abadi, Erlingsson, Goodfellow, McMahan, Mironov, Talwar, Zhang. Deep Learning with Differential Privacy.
[PAEGT17]: Papernot, Abadi, Erlingsson, Goodfellow, Talwar, Semi-Supervised Knowledge Transfer for Deep Learning from Private Training Data.
[BTT18]: Bassily, Thakkar, Thakurta, Model-Agnostic Private Learning.
[BFTT19]: Bassily, Feldman, Talwar, Thakurta, Private Stochastic Convex Optimization with Optimal Rates.
[ABM19]: Alon, Bassily, Moran, Limits of Private Learning with Access to Public Data.
Local (Distributed) Model of Differential Privacy
[HKR12]: Hsu, Khanna, Roth, Distributed Private Heavy Hitters.
[DJW13]: Duchi, Jordan, Wainwright, Local Privacy, Data Processing Inequalities, and Minimax Rates.
[EKP14]: Erlingsson, Korolova, Pihur, RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response.
[BS15]: Bassily, Smith, Local, Private, Efficient Protocols for Succinct Histograms.
[BNST17]: Bassily, Nissim, Stemmer, Thakurta, Practical Locally Private Heavy Hitters.
Differential Privacy for Streaming
[DNPR10]: Dwork, Naor, Pitassi, Rothblum, Differential Privacy Under Continual Observation.
[CSS11]: Chan, Shi, Song, Private and Continual Release of Statistics.
Lower Bounds (Limits of Differential Privacy)
[HT10]: Hardt, Talwar, On the Geometry of Differential Privacy.
[De11]: De, Lower bounds in differential privacy.
[BUV14]: Bun, Ullman, Vadhan, Fingerprinting Codes and the Price of Approximate Differential Privacy.
[BST14]: Bassily, Smith, Thakurta, Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds.
Relaxations of Differential Privacy (Non-worst case definitions allowing for distributional assumptions)
[BBGLT12]: Bhaskar et al., Noiseless Database Privacy.
[KM12]: Kifer, Machanavajjhala, A Rigorous and Customizable Framework for Privacy.
[BGKS13]: Bassily, Groce, Katz, Smith, Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy.
[BF16]: Bassily, Freund, Typical Stability.
Differential Privacy for Robust Adaptive Data Analysis
[DFHPRR15-a]: Dwork, Feldman, Hardt, Pitassi, Reingold, Roth, Preserving Statistical Validity in Adaptive Data Analysis.
[BNSSSU16]: Bassily, Nissim, Smith, Steinke, Stemmer, Ullman, Algorithmic Stability for Adaptive Data Analysis.
[DFHPRR15-b]: Dwork, Feldman, Hardt, Pitassi, Reingold, Roth, Generalization in Adaptive Data Analysis and Holdout Reuse.
[CLNRW16]: Cummings, Ligett, Nissim, Roth, Wu, Adaptive Learning with Robust Generalization Guarantees.
[RRST16]: Rogers, Roth, Smith, Thakkar, Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing.
[FS17-a]: Feldman, Steinke, Generalization for Adaptively-chosen Estimators via Stable Median.
[FS17-b]: Feldman, Steinke, Calibrating Noise to Variance in Adaptive Data Analysis.