research-article

Public Access

Private selection from private candidates

Authors:

Kunal TalwarAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 298 - 309

https://doi.org/10.1145/3313276.3316377

Published: 23 June 2019 Publication History

Abstract

Differentially Private algorithms often need to select the best amongst many candidate options. Classical works on this selection problem require that the candidates’ goodness, measured as a real-valued score function, does not change by much when one person’s data changes. In many applications such as hyperparameter optimization, this stability assumption is much too strong. In this work, we consider the selection problem under a much weaker stability assumption on the candidates, namely that the score functions are differentially private. Under this assumption, we present algorithms that are near-optimal along the three relevant dimensions: privacy, utility and computational efficiency.

Our result can be seen as a generalization of the exponential mechanism and its existing generalizations. We also develop an online version of our algorithm, that can be seen as a generalization of the sparse vector technique to this weaker stability assumption. We show how our results imply better algorithms for hyperparameter selection in differentially private machine learning, as well as for adaptive data analysis.

References

[1]

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318. ACM, 2016.

Digital Library

[2]

R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1046–1059. ACM, 2016.

Digital Library

[3]

A. Beimel, K. Nissim, and U. Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 363–378, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.

[4]

R. Bhaskar, S. Laxman, A. Smith, and A. Thakurta. Discovering frequent patterns in sensitive data. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 503–512. ACM, 2010.

Digital Library

[5]

M. Bun, K. Nissim, U. Stemmer, and S. Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS ’15, pages 634–649, Washington, DC, USA, 2015. IEEE Computer Society.

Digital Library

[6]

K. Chaudhuri, D. Hsu, and S. Song. The large margin mechanism for differentially private maximization. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1, NIPS’14, pages 1287–1295, Cambridge, MA, USA, 2014. MIT Press.

Digital Library

[7]

K. Chaudhuri, A. Sarwate, and K. Sinha. Near-optimal differentially private principal components. In Advances in Neural Information Processing Systems, pages 989–997, 2012.

Digital Library

[8]

K. Chaudhuri and S. A. Vinterbo. A stability-based validation procedure for differentially private machine learning. In Advances in Neural Information Processing Systems, pages 2652–2660, 2013.

[9]

C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117–126. ACM, 2015.

Digital Library

[10]

C. Dwork and J. Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371–380. ACM, 2009.

Digital Library

[11]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography (TCC), pages 265–284, 2006.

Digital Library

[12]

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 Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 381–390. ACM, 2009.

Digital Library

[13]

C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.

Digital Library

[14]

C. Dwork, W. Su, and L. Zhang. Private false discovery rate control. arXiv preprint arXiv:1511.03803, 2015.

[15]

V. Garg and A. Kalai. Supervising unsupervised learning. In 32nd Conference on Neural Information Processing Systems (NIPS), 2018. To Appear.

Digital Library

[16]

A. Gelman and E. Loken. The statistical crisis in science. American scientist, 102(6):460, 2014.

[17]

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, SODA ’10, pages 1106–1125, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics.

Digital Library

[18]

A. Gupta, F. McSherry, and K. Talwar. Personal Communication, 2011.

[19]

M. Kapralov and K. Talwar. On differentially private low rank approximation. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1395–1414. SIAM, 2013.

[20]

S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. D. Smith. What can we learn privately? In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 531–540, 2008.

Digital Library

[21]

I. Kotsogiannis, A. Machanavajjhala, M. Hay, and G. Miklau. Pythia: Data dependent differentially private algorithm selection. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1323–1337. ACM, 2017.

Digital Library

[22]

M. Kusner, J. Gardner, R. Garnett, and K. Weinberger. Differentially private bayesian optimization. In Proceedings of the 32nd International Conference on Machine Learning, pages 918–927, 2015.

Digital Library

[23]

J. Lei, A.-S. Charest, A. Slavkovic, A. Smith, and S. Fienberg. Differentially private model selection with penalized and constrained likelihood. Journal of the Royal Statistical Society: Series A (Statistics in Society), 07 2016.

[24]

L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar. Hyperband: Bandit-based configuration evaluation for hyperparameter optimization. In ICLR, 2017.

[25]

K. Ligett, S. Neel, A. Roth, B. Waggoner, and S. Z. Wu. Accuracy first: Selecting a differential privacy level for accuracy constrained erm. In Advances in Neural Information Processing Systems, pages 2566–2576, 2017.

Digital Library

[26]

J. Liu and K. Talwar. Private selection from private candidates. arXiv preprint arXiv:1811.07971, Nov. 2018.

[27]

F. McSherry and K. Talwar. Mechanism design via differential privacy. In Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, October 2007.

Digital Library

[28]

