Exact Privacy Guarantees for Sampling Algorithms Implementing the Exponential Mechanism

• Activity Number: 164 - Social Statistics Speed Session
• Type: Contributed
• Date/Time: Tuesday, August 10, 2021 : 10:00 AM to 11:50 AM
• Sponsor: Social Statistics Section
• Author(s): Jeremy Seeman* and Matthew Reimherr and Aleksandra Slavkovic
• Companies: Penn State University and Penn State University and Penn State University
• Keywords: Differential Privacy; Markov Chain Monte Carlo

Abstract

Differentially private algorithms often require sampling from intractable distributions in practice. When the true distribution of the output differs from the target distribution, this incurs penalties to both accuracy and privacy. Existing work has addressed this problem by analyzing convergence rates of distances between distributions; however, it fails to address the practitioner’s problem of designing an algorithm with fixed privacy guarantees. Our work rephrases this problem in terms of runtimes using techniques from ergodic theory and perfect simulation. We derive algorithms that can implement the exponential mechanism with exact privacy parameters under mild assumptions (for example, we do not require convexity). Furthermore, we derive conditions under which these algorithms have finite expected runtimes. We demonstrate these techniques on implementations of the exponential mechanism, quantifying the difference in runtime between pure and approximately private implementations.