More Web Proxy on the site http://driver.im/

Article

A simple and practical algorithm for differentially private data release

Authors:

Katrina Ligett,

Frank McSherryAuthors Info & Claims

NIPS'12: Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 2

Pages 2339 - 2347

Published: 03 December 2012 Publication History

Abstract

We present a new algorithm for differentially private data release, based on a simple combination of the Multiplicative Weights update rule with the Exponential Mechanism. Our MWEM algorithm achieves what are the best known and nearly optimal theoretical guarantees, while at the same time being simple to implement and experimentally more accurate on actual data sets than existing techniques.

References

[1]

I. Dinur and K. Nissim. Revealing information while preserving privacy. In PODS, 2003.

[2]

Cynthia Dwork and Kobbi Nissim. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO. Springer, 2004.

[3]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006.

[4]

Cynthia Dwork. The differential privacy frontier (extended abstract). In TCC, 2009.

[5]

Cynthia Dwork. The promise of differential privacy: A tutorial on algorithmic techniques. In FOCS, 2011.

[6]

Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006, 1998.

[7]

Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the SuLQ framework. In Proc. 24th PODS, pages 128-138. ACM, 2005.

[8]

Moritz Hardt and Guy Rothblum. A multiplicative weights mechanism for interactive privacy-preserving data analysis. In FOCS, 2010.

[9]

Anupam Gupta, Moritz Hardt, Aaron Roth, and Jon Ullman. Privately releasing conjunctions and the statistical query barrier. In STOC, 2011.

[10]

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, 2007.

[11]

Chao Li and Gerome Miklau. Efficient batch query answering under differential privacy. CoRR, abs/1103.1367, 2011.

[12]

Chao Li and Gerome Miklau. An adaptive mechanism for accurate query answering under differential privacy. to appear, PVLDB, 2012.

[13]

Stephen E. Fienberg, Alessandro Rinaldo, and Xiolin Yang. Differential privacy and the risk-utility tradeoff for multi-dimensional contingency tables. In Privacy in Statistical Databases, 2010.

[14]

Bolin Ding, Marianne Winslett, Jiawei Han, and Zhenhui Li. Differentially private data cubes: optimizing noise sources and consistency. In SIGMOD, 2011.

[15]

Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, 2009.

[16]

Jonathan Ullman and Salil P. Vadhan. PCPs and the hardness of generating private synthetic data. In TCC, 2011.

[17]

C. Dwork, M. Naor, O. Reingold, G.N. Rothblum, and S. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, 2009.

[18]

Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In STOC, 2008.

[19]

Cynthia Dwork, Guy Rothblum, and Salil Vadhan. Boosting and differential privacy. In FOCS, 2010.

[20]

Aaron Roth and Tim Roughgarden. The median mechanism: Interactive and efficient privacy with multiple queries. In STOC, 2010.

[21]

B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In PODS, 2007.

[22]

C. Li, M. Hay, V. Rastogi, G. Miklau, and A. McGregor. Optimizing linear counting queries under differential privacy. In PODS, 2010.

[23]

Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. Differential privacy via wavelet transforms. IEEE Transactions on Knowledge and Data Engineering, 23:1200-1214, 2011.

[24]

Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially-private queries through consistency. In VLDB, 2010.

[25]

Chao Li and Gerome Miklau. Measuring the achievable error of query sets under differential privacy. CoRR, abs/1202.3399v2, 2012.

[26]

A. Frank and A. Asuncion. UCI machine learning repository, 2010.

[27]

I-Cheng Yeh, King-Jang Yang, and Tao-Ming Ting. Knowledge discovery on RFM model using Bernoulli sequence. Expert Systems with Applications, 36(3), 2008.

Cited By

Liu TTang JVietri GWu ZKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Generating private synthetic data with genetic algorithmsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619321(22009-22027)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619321
Liu YSuresh AZhu WKairouz PGruteser MKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Algorithms for bounding contribution for histogram estimation under user-level privacyAlgorithms for bounding contribution for histogram estimation under user-level privacyProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619319(21969-21996)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619319
Vietri GArchambeau CAydore SBrown WKearns MRoth ASiva ATang SWu ZKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Private synthetic data for multitask learning and marginal queriesProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601599(18282-18295)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601599
Show More Cited By

Recommendations

A differentially private algorithm for location data release

The rise of mobile technologies in recent years has led to large volumes of location information, which are valuable resources for knowledge discovery such as travel patterns mining and traffic analysis. However, location dataset has been confronted ...
On the complexity of differentially private data release: efficient algorithms and hardness results
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set that simultaneously protects the ...
Differentially private data release for data mining
KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

Privacy-preserving data publishing addresses the problem of disclosing sensitive data when mining for useful information. Among the existing privacy models, ∈-differential privacy provides one of the strongest privacy guarantees and has no assumptions ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

NIPS'12: Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 2

December 2012

3328 pages

Publisher

Curran Associates Inc.

Red Hook, NY, United States

Publication History

Published: 03 December 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu TTang JVietri GWu ZKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Generating private synthetic data with genetic algorithmsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619321(22009-22027)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619321
Liu YSuresh AZhu WKairouz PGruteser MKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Algorithms for bounding contribution for histogram estimation under user-level privacyAlgorithms for bounding contribution for histogram estimation under user-level privacyProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619319(21969-21996)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619319
Vietri GArchambeau CAydore SBrown WKearns MRoth ASiva ATang SWu ZKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Private synthetic data for multitask learning and marginal queriesProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601599(18282-18295)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601599
Dong WFang JYi KTao YMachanavajjhala AIves ZBonifati AEl Abbadi A(2022)R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign KeysProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517844(759-772)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517844
Abowd JAshmead RCumings-Menon RGarfinkel SKifer DLeclerc PSexton WSimpson ATask CZhuravlev PRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)An uncertainty principle is a price of privacy-preserving microdataProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541170(11883-11895)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541170
Cai KLei XWei JXiao X(2021)Data synthesis via differentially private markov random fieldsProceedings of the VLDB Endowment10.14778/3476249.347627214:11(2190-2202)Online publication date: 27-Oct-2021
https://dl.acm.org/doi/10.14778/3476249.3476272
Xiao YDing ZWang YZhang DKifer D(2021)Optimizing fitness-for-use of differentially private linear queriesProceedings of the VLDB Endowment10.14778/3467861.346786414:10(1730-1742)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.14778/3467861.3467864
Ji TLi PYilmaz EAyday EYe YSun J(2021)Differentially private binary- and matrix-valued data queryProceedings of the VLDB Endowment10.14778/3446095.344610614:5(849-862)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.14778/3446095.3446106
Vietri GTian GBun MSteinke TWu ZDaumé HSingh A(2020)New oracle-efficient algorithms for private synthetic data releaseProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525843(9765-6774)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525843
Chowdhury ARekatsinas TJha SDaumé HSingh A(2020)Data-dependent differentially private parameter learning for directed graphical modelsProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525119(1939-1951)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525119
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents