Privacy-Preserving Machine Learning (CSE 5479)

Fall 2018

Venue: Caldwell Lab 177

Time: Fridays, 4:45-6:30 PM

Course forum on Piazza: Sign up 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 (Google, Apple, and Uber). We will also highlight some limitations with the existing tools and discuss several new efforts to fully extend the power of differential privacy to the area of deep learning.

Goals:

The goal of this course is to introduce students to the burgeoning area of privacy-preserving machine learning and data analysis, and mainly to differential privacy. This course aim to help students take up a research career in data privacy, or pursue industry positions in privacy engineering, of which there has been increasing demand especially in big corporations such as Google, Apple, Uber and many others. 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.

Pre-requisites:

  • Highly recommended (CSE 5523 or STAT 3470) and CSE 5331 (or equivalent)

If you have not taken one of these classes, but you feel confident you have the knowledge from other sources/courses, you can still enroll.

  • Good mathematical background in probability, algorithms (including randomized algorithms), linear algebra and calculus is required.

Evaluation:

  • 35% Active participation (Class + Piazza)
  • 15% Mid-term assignment.
  • 50% Project (also has its own presentation to be held during the last 2 weeks of class)

Project

  • Semester long project on a topic in privacy

(see possible topics and some relevant papers in the References section below).

  • Suggestions: implementation of differentially private algorithms for one of the following applications i) supervised learning task, e.g., training SVM classifier, or linear regression, ii) an application in the distributed setting of private data analysis , iii) deep learning application. See more specific suggestions here.
  • It's a group project: 2-3 students/group
  • Project components:

– Mid-term check (discussion with groups during office hours)

– Final Report: a) Introduction: literature review + motivation, b) Problem statement, c) Proposed solution/implementation and Results.

– Project presentation: ~ 25-30 min. per group during the last 2 weeks of class.

References

Textbook and survey papers:

Relevant papers (non-exhaustive, listed by topic):

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.

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.