Timezone: »

A Joint Exponential Mechanism for Differentially Private Top-k Set
Andres Munoz · Matthew Joseph · Jennifer Gillenwater · Monica Ribero Diaz
Event URL: https://openreview.net/forum?id=BjBeRB3NqG »

We present a novel differentially private algorithm for releasing the set of k elements with the highest counts from a data domain of d elements. We define a ``joint'' instance of the exponential mechanism (EM) whose output space consists of all O(d^k) size-k subsets; yet, we are able to show how to sample from this EM in only time O(dk^3). Experiments suggest that this joint approach can yield utility improvements over the existing state of the art for small problem sizes.

Author Information

Andres Munoz (Google)
Matthew Joseph (Google)
Jennifer Gillenwater (Google Research NYC)
Monica Ribero Diaz (University of Texas at Austin)

More from the Same Authors