Sublinear Space Private Algorithms Under the Sliding Window Model

Jalaj Upadhyay
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6363-6372, 2019.

Abstract

The Differential privacy overview of Apple states, “Apple retains the collected data for a maximum of three months." Analysis of recent data is formalized by the sliding window model. This begs the question: what is the price of privacy in the sliding window model? In this paper, we study heavy hitters in the sliding window model with window size w. Previous works of Chan et al. (2012) estimates heavy hitters with an error of order θw for a constant θ>0. In this paper, we give an efficient differentially private algorithm to estimate heavy hitters in the sliding window model with ˜O(w3/4) additive error and using ˜O(√w) space.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-upadhyay19a, title = {Sublinear Space Private Algorithms Under the Sliding Window Model}, author = {Upadhyay, Jalaj}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {6363--6372}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/upadhyay19a/upadhyay19a.pdf}, url = {https://proceedings.mlr.press/v97/upadhyay19a.html}, abstract = {The Differential privacy overview of Apple states, “Apple retains the collected data for a maximum of three months." Analysis of recent data is formalized by the sliding window model. This begs the question: what is the price of privacy in the sliding window model? In this paper, we study heavy hitters in the sliding window model with window size $w$. Previous works of Chan et al. (2012) estimates heavy hitters with an error of order $\theta w$ for a constant $\theta >0$. In this paper, we give an efficient differentially private algorithm to estimate heavy hitters in the sliding window model with $\widetilde O(w^{3/4})$ additive error and using $\widetilde O(\sqrt{w})$ space.} }
Endnote
%0 Conference Paper %T Sublinear Space Private Algorithms Under the Sliding Window Model %A Jalaj Upadhyay %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-upadhyay19a %I PMLR %P 6363--6372 %U https://proceedings.mlr.press/v97/upadhyay19a.html %V 97 %X The Differential privacy overview of Apple states, “Apple retains the collected data for a maximum of three months." Analysis of recent data is formalized by the sliding window model. This begs the question: what is the price of privacy in the sliding window model? In this paper, we study heavy hitters in the sliding window model with window size $w$. Previous works of Chan et al. (2012) estimates heavy hitters with an error of order $\theta w$ for a constant $\theta >0$. In this paper, we give an efficient differentially private algorithm to estimate heavy hitters in the sliding window model with $\widetilde O(w^{3/4})$ additive error and using $\widetilde O(\sqrt{w})$ space.
APA
Upadhyay, J.. (2019). Sublinear Space Private Algorithms Under the Sliding Window Model. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:6363-6372 Available from https://proceedings.mlr.press/v97/upadhyay19a.html.

Related Material