Private counting of distinct elements in the turnstile model and extensions
Henzinger MH, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Sricharan, A. R.;
Steiner, Teresa Anna
Corresponding author has ISTA affiliation
Department
Grant
Series Title
LIPIcs
Abstract
Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level (ε,δ)-differential privacy and item-level ε-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023].
Publishing Year
Date Published
2024-09-16
Proceedings Title
International Conference on Approximation Algorithms for Combinatorial Optimization Problems
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Acknowledgement
Monika Henzinger: This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.
Teresa Anna Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN.
Volume
317
Article Number
40
Conference
APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems
Conference Location
London, United Kingdom
Conference Date
2024-08-27 – 2024-08-30
ISBN
ISSN
IST-REx-ID
Cite this
Henzinger MH, Sricharan AR, Steiner TA. Private counting of distinct elements in the turnstile model and extensions. In: International Conference on Approximation Algorithms for Combinatorial Optimization Problems . Vol 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40
Henzinger, M. H., Sricharan, A. R., & Steiner, T. A. (2024). Private counting of distinct elements in the turnstile model and extensions. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40
Henzinger, Monika H, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” In International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40.
M. H. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct elements in the turnstile model and extensions,” in International Conference on Approximation Algorithms for Combinatorial Optimization Problems , London, United Kingdom, 2024, vol. 317.
Henzinger MH, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.
Henzinger, Monika H., et al. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” International Conference on Approximation Algorithms for Combinatorial Optimization Problems , vol. 317, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2024_LIPICs_HenzingerM.pdf
973.92 KB
Access Level
Open Access
Date Uploaded
2024-10-01
MD5 Checksum
c08b41c896e4d8c69570044808b40e0b
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2408.11637