Differentially Private Histograms Under Continual Observation: Streaming Selection into the Unknown
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
Text
Rivera Cardoso and Rogers. " Differentially Private Histograms Under Continual Observation: Streaming Selection into the Unknown ." Artificial Intelligence and Statistics, 2022.Markdown
[Rivera Cardoso and Rogers. " Differentially Private Histograms Under Continual Observation: Streaming Selection into the Unknown ." Artificial Intelligence and Statistics, 2022.](https://mlanthology.org/aistats/2022/riveracardoso2022aistats-differentially/)BibTeX
@inproceedings{riveracardoso2022aistats-differentially,
title = {{ Differentially Private Histograms Under Continual Observation: Streaming Selection into the Unknown }},
author = {Rivera Cardoso, Adrian and Rogers, Ryan},
booktitle = {Artificial Intelligence and Statistics},
year = {2022},
pages = {2397-2419},
volume = {151},
url = {https://mlanthology.org/aistats/2022/riveracardoso2022aistats-differentially/}
}