Exact MCMC with differentially private moves: revisiting the penalty algorithm in a data privacy framework

We view the penalty algorithm of Ceperley and Dewing (1999), a Markov chain Monte Carlo (MCMC) algorithm for Bayesian inference, in the con- text of data privacy. Specifically, we study differential privacy of the penalty algorithm and advocate its use for data privacy. The algorithm can be made differentially private while remaining exact in the sense that its target distribution is the true posterior distribution conditioned on the private data. We also show that in a model with independent observations the algorithm has desirable convergence and privacy properties that scale with data size. Two special cases are also investigated and privacy preserving schemes are proposed for those cases: (i) Data are distributed among several data owners who are interested in the inference of a com- mon parameter while preserving their data privacy. (ii) The data likelihood belongs to an exponential family. The results of our numerical experiments on the Beta- Bernoulli and the logistic regression models agree with the theoretical results