A Joint Exponential Mechanism For Differentially Private Top-k

2022/01/28 by Gillenwater, Jennifer, Joseph, Matthew, Medina, Andrés Muñoz +1 · 1 citation
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2201.12333

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(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.

Cited by

• Differentially Private In-Context Learning with Nearest Neighbor Search

Related

• Faster Differentially Private Top-k Selection: A Joint Exponential Mechanism with Pruning
• Oneshot Differentially Private Top-k Selection
• Differentially Private Top-k Selection via Canonical Lipschitz Mechanism
• Practical Differentially Private Top-k Selection with Pay-what-you-get\n Composition
• Tight Data Access Bounds for Private Top-k Selection