Document Open Access Logo

Generalized Private Selection and Testing with High Confidence

Authors Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.39.pdf
  • Filesize: 0.84 MB
  • 23 pages

Document Identifiers

Author Details

Edith Cohen
  • Google Research, Mountain View, CA, USA
  • Tel Aviv University, Israel
Xin Lyu
  • UC Berkeley, CA, USA
  • Google Research, Mountain View, CA, USA
Jelani Nelson
  • UC Berkeley, CA, USA
  • Google Research, Mountain View, CA, USA
Tamás Sarlós
  • Google Research, Mountain View, CA, USA
Uri Stemmer
  • Tel Aviv University, Israel
  • Google Research, Herzliya, Israel

Funding

  • Cohen, Edith: Partially supported by Israel Science Foundation (grant no. 1595/19).
  • Lyu, Xin: Most of the work was done while interning at Google.
  • Stemmer, Uri: Partially supported by the Israel Science Foundation (grant 1871/19) and by Len Blavatnik and the Blavatnik Family foundation.

Cite As Get BibTex

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Generalized Private Selection and Testing with High Confidence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.39

Abstract

Composition theorems are general and powerful tools that facilitate privacy accounting across multiple data accesses from per-access privacy bounds. However they often result in weaker bounds compared with end-to-end analysis. Two popular tools that mitigate that are the exponential mechanism (or report noisy max) and the sparse vector technique, generalized in a recent private selection framework by Liu and Talwar (STOC 2019). In this work, we propose a flexible framework of private selection and testing that generalizes the one proposed by Liu and Talwar, supporting a wide range of applications. We apply our framework to solve several fundamental tasks, including query releasing, top-k selection, and stable selection, with improved confidence-accuracy tradeoffs. Additionally, for online settings, we apply our private testing to design a mechanism for adaptive query releasing, which improves the sample complexity dependence on the confidence parameter for the celebrated private multiplicative weights algorithm of Hardt and Rothblum (FOCS 2010).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • differential privacy
  • sparse vector technique
  • adaptive data analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • The arXiv version has a substantially revised introduction, which includes a more accurate survey and comparison with prior works.
  • Full Version https://arxiv.org/abs/2211.12063

References

  1. Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 1046-1059. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897566.
  2. Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. Theory Comput., 12(1):1-61, 2016. URL: https://doi.org/10.4086/toc.2016.v012a001.
  3. Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 74-86. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188946.
  4. Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. IEEE Trans. Inf. Theory, 67(3):1981-2000, 2021. URL: https://doi.org/10.1109/TIT.2021.3049802.
  5. Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 1-10, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591877.
  6. Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Generalized private selection and testing with high confidence, 2022. URL: http://arxiv.org/abs/2211.12063.
  7. Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy. CoRR, abs/2012.03817, 2020. URL: http://arxiv.org/abs/2012.03817.
  8. Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2597-2606. PMLR, 13-18 July 2020. URL: https://proceedings.mlr.press/v119/dong20a.html.
  9. David Durfee and Ryan M. Rogers. Practical differentially private top-k selection with pay-what-you-get composition. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3527-3537, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/b139e104214a08ae3f2ebcce149cdf6e-Abstract.html.
  10. Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 117-126, 2015. Google Scholar
  11. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. J. Priv. Confidentiality, 7(3):17-51, 2016. Google Scholar
  12. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil 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, STOC '09, pages 381-390, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1536414.1536467.
  13. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407, 2014. URL: https://doi.org/10.1561/0400000042.
  14. Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51-60. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.12.
  15. Arun Ganesh and Jiazheng Zhao. Privately Answering Counting Queries with Generalized Gaussian Mechanisms. In Katrina Ligett and Swati Gupta, editors, 2nd Symposium on Foundations of Responsible Computing (FORC 2021), volume 192 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-1:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.FORC.2021.1.
  16. Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 89-99. PMLR, 2020. URL: http://proceedings.mlr.press/v108/geng20a.html.
  17. Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/299dc35e747eb77177d9cea10a802da2-Abstract.html.
  18. Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On avoiding the union bound when answering multiple differentially private queries. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2133-2146. PMLR, 2021. URL: http://proceedings.mlr.press/v134/ghazi21a.html.
  19. Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1106-1125. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.90.
  20. Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 61-70. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.85.
  21. Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2263-2285. PMLR, 2020. URL: http://proceedings.mlr.press/v125/kaplan20a.html.
  22. Haim Kaplan, Yishay Mansour, and Uri Stemmer. The sparse vector technique, revisited. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2747-2776. PMLR, 2021. URL: http://proceedings.mlr.press/v134/kaplan21a.html.
  23. Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 298-309. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316377.
  24. Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proc. VLDB Endow., 10(6):637-648, 2017. URL: https://doi.org/10.14778/3055330.3055331.
  25. Ryan McKenna and Daniel Sheldon. Permute-and-flip: A new mechanism for differentially private selection. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. Google Scholar
  26. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 94-103. IEEE Computer Society, 2007. URL: https://doi.org/10.1109/FOCS.2007.41.
  27. Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pages 263-275. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/CSF.2017.11.
  28. Jack Murtagh and Salil P. Vadhan. The complexity of computing the optimal composition of differential privacy. Theory Comput., 14(1):1-35, 2018. URL: https://doi.org/10.4086/toc.2018.v014a008.
  29. Sewoong Oh and Pramod Viswanath. The composition theorem for differential privacy. CoRR, abs/1311.0776, 2013. URL: http://arxiv.org/abs/1311.0776.
  30. Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with Rényi differential privacy. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL: https://openreview.net/forum?id=-70L8lpp9DF.
  31. Gang Qiao, Weijie J. Su, and Li Zhang. Oneshot differentially private top-k selection. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8672-8681. PMLR, 2021. URL: http://proceedings.mlr.press/v139/qiao21b.html.
  32. Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 765-774. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806794.
  33. Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 552-563, 2017. URL: https://doi.org/10.1109/FOCS.2017.57.
  34. Thomas Steinke and Jonathan Ullman. Open problem - avoiding the union bound for multiple queries. DifferentialPrivacy.org, October 2020. URL: https://differentialprivacy.org/open-problem-avoid-union/.
  35. Thomas Steinke and Jonathan R. Ullman. Between pure and approximate differential privacy. J. Priv. Confidentiality, 7(2), 2016. URL: https://doi.org/10.29012/jpc.v7i2.648.
  36. Salil P. Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 347-450. Springer International Publishing, 2017. URL: https://doi.org/10.1007/978-3-319-57048-8_7.
  37. Yuqing Zhu and Yu-Xiang Wang. Improving sparse vector technique with Renyi differential privacy. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/e9bf14a419d77534105016f5ec122d62-Abstract.html.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact