A Joint Exponential Mechanism for Differentially Private Top-$k$
Abstract
We present a differentially private algorithm for releasing the sequence of $k$ elements with the highest counts from a data domain of $d$ elements. The algorithm is a "joint" instance of the exponential mechanism, and its output space consists of all $O(d^k)$ length-$k$ sequences. Our main contribution is a method to sample this exponential mechanism in time $O(dk\log(k) + d\log(d))$ and space $O(dk)$. Experiments show that this approach outperforms existing pure differential privacy methods and improves upon even approximate differential privacy methods for moderate $k$.
Cite
Text
Gillenwater et al. "A Joint Exponential Mechanism for Differentially Private Top-$k$." International Conference on Machine Learning, 2022.Markdown
[Gillenwater et al. "A Joint Exponential Mechanism for Differentially Private Top-$k$." International Conference on Machine Learning, 2022.](https://mlanthology.org/icml/2022/gillenwater2022icml-joint/)BibTeX
@inproceedings{gillenwater2022icml-joint,
title = {{A Joint Exponential Mechanism for Differentially Private Top-$k$}},
author = {Gillenwater, Jennifer and Joseph, Matthew and Munoz, Andres and Diaz, Monica Ribero},
booktitle = {International Conference on Machine Learning},
year = {2022},
pages = {7570-7582},
volume = {162},
url = {https://mlanthology.org/icml/2022/gillenwater2022icml-joint/}
}