Skip to main content
stat
Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism
Add to Calendar 2021-09-17T14:10:00 2021-09-17T15:00:00 UTC Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism 327 Thomas Building, University Park, PA
Start DateFri, Sep 17, 2021
10:10 AM
to
End DateFri, Sep 17, 2021
11:00 AM
Presented By
Jeremy Seeman
Event Series: SMAC Talks

Implementations of the exponential mechanism in differential privacy often require sampling from intractable distributions. When approximate procedures like Markov chain Monte Carlo (MCMC) are used, the end result incurs costs to both privacy and accuracy. Existing work has examined these effects asymptotically, but implementable finite sample results are needed in practice so that users can specify privacy budgets in advance and implement samplers with exact privacy guarantees. In this paper, we use tools from ergodic theory and perfect simulation to design exact finite runtime sampling algorithms for the exponential mechanism by introducing an intermediate modified target distribution using artificial atoms. We propose an additional modification of this sampling algorithm that maintains its ε-DP guarantee and has improved runtime at the cost of some utility. We then compare these methods in scenarios where we can explicitly calculate a 𝛿 cost (as in (ε, 𝛿)-DP) incurred when using standard MCMC techniques. Much as there is a well known trade-off between privacy and utility, we demonstrate that there is also a trade-off between privacy guarantees and runtime.