A Joint Exponential Mechanism For Differentially Private Top-$k$

@InProceedings{pmlr-v162-gillenwater22a,
  title = 	 {A Joint Exponential Mechanism For Differentially Private Top-$k$},
  author =       {Gillenwater, Jennifer and Joseph, Matthew and Munoz, Andres and Diaz, Monica Ribero},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {7570--7582},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/gillenwater22a/gillenwater22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/gillenwater22a.html},
  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$.}
}