A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis
Authors:
- Moritz HardtMHMoritz Hardt
- Guy N. RothblumGRGuy N. Rothblum
Top Cited Papers
- 1 October 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 61-70
Abstract
We consider statistical data analysis in the interactive setting. In this setting a trusted curator maintains a database of sensitive information about individual participants, and releases privacy-preserving answers to queries as they arrive. Our primary contribution is a new differentially private multiplicative weights mechanism for answering a large number of interactive counting (or linear) queries that arrive online and may be adaptively chosen. This is the first mechanism with worst-case accuracy guarantees that can answer large numbers of interactive queries and is efficient (in terms of the runtime's dependence on the data universe size). The error is asymptotically optimal in its dependence on the number of participants, and depends only logarithmically on the number of queries being answered. The running time is nearly linear in the size of the data universe. As a further contribution, when we relax the utility requirement and require accuracy only for databases drawn from a rich class of databases, we obtain exponential improvements in running time. Even in this relaxed setting we continue to guarantee privacy for any input database. Only the utility requirement is relaxed. Specifically, we show that when the input database is drawn from a smooth distribution - a distribution that does not place too much weight on any single data item - accuracy remains as above, and the running time becomes poly-logarithmic in the data universe size. The main technical contributions are the application of multiplicative weights techniques to the differential privacy setting, a new privacy analysis for the interactive setting, and a technique for reducing data dimensionality for databases drawn from smooth distributions.Keywords
This publication has 10 references indexed in Scilit:
- Boosting and Differential Privacy2010
- Differential privacy under continual observation2010
- Interactive privacy via the median mechanism2010
- Differential privacy and robust statistics2009
- On the complexity of differentially private data release2009
- New Efficient Attacks on Statistical Disclosure Control Mechanisms2008
- A learning theory approach to non-interactive database privacy2008
- The price of privacy and the limits of LP decoding2007
- Revealing information while preserving privacy2003
- The Weighted Majority AlgorithmInformation and Computation, 1994