Boosting and Differential Privacy
Speaker: Guy Rothblum , Princeton University
Date: October 8 2010
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: We consider a trusted curator who maintains a database of sensitive information about a population of participants, and wants to release privacy-preserving answers to statistical queries about the population. A successful research program has, in the last few years, formulated the rigorous privacy guarantee of differential privacy [Dwork McSherry Nissim and Smith '06] and provided both feasability results and lower bounds for differentially private data analysis.
We introduce new tools for designing differentially private algorithms:
1. A new boosting methodology that lets us improve the accuracy guarantees of weak differentially private algorithms to obtain stronger more accurate algorithms
2. An improved understanding of composition for differentially private analyses. We show that privacy guarantees degrade more slowly under composition than was previously known.
We use these tools to show that, computational complexity aside, differential privacy permits surprisingly rich statistical data analyses. Time permitting, I will also describe computational hardness results and map the boundary between feasability and infeasability for privacy-preserving data analysis.
Based on joint work with Cynthia Dwork and Salil Vadhan.
See other events that are part of CIS Seminars 2010/2011
See other events happening in October 2010