K. Minami, H. Arai, I. Sato, and H. Nakagawa. Differential privacy without sensitivity. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, pages 964–972, USA, 2016. Curran Associates Inc.

Digital Library

[29]

D. J. Mir. Differential privacy: an exploration of the privacy-utility landscape. PhD thesis, Rutgers University-Graduate School-New Brunswick, 2013.

Digital Library

[30]

K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75–84. ACM, 2007.

Digital Library

[31]

N. Papernot, M. Abadi, U. Erlingsson, I. Goodfellow, and K. Talwar. Semisupervised knowledge transfer for deep learning from private training data. arXiv preprint arXiv:1610.05755, 2016.

[32]

S. Raskhodnikova and A. Smith. Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 495–504. IEEE, 2016.

[33]

A. Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 813–822, New York, NY, USA, 2011. ACM.

Digital Library

[34]

A. Smith and A. Thakurta. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Proceedings of the 26th Annual Conference on Learning Theory, pages 819–850, 2013.

[35]

C. Uhlerop, A. Slavković, and S. E. Fienberg. Privacy-preserving data sharing for genome-wide association studies. The Journal of privacy and confidentiality, 5(1):137, 2013.

Cited By

Demelius LKern RTrügler A(2025)Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic SurveyACM Computing Surveys10.1145/371200057:6(1-28)Online publication date: 21-Jan-2025
https://dl.acm.org/doi/10.1145/3712000
Colombo MAsal RDamiani EAlQassem LAlmemari AAlhammadi Y(2025)A quantization-based technique for privacy preserving distributed learningFuture Generation Computer Systems10.1016/j.future.2025.107741167(107741)Online publication date: Jun-2025
https://doi.org/10.1016/j.future.2025.107741
Yu DKairouz POh SXu ZSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Privacy-preserving instructions for aligning large language modelsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694441(57480-57506)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694441
Show More Cited By

Index Terms

Private selection from private candidates

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 ...
Evaluating differentially private decision tree model over model inversion attack
Abstract
Machine learning techniques have been widely used and shown remarkable performance in various fields. Along with the widespread utilization of machine learning, concerns about privacy violations have been raised. Recently, as privacy invasion ...
Differentially Private Feature Selection for Data Mining
IWSPA '18: Proceedings of the Fourth ACM International Workshop on Security and Privacy Analytics

One approach to analysis of private data is ε-differential privacy, a randomization-based approach that protects individual data items by injecting carefully limited noise into results. A challenge in applying this to private data analysis is that the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

June 2019

1258 pages

ISBN:9781450367059

DOI:10.1145/3313276

General Chair:
Moses Charikar
Stanford University
,
Program Chair:
Edith Cohen
Google, USA / Tel Aviv University, Israel

Copyright © 2019 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

STOC '19

Sponsor:

SIGACT

STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing

June 23 - 26, 2019

AZ, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
1,409
Total Downloads

Downloads (Last 12 months)351
Downloads (Last 6 weeks)43

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Demelius LKern RTrügler A(2025)Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic SurveyACM Computing Surveys10.1145/371200057:6(1-28)Online publication date: 21-Jan-2025
https://dl.acm.org/doi/10.1145/3712000
Colombo MAsal RDamiani EAlQassem LAlmemari AAlhammadi Y(2025)A quantization-based technique for privacy preserving distributed learningFuture Generation Computer Systems10.1016/j.future.2025.107741167(107741)Online publication date: Jun-2025
https://doi.org/10.1016/j.future.2025.107741
Yu DKairouz POh SXu ZSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Privacy-preserving instructions for aligning large language modelsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694441(57480-57506)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694441
Xian RLi QKamath GZhao HSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Differentially private post-processing for fair regressionProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694296(54212-54235)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694296
Sander TYu YSanjabi MDurmus AMa YChaudhuri KGuo CSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Differentially private representation learning via image captioningProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693832(43255-43275)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693832
Lowy ALi ZHuang TRazaviyayn MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Optimal differentially private model training with public dataProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693404(32849-32903)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693404
Lalanne CGadat SSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Privately learning smooth distributions on the hypercube by projectionsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693108(25936-25975)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693108
Koskela ARedberg RWang YSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Privacy profiles for private selectionProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693084(25313-25332)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693084
Tang SAydore SKearns MRho SRoth AWang YWang YWu Z(2024)Improved Differentially Private Regression via Gradient Boosting2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00011(33-56)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00011
Schulze MZisgen YKirschte MMohammadi EKoschmider A(2024)Differentially Private Inductive Miner2024 6th International Conference on Process Mining (ICPM)10.1109/ICPM63005.2024.10680684(89-96)Online publication date: 14-Oct-2024
https://doi.org/10.1109/ICPM63005.2024.10680684
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten