Timezone: »

 
Poster
A Joint Exponential Mechanism For Differentially Private Top-$k$
Jennifer Gillenwater · Matthew Joseph · andres munoz · Monica Ribero Diaz

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #912
in Poster Session 1 »
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$.
Keywords: SA: Privacy-preserving Statistics and Machine Learning

Author Information

Jennifer Gillenwater (Google Research NYC)
Matthew Joseph (Google)
andres munoz (Google)
Monica Ribero Diaz (University of Texas at Austin / Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors