Counting Distinct Elements Under Person-Level Differential Privacy
Abstract
We study the problem of counting the number of distinct elements in a dataset subject to the constraint of differential privacy. We consider the challenging setting of person-level DP (a.k.a. user-level DP) where each person may contribute an unbounded number of items and hence the sensitivity is unbounded.Our approach is to compute a bounded-sensitivity version of this query, which reduces to solving a max-flow problem. The sensitivity bound is optimized to balance the noise we must add to privatize the answer against the error of the approximation of the bounded-sensitivity query to the true number of unique elements.
Cite
Text
Steinke and Knop. "Counting Distinct Elements Under Person-Level Differential Privacy." Neural Information Processing Systems, 2023.Markdown
[Steinke and Knop. "Counting Distinct Elements Under Person-Level Differential Privacy." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/steinke2023neurips-counting/)BibTeX
@inproceedings{steinke2023neurips-counting,
title = {{Counting Distinct Elements Under Person-Level Differential Privacy}},
author = {Steinke, Thomas and Knop, Alexander},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/steinke2023neurips-counting/}
}