A Joint Exponential Mechanism for Differentially Private Top-K Set
Abstract
We present a novel differentially private algorithm for releasing the set of k elements with the highest counts from a data domain of d elements. We define a ``joint'' instance of the exponential mechanism (EM) whose output space consists of all O(d^k) size-k subsets; yet, we are able to show how to sample from this EM in only time O(dk^3). Experiments suggest that this joint approach can yield utility improvements over the existing state of the art for small problem sizes.
Cite
Text
Medina et al. "A Joint Exponential Mechanism for Differentially Private Top-K Set." NeurIPS 2021 Workshops: PRIML, 2021.Markdown
[Medina et al. "A Joint Exponential Mechanism for Differentially Private Top-K Set." NeurIPS 2021 Workshops: PRIML, 2021.](https://mlanthology.org/neuripsw/2021/medina2021neuripsw-joint/)BibTeX
@inproceedings{medina2021neuripsw-joint,
title = {{A Joint Exponential Mechanism for Differentially Private Top-K Set}},
author = {Medina, Andres Munoz and Joseph, Matthew and Gillenwater, Jennifer and Ribero, Mónica},
booktitle = {NeurIPS 2021 Workshops: PRIML},
year = {2021},
url = {https://mlanthology.org/neuripsw/2021/medina2021neuripsw-joint/}
}