Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC

Abstract

Various differentially private algorithms instantiate the exponential mechanism, and require sampling from the distribution $\exp (-f)$ for a suitable function $f$. When the domain of the distribution is high-dimensional, this sampling can be computationally challenging. Using heuristic sampling schemes such as Gibbs sampling does not necessarily lead to provable privacy. When $f$ is convex, techniques from log-concave sampling lead to polynomial-time algorithms, albeit with large polynomials. Langevin dynamics-based algorithms offer much faster alternatives under some distance measures such as statistical distance. In this work, we establish rapid convergence for these algorithms under distance measures more suitable for differential privacy. For smooth, strongly-convex $f$, we give the first results proving convergence in Rényi divergence. This gives us fast differentially private algorithms for such $f$. Our techniques and simple and generic and apply also to underdamped Langevin dynamics.

arXiv commentAppeared in NeurIPS 2020. Fixed a typo in the proof of Theorem 15

References in corpus (8)

• Rényi Divergence and Kullback-Leibler Divergence
• Renyi Differential Privacy
• General state space Markov chains and MCMC algorithms
• Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo
• Is There an Analog of Nesterov Acceleration for MCMC?
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• Benefits and Pitfalls of the Exponential Mechanism with Applications to Hilbert Spaces and Functional PCA
• Near Instance-Optimality in Differential Privacy

Cited by in corpus (1)

• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm