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

research-article

Subsampled Exponential Mechanism: Differential Privacy in Large Output Spaces

Authors:

David PageAuthors Info & Claims

AISec '15: Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security

Pages 25 - 33

https://doi.org/10.1145/2808769.2808776

Published: 16 October 2015 Publication History

Abstract

In the last several years, differential privacy has become the leading framework for private data analysis. It provides bounds on the amount that a randomized function can change as the result of a modification to one record of a database. This requirement can be satisfied by using the exponential mechanism to perform a weighted choice among the possible alternatives, with better options receiving higher weights. However, in some situations the number of possible outcomes is too large to compute all weights efficiently. We present the subsampled exponential mechanism, which scores only a sample of the outcomes. We show that it still preserves differential privacy, and fulfills a similar accuracy bound. Using a clustering application, we show that the subsampled exponential mechanism outperforms a previously published private algorithm and is comparable to the full exponential mechanism but more scalable.

References

[1]

D. Arthur and S. Vassilvitskii. k-means+: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027--1035. Society for Industrial and Applied Mathematics, 2007.

Digital Library

[2]

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544--562, 2004.

Digital Library

[3]

J. Blocki, A. Blum, A. Datta, and O. Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 87--96. ACM, 2013.

Digital Library

[4]

A. Blum, K. Ligett, and A. Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM (JACM), 60(2):12, 2013.

Digital Library

[5]

J. Chambers. Graphical methods for data analysis. Chapman & Hall statistics series. Wadsworth International Group, 1983.

[6]

K. Chaudhuri and D. J. Hsu. Convergence rates for differentially private statistical estimation. In Proceedings of the 29th International Conference on Machine Learning (ICML-12), pages 1327--1334, 2012.

[7]

K. Chaudhuri and N. Mishra. When random sampling preserves privacy. In Advances in Cryptology-CRYPTO 2006, pages 198--213. Springer, 2006.

Digital Library

[8]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pages 265--284. Springer, 2006.

Digital Library

[9]

C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 51--60. IEEE, 2010.

Digital Library

[10]

A. Friedman and A. Schuster. Data mining with differential privacy. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 493--502. ACM, 2010.

Digital Library

[11]

A. Gupta, K. Ligett, F. McSherry, A. Roth, and K. Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1106--1125. Society for Industrial and Applied Mathematics, Jan. 2010.

[12]

M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems, pages 2339--2347, 2012.

Digital Library

[13]

Z. Ji and C. Elkan. Differential privacy based on importance weighting. Machine learning, 93(1):163--183, 2013.

Digital Library

[14]

V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev. Private analysis of graph structure. Proceedings of the VLDB Endowment, 4(11):1146--1157, 2011.

Digital Library

[15]

S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography, pages 457--476. Springer, 2013.

Digital Library

[16]

L. Kaufman and P. J. Rousseeuw. Finding groups in data: an introduction to cluster analysis. John Wiley & Sons, 1990.

[17]

N. Li, W. Qardaji, and D. Su. On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 32--33. ACM, 2012.

Digital Library

[18]

F. McSherry and K. Talwar. Mechanism design via differential privacy. In Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on, pages 94--103. IEEE, 2007.

Digital Library

[19]

B. I. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft. Learning in a large function space: Privacy-preserving mechanisms for svm learning. arXiv preprint arXiv:0911.5708, 2009.

[20]

L. Wasserman and S. Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375--389, 2010.

[21]

X. Xiao, G. Wang, and J. Gehrke. Differential privacy via wavelet transforms. Knowledge and Data Engineering, IEEE Transactions on, 23(8):1200--1214, 2011.

Digital Library

[22]

J. Zhang, X. Xiao, Y. Yang, Z. Zhang, and M. Winslett. Privgene: differentially private model fitting using genetic algorithms. In Proceedings of the 2013 international conference on Management of data, pages 665--676. ACM, 2013.

Digital Library

Cited By

Di Fazio A(2024)Enhancing Privacy in Recommender Systems through Differential Privacy TechniquesProceedings of the 18th ACM Conference on Recommender Systems10.1145/3640457.3688019(1348-1352)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3640457.3688019
Cunningham TCormode GFerhatosmanoglu HSrivastava D(2021)Real-world trajectory sharing with local differential privacyProceedings of the VLDB Endowment10.14778/3476249.347628014:11(2283-2295)Online publication date: 27-Oct-2021
https://dl.acm.org/doi/10.14778/3476249.3476280
Shafieinejad MKerschbaum FIlyas ILi GLi ZIdreos SSrivastava D(2021)PCOR: Private Contextual Outlier Release via Differentially Private SearchProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452812(1571-1583)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452812
Show More Cited By

Index Terms

Subsampled Exponential Mechanism: Differential Privacy in Large Output Spaces

Recommendations

Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

We give the first polynomial-time algorithm to estimate the mean of a d-variate probability distribution with bounded covariance from Õ(d) independent samples subject to pure differential privacy. Prior algorithms for this problem either incur ...
Implementing the Exponential Mechanism with Base-2 Differential Privacy
CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

Despite excellent theoretical support, Differential Privacy (DP) can still be a challenge to implement in practice. In part, this challenge is due to the concerns associated with translating arbitrary- or infinite-precision theoretical mechanisms to the ...
The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

In this paper we show that for any mechanism design problem with the objective of maximizing social welfare, the exponential mechanism can be implemented as a truthful mechanism while still preserving differential privacy. Our instantiation of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AISec '15: Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security

October 2015

110 pages

ISBN:9781450338264

DOI:10.1145/2808769

General Chair:
Indrajit Ray
Colorado State University, USA
,
Program Chairs:
Christos Dimitrakakis
Chalmers University of Technology, Sweden
,
Aikaterini Mitrokotsa
Chalmers University of Technology, Sweden
,
Arunesh Sinha
University of Southern California, USA
,
Publications Chairs:
Xiaofeng Wang
Indiana University, USA
,
Kui Ren
SUNY Buffalo, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 October 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

US National Library of Medicine

Conference

CCS'15

Sponsor:

SIGSAC

CCS'15: The 22nd ACM Conference on Computer and Communications Security

October 16, 2015

Colorado, Denver, USA

Acceptance Rates

AISec '15 Paper Acceptance Rate 11 of 25 submissions, 44%;

Overall Acceptance Rate 94 of 231 submissions, 41%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
553
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)4

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Di Fazio A(2024)Enhancing Privacy in Recommender Systems through Differential Privacy TechniquesProceedings of the 18th ACM Conference on Recommender Systems10.1145/3640457.3688019(1348-1352)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3640457.3688019
Cunningham TCormode GFerhatosmanoglu HSrivastava D(2021)Real-world trajectory sharing with local differential privacyProceedings of the VLDB Endowment10.14778/3476249.347628014:11(2283-2295)Online publication date: 27-Oct-2021
https://dl.acm.org/doi/10.14778/3476249.3476280
Shafieinejad MKerschbaum FIlyas ILi GLi ZIdreos SSrivastava D(2021)PCOR: Private Contextual Outlier Release via Differentially Private SearchProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452812(1571-1583)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452812
Wang TZheng ZBashir AJolfaei AXu Y(2021)FinPrivacy: A Privacy-preserving Mechanism for Fingerprint IdentificationACM Transactions on Internet Technology10.1145/338713021:3(1-15)Online publication date: 16-Jun-2021
https://dl.acm.org/doi/10.1145/3387130
McKenna RSheldon DLarochelle HRanzato MHadsell RBalcan MLin H(2020)Permute-and-flipProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3495741(193-203)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3495741
Tian FWu ZLiu HLu LGui X(2019)Secure Spatial Query with Differentially Private Access Pattern2019 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA.2019.00073(385-390)Online publication date: Oct-2019
https://doi.org/10.1109/NaNA.2019.00073
Bindschaedler VShokri RGunter C(2017)Plausible deniability for privacy-preserving data synthesisProceedings of the VLDB Endowment10.14778/3055540.305554210:5(481-492)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.14778/3055540.3055542

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents