Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data
Pages 237 - 249
Abstract
Longitudinal data tracking under Local Differential Privacy (LDP) is a challenging task. Baseline solutions that repeatedly invoke a protocol designed for one-time computation lead to linear decay in the privacy or utility guarantee with respect to the number of computations. To avoid this, the recent approach of Erlingsson et al. (2020) exploits the potential sparsity of user data that changes only infrequently. Their protocol targets the fundamental problem of frequency estimation for longitudinal binary data, with l∞ error of O ((1 / ε) ⋅ (log d)3/2 ⋅ k ⋅ √ n ⋅ log (d / β)), where ε is the privacy budget, d is the number of time periods, k is the maximum number of changes of user data, and β is the failure probability. Notably, the error bound scales polylogarithmically with d, but linearly with k.
In this paper, we break through the linear dependence on k in the estimation error. Our new protocol has error O ((1 / ε) ⋅ (log d) ⋅ √ k ⋅ n ⋅ log (d / β)), matching the lower bound up to a logarithmic factor. The protocol is an online one, that outputs an estimate at each time period. The key breakthrough is a new randomizer for sequential data, FutureRand, with two key features. The first is a composition strategy that correlates the noise across the non-zero elements of the sequence. The second is a pre-computation technique which, by exploiting the symmetry of input space, enables the randomizer to output the results on the fly, without knowing future inputs. Our protocol closes the error gap between existing online and offline algorithms.
Supplementary Material
Presentatioin video for the paper Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data
- Download
- 311.21 MB
References
[1]
Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2020. Practical Locally Private Heavy Hitters. J. Mach. Learn. Res. 21 (2020), 16:1--16:42.
[2]
Mark Bun, Jelani Nelson, and Uri Stemmer. 2019. Heavy Hitters and the Structure of Local Privacy. ACM Trans. Algorithms 15, 4 (2019), 51:1--51:40.
[3]
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2011. Private and Continual Release of Statistics. ACM Trans. Inf. Syst. Secur. 14, 3 (2011), 26:1--26:24.
[4]
Luc Devroye and Gábor Lugosi. 2001. Combinatorial methods in density estimation. Springer.
[5]
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting Telemetry Data Privately. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4--9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 3571--3580.
[6]
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. 2010. Differential privacy under continual observation. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5--8 June 2010, Leonard J. Schulman (Ed.). ACM, 715--724.
[7]
Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci. 9, 3--4 (2014), 211--407.
[8]
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6--9, 2019, Timothy M. Chan (Ed.). SIAM, 2468--2479.
[9]
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3--7, 2014, Gail-Joon Ahn, Moti Yung, and Ninghui Li (Eds.). ACM, 1054--1067.
[10]
Giulia C. Fanti, Vasyl Pihur, and Úlfar Erlingsson. 2016. Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries. Proc. Priv. Enhancing Technol. 2016, 3 (2016), 41--61.
[11]
Matthew Joseph, Aaron Roth, Jonathan R. Ullman, and Bo Waggoner. 2018. Local Differential Privacy for Evolving Data. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3--8, 2018, Montréal, Canada, Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (Eds.). 2381--2390.
[12]
Jirí Matousek and Jaroslav Nesetril. 2009. Invitation to Discrete Mathematics (2. ed.). Oxford University Press.
[13]
Thông T. Nguyên, Xiaokui Xiao, Yin Yang, Siu Cheung Hui, Hyejin Shin, and Junbum Shin. 2016. Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy. CoRR abs/1606.05053 (2016). arXiv:1606.05053
[14]
Herbert Robbins. 1955. A Remark on Stirling's Formula. The American Mathematical Monthly 62, 1 (1955), 26--29.
[15]
Differential Privacy Team. 2017. Learning with Privacy at Scale. Apple Machine Learning Journal 2017, 1 (2017), 1--25.
[16]
Flemming Topsøe. 2001. Bounds for entropy and divergence for distributions over a two-element set. JIPAM. Journal of Inequalities in Pure & Applied Mathematics [electronic only] 2, 2 (2001), Paper--No.
[17]
Stanley L. Warner. 1965. Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias. J. Amer. Statist. Assoc. 60, 309 (1965), 63--69. 12261830.
[18]
Mingxun Zhou, Tianhao Wang, Hubert Chan, Giulia Fanti, and Elaine Shi. 2021. Locally Differentially Private Sparse Vector Aggregation. arXiv:2112.03449 [cs.CR]
[19]
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2020. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. arXiv:1811.12469 [cs.LG]
Index Terms
- Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data
Recommendations
Local differentially private frequency estimation based on learned sketches
AbstractSketches are widely used for frequency estimation of data with a large domain. However, sketches-based frequency estimation faces more challenges when considering privacy. Local differential privacy (LDP) is a solution to frequency ...
Bias correction for multiple covariate analysis using empirical bayesian estimation in mixed-effects models for longitudinal data
AbstractThe naïve empirical Bayes method has been widely used as an ad hoc tool in fitting linear mixed-effect models, which is much computationally efficient than the maximum likelihood estimation method. However, the shrinkage effect of the ...
Graphical AbstractDisplay Omitted
Highlights- Mixed-effects model can improve statistical power; however, EBE will give biased estimates due to shrinkage.
Model specification test in a semiparametric regression model for longitudinal data
We propose a model specification test for whether or not a postulated parametric model (null hypothesis) fits longitudinal data as well as a semiparametric model (alternative hypothesis) does. In the semiparametric model, we suppose that a baseline ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2022
462 pages
Copyright © 2022 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 ACM 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 June 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
SIGMOD/PODS '22
Sponsor:
SIGMOD/PODS '22: International Conference on Management of Data
June 12 - 17, 2022
PA, Philadelphia, USA
Acceptance Rates
Overall Acceptance Rate 642 of 2,707 submissions, 24%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 102Total Downloads
- Downloads (Last 12 months)13
- Downloads (Last 6 weeks)1
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in