[edit]
A Joint Exponential Mechanism For Differentially Private Top-k
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:7570-7582, 2022.
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(dk) length-k sequences. Our main contribution is a method to sample this exponential mechanism in time O(dklog(k)+dlog(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.