Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown

Adrian Rivera Cardoso, Ryan Rogers
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:2397-2419, 2022.

Abstract

We generalize the continuous observation privacy setting from Dwork et al. and Chan et al. by allowing each event in a stream to be a subset of some (possibly unknown) universe of items. We design differentially private (DP) algorithms for histograms in several settings, including top-k selection, with privacy loss that scales with polylog(T), where T is the maximum length of the input stream. We present a meta-algorithm that can use existing one-shot top-k private algorithms as a subroutine to continuously release DP histograms from a stream. Further, we present more practical DP algorithms for two settings: 1) continuously releasing the top-k counts from a histogram over a known domain when an event can consist of an arbitrary number of items, and 2) continuously releasing histograms over an unknown domain when an event has a limited number of items.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-rivera-cardoso22a, title = { Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown }, author = {Rivera Cardoso, Adrian and Rogers, Ryan}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2397--2419}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/rivera-cardoso22a/rivera-cardoso22a.pdf}, url = {https://proceedings.mlr.press/v151/rivera-cardoso22a.html}, abstract = { We generalize the continuous observation privacy setting from Dwork et al. and Chan et al. by allowing each event in a stream to be a subset of some (possibly unknown) universe of items. We design differentially private (DP) algorithms for histograms in several settings, including top-k selection, with privacy loss that scales with polylog(T), where T is the maximum length of the input stream. We present a meta-algorithm that can use existing one-shot top-k private algorithms as a subroutine to continuously release DP histograms from a stream. Further, we present more practical DP algorithms for two settings: 1) continuously releasing the top-k counts from a histogram over a known domain when an event can consist of an arbitrary number of items, and 2) continuously releasing histograms over an unknown domain when an event has a limited number of items. } }
Endnote
%0 Conference Paper %T Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown %A Adrian Rivera Cardoso %A Ryan Rogers %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-rivera-cardoso22a %I PMLR %P 2397--2419 %U https://proceedings.mlr.press/v151/rivera-cardoso22a.html %V 151 %X We generalize the continuous observation privacy setting from Dwork et al. and Chan et al. by allowing each event in a stream to be a subset of some (possibly unknown) universe of items. We design differentially private (DP) algorithms for histograms in several settings, including top-k selection, with privacy loss that scales with polylog(T), where T is the maximum length of the input stream. We present a meta-algorithm that can use existing one-shot top-k private algorithms as a subroutine to continuously release DP histograms from a stream. Further, we present more practical DP algorithms for two settings: 1) continuously releasing the top-k counts from a histogram over a known domain when an event can consist of an arbitrary number of items, and 2) continuously releasing histograms over an unknown domain when an event has a limited number of items.
APA
Rivera Cardoso, A. & Rogers, R.. (2022). Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:2397-2419 Available from https://proceedings.mlr.press/v151/rivera-cardoso22a.html.

Related Material