Differential Privacy Guarantees of Markov Chain Monte Carlo Algorithms
Authors: Andrea Bertazzi
Tim Johnston
Gareth O. Roberts
Alain Oliviero Durmus
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Markov Chain Monte Carlo Methods
Girsanov's theorem
Primary area: probabilistic_methods->monte_carlo_and_sampling_methods

Abstract: This paper aims to provide differential privacy (DP) guarantees for Markov chain Monte Carlo (MCMC) algorithms. In a first part, we establish DP guarantees on samples output by MCMC algorithms as well as Monte Carlo estimators associated with these methods under assumptions on the convergence properties of the underlying Markov chain. In particular, our results highlight the critical condition of ensuring the target distribution is differentially private itself. In a second part, we specialise our analysis to the unadjusted Langevin algorithm and stochastic gradient Langevin dynamics and establish guarantees on their (Rényi) DP. To this end, we develop a novel methodology based on Girsanov's theorem combined with a perturbation trick to obtain bounds for an unbounded domain and in a non-convex setting. We establish: (i) uniform in $n$ privacy guarantees when the state of the chain after $n$ iterations is released, (ii) bounds on the privacy of the entire chain trajectory. These findings provide concrete guidelines for privacy-preserving MCMC.

Differential Privacy Guarantees of Markov Chain Monte Carlo Algorithms
Andrea Bertazzi
Tim Johnston
Gareth O. Roberts Alain Durmus'
Abstract
are required to produce approximate samples from the pos- terior, and for this reason their DP guarantees have also been the object of extensive research (Heikkilä et al., 2019; Yildırm & Ermics, 2019; Li et al., 2019; Chourasia et al., 2021; Altschuler Talwar, 2022: Zhang & Zhang, 2023).
This paper aims to provide differential privacy (DP) guarantees for Markov chain Monte Carlo (MCMC) algorithms. In first part, we establish DP guarantees on samples output by MCMC algo- rithms as well as Monte Carlo estimators associ- ated with these methods under assumptions on the convergence properties of the underlying Markov chain. In particular, our results highlight the criti- cal condition of ensuring the target distribution is differentially private itself. In second part, we specialise our analysis to the unadjusted Langevin algorithm and stochastic gradient Langevin dy- namics and establish guarantees on their (Rényi) DP. To this end, we develop a novel methodology based on Girsanov's 's theorem combined with a per- turbation trick to obtain bounds for unbounded domain and in a non-convex setting. We estab- lish: (i) uniform in n privacy guarantees when the state of the chain after n iterations is released, (ii) bounds on the privacy of the entire chain trajec- tory. These findings provide concrete guidelines MCMC.
Several works obtain DP of the one-step transitions of the MCMC algorithm by injecting extra noise in various ways, e.g. in the acceptance-rejeccion step of type algorithms (Heikkilä et al., 2019; Yıldırım & Ermics, 2019), or leveraging the additional randomness already introduced by subsampling strategies (Wang et al., 2015; Bierkens & Duncan, 2022), optionally together with clip- ping of the gradient that drives the moves of the chain (Song et al., 2013; Abadi et al., 2016). Many iterations of the MCMC chain are required to approach the posterior distri- bution, and the typical strategy to obtain guarantees on the DP of the algorithm after some number n of iterations is to use composition bounds (Abadi et al., 2016; Wang et al., 2019; Bassily et al., 2014; Ganesh et al., 2023). However, the privacy implied using composition bounds for Markov chains naturally decays with the number of steps (Kairouz et al., 2015) and as consequence the injected noise must scale with the number of iterations in order to obtain uni- form privacy bounds for the final draw. Many other works using different techniques to prove uniform-in-tine privacy bounds for the final draw from a Markov chain have bad dependence the radius of the state space or the stepsize, see (Altschuler & Talwar, 2022; Asoodeh & Diaz, 2023). These limitations were overcome in Chourasia et al. (2021), in which uniform-in time bounds on the (Rényi) DP of gra- dient descent-type algorithms was obtained, however under a strong convexity assumption.
for
1. Introduction
The framework of differential privacy (DP) (Dwork, 2006; Dwork et al., 2006) has become the standard approach for designing statistical and machine learning algorithms with quantitative guarantees on the information that their output reveals about the data. In particular, the DP guarantees of Bayesian statistical methods have already been investigated in various works, typically focusing on the DP analysis of samples drawn from the posterior distribution associated with the data and problem at hand (Wang et al., 2015; Dimi- trakakis et al., 2017: Geumlek et al., 2017: Hu et al., 2025). In practice, Markov chain Monte Carlo (MCMC) algorithms
Contributions of this work In this paper we study the differential privacy of MCMC algorithms. The paper is divided in two parts.
In the first part (Section 3) we consider general MCMC algo- rithms and establish clear connections between the DP guar- antees of the posterior distribution and of corresponding MCMC algorithm. Assuming DP of the posterior, Proposi- tions 3.2 and 3.10 show (s, 6DP for the MCMC algorithm when we either release the 7-th state of the chain or a (noisy) Monte Carlo estimator. These result show that, under suit- able assumptions, the MCMC algorithm inherits the "good"
'École polytechnique. Institut Polytechnique de Paris, France UUniversité Paris Dauphine PSL. France 'University of Warwick, UK. Correspondence to: Andrea Bertazzi <an- www.bbrrttazzeeeee polytechmique..cus
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

DP Guarantecs for MCMC Algorithms
privacy properties of the posterior. Analogously, Proposi-
as TD. is of the form
tions 3.3 and 3.4 illustrate how "bad" privacy properties of the posterior affect the privacy of an MCMC algorithm. In particular, Proposition 3.3 shows how an MCMC algorithm violates DP at a certain level (e, 6) whenever it is sufficiently close to the posterior, assuming the posterior is not (s, 8')- DP for some 8' > 6. On the other hand, Proposition 3.4 shows that if the posterior has weaker DP guarantees than the MCMC algorithm, then the law of the MCMC chain after n iterations can be far from the posterior in total vari- ation distance. These results emphasise the importance of starting with a differentially private posterior, rather than only focusing on the one-step DP of the MCMC algorithm as often suggested in the literature. This viewpoint guaran- tees that the output of the MCMC algorithm can then be both private and close to the posterior.
TD(B)= = LD(())((0)) / LD E BE)))
where (E,, B(F)) is a Borel space, (0) is the likelihood associated with D, is a prior distribution for the param- eter, and Zp- = fg (D)))n(dd). In order to make prac- tical use of the Bayesian framework, it is then essential to have access to key statisties of the posterior distribu- tion, such as its moments. MCMC algorithms aim to solve this task relying on a Markov chain, (XP))ai, which has law that converges to TD asymptotically in the num- ber of iterations n. Throughout the paper, we shall de- note the transition kernel of the Markov chain as PD E x B(E) + [0. 1]. where this means X ~ PP and also that X PB(XP: :)) where XP is the initial state of the chain. In particular, MCMC algorithms can be used to estimate expectations (f) == JE f (())TT(d)) for some statistics f E + R thanks to associated Monte Carlo averages 1
In Section 4 we prove privacy bounds for class of Markov chains in a non-convex setting, using a novel approach to establish uniform-in-time (s, 0DDP and Rényi-DP guaran- tees of the nihh state of the chain, as well as bounds for the trajectory up to the rith state. We show in Section 4.1 1.1 that it possible to prove privacy guarantees via high probability bounds on the Radon-Nikodyl derivative of different proba- bility measures on the underlying probability space. In Sec- tion 4.2 we illustrate how this strategy can be applied to the case of MCMC algorithms based on diffusions, where we rely on Girsanov's 's theorem to express the Rikon-Nikodym derivative. Using a careful perturbation technique, we are able to apply our approach to the case where only the final state after iterations is released, and not the entire path. In this case, we obtain uniform-inttime guarantees both for DP and Rényi-DP. Our strategy of proof also allows to obtain bounds for the entire trajectory of a variety of stochastic al- gorithms, improving on (c, dDP composition bounds and matching Rényi composition bounds. In particular, we show that the entire trajectory up to the n-th iteration is 8DDP, where is (n + /n log() and 8 > 0 constant, and also (a, e Rénnéénn-DD with ((m) for a > O constant. These techniques have the additional advantage of extend- ing easily to the continuous time case. We then focus our analysis on two classical MCMC algorithms based on the Langevin diffusion: the unadjusted Langevin algorithm and its stochastic gradient variant (see Section 5). In doing so, we address the open problem of obtaining uniform-in -inttm--i--ime DP guarantees in a non-convex setting.
N I==I fXP)), in the sense that Tf(f) (Robert & Casella,
lim N >n f(X)) 2004). There can be several possible outputs of an MCMC algorithm, such as X the state of the chain at time or (XP (X. Monte Carlo estimator NN Σx= f(XP). In either case, we can think of our MCMC methods as randomised algorithm A(D), that is random function of the dataset. We refer to Roberts & Rosenthal (2004) for an introduction to the main concepts required to obtain (asymptotically) valid MCMC algorithms.
)?)), the entire path up to time n, or also the
We call randomised algorithm any function D A(D), such that A(D) is random variable on a probability space (S,, P. F). We denote the law of a randomised algorithm A as PA(D). that is defined for any measurable set B as
PA(D) == P(A(D) E B).
The framework of differential privacy (Dwork, 2006) com- pares the output of randomised algorithm obtained giving two adjacent datasets as input. Various notions of adjacency between datasets can be introduced, where the most popular considers adjacent any two datasets that differ in only one entry. Below we state the definition of differential privacy. Definition 2.1. A randomised algorithm A is (E, differentially private, fore, 6 > 0, if for any measurable set B E B(E)
2. Preliminaries
(B) E PA(D)) + 8,
for any pair of adjacent datasets D, D' E S.
In Bayesian statistics, the primary object of interest is the posterior distribution of the parameter 0 E E given an ob- served dataset D S. The posterior distribution, denoted
Following Definition 2.1, we say that a posterior distribution is (c, 5)-differentially private when, for all measurable sets B, holds that
TD (B) & e TD (B) + 5,
(1)
2

---

DP Guarantecs for MCMC Algorithms
for all adjacent datasets D, D'. This is interpreted a pri- vacy guarantee of i.i.d. sample from the posterior.
chain). Consider a family of transition kernlls (Po E
B(F) [0 D E S} and family of initial distributions {VD D E S}. There exist positive, decreasing function R such that limm-+oc R(m) = > 0, and a constant Ç < oo such that for all 'D E S and all n E N
A related notion of privacy that we consider in this article is that of Rényi differential privacy (Mironov, 2017). In order to introduce the Rényi-DP we first need to define the Rényi divergence. For a > and two probability distributions, P and Q, for which their Radon Radon-Nikodyle Nikodym derivative well defined, their Rényi divergence
I TD/ & (R(n).
(3)
In particular, Assumption 3.1 requires that Ç and R are independent of the dataset. The function R is typically such that either limm- R(m) = = O. that is the when case the MCMC algorithm is asymptotically exact, or I > O, that is the case when the MCMC algorithm biased, for instance as a result of using an unadjusted discretisation scheme of continuous time process. Under this assumption, we can obtain the following relations between the DP guarantees of A, (D) and TD.
Do (PIIQ) =
- - log
1
J/2
dP> dQ
dQ
(2)
We then have the following definition.
Definition 2.2. A randomised algorithm A is sénééyi differentially private, > 0 and a > 1, if for all adjacent sets D. D' it holds that D. (PA(D)) PA(Dr)) < s.
When a + 0C we recover (e, D). Notice also that a (enej--kiidddffeeetiallll private algorithm is also (c e-1 log 8, diiffeerent private for any (0, 1) (see Proposition 3 in Mironov (2017)). Similarly to (1), we say posterior distribution is (a, s) --énni--differeeee when (I & for all adjacent datasets D, D'.
Proposition 3.2. Consider the randomised algorithm (D) ~ Vo PDPB and suppose Assumption 3.1 is verified. The following statements hold:
private
(i) I is (e, 8yddifferentially private, then A,(D) is (e, (+ ((([=)))-ifferenniid private with K = [[e= + 1).
3. From convergence to differential privacy
(i) If (D) is ( -iffferrennilll private for any n, then क is (c, 8 + (1 + (z) private.
This section establishes the connection between the DP of an MCMC algorithm and its convergence the posterior distribution.
Proof. The first statement is obtained applying Proposi- tion A.2. The second statement follows applying Propo- sition A.2 to obtain that TD is (e,5 + (1 + e²) R()))- differentially private, then taking the limit as n + cc.
3.1. Differential privacy of a Markov chain after steps
Here we are interested in the following question: what is the relation between the differential privacy of the n-th state of an MCMC algorithm, the differential privacy of the target distribution, and the total variation distance between them?
The first statement is similar to Proposition 3 in Wang et al. (2015). We note also that the second statement in Proposi- tion 3.2 still valid when the convergence bound (3) not data-uniform.
In order to address the question above, we consider the randomised algorithm AD) = XP. where (X?) kEN is a Markov chain with transition kernel PD and that is ini- tialised from probability distribution VDD The law of X is denoted Vn P-() := f (roddd))((,,, -). If || l/rv denotes the total variation distance (see Definition A.1),
A simple corollary of Proposition 3.2-(ii) is that any MCMC algorithm that is asymptotically exact, i.c. such that r = 0, will fail to be (c, d)dffferrentilll private for some num- ber of iterations n when the posterior itself is not (c, differentially private. The following proposition gives a quantitative result in this direction.
for two families of probability distributions JUD. 1'D that satisfy [|u - / & B, we have that (c, 6)- of pD implies (e. 8 + 3(e + D)) of t/D (see Proposition A.2 in Appendix A. for the proof of this result). In the case of MCMC algorithms, the law of A(D) depends on the num- ber of iterations n. and will its total variation distance to TD. Nevertheless, also in our case we can apply Propo- sition A.2 to address the question above. In this sense we make the following assumption, which requires bound on the total variation distance that is uniform over datasets and decreasing in the number of iterations.
Proposition 3.3. Suppose Assumption 3.1 verified. Let > 0, 8 E 10, and 8' (5, 1) and suppose Tp is not (c, -diffeeriretl private. Let
n" = =inf(n E N: (+++)R(()) < 8' -0.
Then, A.(D) PD B is not (e, 8) d)ffferrnnntl private for all n > n².
Proof. The result follows applying Proposition A.3, that can be found in Appendix A.2.
Assumption 3.1 (Data-uniform convergence of the Markov
3

---

DP Guarantees for MCMC Algorithms
Proposition 3.3 gives that (D) "DPB is not (e, differentially private whenever it is sufficiently close wD. assuming TD is not (s, ddifferrrrtl private for some 0.5..
the observed output. In particular, L should satisfy the following assumption, which makes the release of scalars that are close to each other differentially private.
Assumption 3.5. Let of E (0, oc). There exist (c, E R+ x [0, 1) such that, for any measurable set B and any a, b E for which Ja b) & 1/, it holds
Finally, we show that vy PB can be far from TD when PD P (e, 6n J-iiffereentiall private, while the posterior distribu- tion violates a weaker DP guarantee. In particular, we say that the posterior distribution not (e, d.dffffeeren pri- vate when there exist adjacent datasets D, D' E S and measurable set B such that (B) > (B) 6.
Pla+ < P BE
A typical choice is to draw I. from the Laplacian distribution with scale parameter n/s, which for any 1 E (0, oo) satisfies Assumption 3.5 with parameters (E, 0) (Dwork et al., 2006),
Proposition 3.4. Consider the randomised algorithm A(D) ~ PDPB and assume it is (s, (oddd))ffeeeniaallll private. Let (TD: : D E S} be a family of posterior distributions that is not (e, ddifterentyy private for some 8 > 8. Then, there exists dataset D E S such that
In order to take advantage of Assumption 3.5, we shall require that the ergodic averages for the observable / cor- responding to two Markov chains for two adjacent datasets D, D' are 17-close with high probability. Without such a property, adversary would be able distinguish between two adjacent datasets based on the observed Monte Carlo estimator. We formalise this requirement in the next assump- tion.
C
IPDB - TDIITV 1IpPb-xollyy
16
(4)
Proof. The statement follows by an application of Proposi- tion A.4 in Appendix A.3.
Assumption 3.6. Let (PB :D E S be a family of Markov kernels and {PD D E S} a family of initial distributions and let N N. There exist n < co, 8 E (0, 1) that are independent of D, D', such that for any adjacent datasets D and D'
The statement of Proposition A.4 in Appendix A.3 gives more insight than the statement above. Indeed, it shows that, for any pair of adjacent datasets D, D' for which there exists a measurable set B such that (B(B) > e TD (B) + 8, (4) holds for either 'D or D'. This means that the n-th state of the MCMC algorithm can be far from the posterior distribution for numerous datasets. In practice, a posterior distribution ı can violate (s. ()-D) even for large E and 5 unless it is carefully designed (Dimitrakakis et al., 2017). Hence, Proposition 3.4 shows that it is essential to design π carefully.
IP (|N E
Σ
f(X
E
3 - 8
for some joint processes (XP, XP' )m= ) such that (XP)== and WN are two Markov chains respec- tively with transition kernels PD and PD. and initial distri- butions VD; VDD
Note that in Assumption 3.6, we do not suppose that X and n are independent and we can consider any cou- pling between VoP and B/yy PB. Moreover, we remark that Assumption 3.6 should hold only for the observable of interest.
3.2. Differential privacy of Monte Carlo estimators
We are concerned with the task of releasing esti- mate of an expectation (f) = fg. I (zx) obtained running an MCMC algorithm for N iterations. Specifically, we are given an observable f E > R and we simulate a Markov chain X with transition kernel Pp to obtain the ergodic average 1, ΣN f(XP). Similarly to the previous section, our strategy to obtain DP guarantee will be based on assumption that requires the ergodic average to be close to the truth, i.e. (f).
In order to obtain guarantee on the DP of A, we shall assume that T. satisfies Assumption 3.5 with ry as given by Assumption 3.6. Notice that the variance of the noise in- jected in the output to achieve fixed level of DP e increases with 17. In particular, in the case of Laplacian noise we find
N
1
1 N
We consider the randomised algorithm
Var(A(DD) = -ar
+ +
N
N
n=1
A(D) = / (xx2) + L,
(5) We are now ready to state our result, that is obtained apply- ing more general argument that holds for any algorithm of the type A(D) = 9D + L, where gD is a random function that depends on D (see Proposition A.6 in Appendix A.4).
Therefore, the variance of the injected noise scales linearly with
where L is a random variable that independent of the chain X" and f is the observable of interest. Here, it is crucial to add noise to the ergodic average to prevent an adversary from distinguishing between two adjacent datasets based
4

---

DP Guarantees for MCMC Algorithms
Proposition 3.7. Let f : E R and let A be the corre- sponding randomised mechanism defined in (5). Suppose Assumption 3.6 holds for some 1 E (0, o0), 5 E [0, 1), and that L satisfies Assumption 3.5 with the same 1 and some & E RR, 5 E [0, -).. 5). Then, A is (e, 6 + - private.
focus here on Radon-Nikodym derivatives, which is essen- tially an abstraction of the well-known approach using the density function of the random mechanism, see for example in Section 3.1 of Desfontaines & Pejó (2022) or Lemma 7.1.5 of Vadhan (2017) for Lemma 4.1. This framework allows us to calculate privacy parameters via Girsanov's s theorem, which describes a change of measure on the prob- ability space.
Proof. The result follows applying Proposition A.6.
Verifying Assumption 3.6 directly would require ad-hoc arguments. Therefore we now introduce two conditions that are sufficient to ensure that Assumption 3.6 holds. We start with a high-probabilityy non-asymptotic bound on the convergence of the ergodic average to the true value, (f).).
4.1. Differential Privacy with Radon-Nikodye Derivatives
We shall start describing our approach considering an ab- stract randomised algorithm A(D) Ω - X' taking values in some (measurable) space X' and defined on a probability space (.IFF,) This shall be interpreted in the sequel as the output of an MCMC algorithm such as its n-th state or its full path up to the the n-th state. Here we stress the dependence on and denote the distribution of A(D) for any E S as
Assumption 3.8. Let f E + R. Let {PB D E S} be a family of Markov kernels and {VD D E S} family of initial distributions and let N E N. Denote by (X2)) n==
a Markov chain with transition kernel PD for any D S.
There exist d E (0, 1) and C < oo such that for any D e S
N
((D) (B) P(A(D) E B):
1 N
P
Σ 2=1
- (f) <C
2 1-8.
for any measurable set B C X. Our strategy to obtain DP of the mechanism A is based on a change of measure argument. In particular, for every pair of adjacent datasets D, D' S we shall find probability measure Q (9, such that the law of A(D) under Q is equal to the law of A(D') under P. This is to say,
This assumption can be typically verified using some mixing properties of the family of Markov kernels {PB D E S), that should be uniform over D S as stated in Assump- tion 3:1; see e.g. Paulin (2015); Durmus et al. (2023) and the reference therein.
P PX(D) A(D")
(6)
Then, we require that the absolute value of the difference between (f) and TD (f) is bounded by a constant for any adjacent datasets D, D'. This ensures that the output A localises around similar values and thus can be private.
Note that Q depends on D,D', but to avoid overloading the notation, we keep this dependence implicit. When and Q are mutually absolutely continuous, we can define the Radon-Nikodym (RN) derivative d2 Ω + R, together oF
Assumption 3.9. There exists 7f < oc such that
with inverse aq- That to say, for every random variable Z Ω + X one has
dF'
(TD(f) TD. (f)l < 7f.
dQ Z dIp
for any adjacent datasets D,D' E S.
Eg 2
E
We now state our main result of the section.
where Eg denotes integration on Q with respect to Q, while E denotes integration with respect to I.. Since do is a mapping from the probability space, we can treat it random variable taking values in IR.
Proposition 3.10. Suppose Assumptions 3.8 and 3.9 hold for some C, 5, Ti. Suppose also that T. satisfies Assump- tion 3.5 for 17 = 2C + 7f- Then the randomised mechanism A defined in (5) is (e, 8 + 28- d')-differentially private.
AP
Now that we have set the framework, we can show how to obtain DP of A bounding the Radon-Nikodym derivative with high probability.
Proof. The proof based on showing that Assumption 3.6 holds under our assumptions. The details can be found in Appendix A.5.
Lemma 4.1. Let A be a random mechanism and suppose for every two adjacent datasets there exists a measure Q such that (6) holds. Suppose furthermore for every such Q
4. Characterising the Privacy of Diffusions
the Radon-Nikodym derivative,
dp is well defined, and also dg
that
In this section we describe our proof strategy to obtain DP guarantees of MCMC algorithms based on diffusions. We
dP
P
e
$ 5.
dQ
5

---

DP Guarantees for MCMC Algorithms
Then, is (e, didiffrreet private.
e.g. applying the Euler scheme continuous time SDE. For instance, the choice x(t) == >|4/7] corresponds to the backwards projection onto the grid (NYYDEN. In this
Proof. The proof follows by splitting the expectation of the dP
relevant indicator function into regions where ac large and small. Full details can be found in Appendix B.I. U
case one has that X is equal in law to the Markov chain (x JNEN
# = In + +fD((E : + 22 Zn+1
In the next section, we will rely on Lemma 4.1 to obtain DP guarantees for diffusion-baset MCMC algorithms, where the Radon-Nikodym derivative can be obtained by Gir- sanov's theorem. The following lemma is essentially corollary of the data processing inequality, see Theorem 9 in van Erven & Harremos (2014).
and (zn n231 1 is sequence of independent standard normal random variables. The process (7t)c2 allows us to consider additional sources of randomness, for instance the random mini-batcher that give the stochastic gradient in the noisy SGD algorithm.
Lemma 4.2. Let A be random mechanism and consider two constants a > 1, >> O. Suppose for every D, D' E there exists a measure Q such that (6) holds. Suppose in addition that the Mudon-Nikodyn derivative is well aq
Remark 4.4. We assume without further commentary that (7) has a unique strong solution. This holds when k is a projection onto a grid, and also when r<()) t under weak conditions (Zhang. 2005).
defined and
In the following result, we demonstrate that our proof strat- egy can be used to give privacy bounds for (D) that are uniform in T > We remark that the condition (9) can be satisfied in non-convex settings, which to the best of our knowledge have not been addressed thus far in the literature.
E
E cla-1)e
d
Then, A is (a, E--ény differentially private.
Proposition 4.5 (Privacy of the final value). Let T > 0 and assume there exist constants L, C, O such that for every adjacent datasets D, P.'' E S one has for any x, y E Rd and E y
Proof. The proof can be found in Appendix B.2.
Remark 4.3, For all results in this paper, bounds in (s, 8)- DP can be achieved by converting Rényi-DP bound, as mentioned in Section 2. However, we presented Lemmas 4.1 and 4.2 separately since Lemma 4.2 applies more generally, and in particular does not require control of the tails of dP /dQ.
s) - JD (v, & L/x - yl cc
(8)
and (XP )efoory and (XP") )(Ej0,1 are solutions of (7) with drifts fo and for respectively, driven by the same Brownian motion (W,), 2 O, such that almost surely! it holds that
4.2. Differential privacy of stochastic differential equations
IXP -P-XXP -P-PPPCC. =E[0,T]
sup
(9)
In this section we shall consider the DP of random mecha- nisms A that involve the solution of a stochastic differen- tial equation (SDE). We are particularly interested in two distinct random mechanisms generated by (7): the single time evaluation AD) = X taking values in Rd and also the whole path (D) (XP) )reo,,T] taking values in C(OO, TJ. RR,,, that is the space of continuous functions on [0, T] taking values in Rd
Then for 8 > 0, > 1 one has that A. XP (Es, 6)-piivate and (a, private for
Es = C2/4 + / log(1/5), Ea = =C2/4
where C₂ = (C + +))
Proof. We fix a pair of adjacent datasets D, D' E S and
The general SDE we study is
T > 0, and define an auxiliary process (Z)) satisfying
dxp- = (x(X k(t)s )dl + d2/
Z, = XP for E [0,T- -1,,
2T 2==
with initial condition XP- 2o E d.d Here W. is Brown- ian motion, fD+ Rd x y + Rd is measurable function,
In particular, Ze is given by perturbing the dynamics of X on 1. E -T- 1, [] in such way that it approaches xp. By the assumption that xP and x.'' are almost
[0, 0o) + [0, x)) is a function satisfying x(() & I, (nd)00 is a stochastic process independent of (Wo)zo tak- ing values in some space V, and 3 > 0 is an inverse tem- perature parameter that scales the noise. The function x allows us to consider discrete time approximations obtained
Since the measures P and C are absolutely continuous, here and elsewhere don't 't distinguish for which measure the event in question almost sure.
6

---

DP Guarantees for MCMC Algorithms
surely close, one may define this perturbation in such way that it is almost surely bounded. Therefore via Girsanov's theorem we can find measure Q satisfying the assump- tions of Lemmas 4.1 and 4.2. Full details are presented in Appendix B.6.
range of assumptions (Neal, 1992; Roberts & Tweedie, 1996; Durmus & Moulines, 2019). We shall consider the pri- vacy of both the final draw = E IR and of the entire chain E R under a non-convex assumption on Up. The particular assumption we place upon the posterior in the following theorem is close to the convexity outside a ball condition considered in Durmus & Moulines (2017) and Erdogdu et al. (2022). The strongly convex part K could be interpreted as regulariser.
Furthermore, we have the following result on the privacy of the entire trajectory of X2 up to a time T > O.
Proposition 4.6 (Privacy of the path). Consider the family of processes (7). Suppose there exists >> O such that for every adjacent datasets D,D's E and x E IR", .7 E y one has
Assumption 5.1. Consider a posterior distribution (11) and suppose for every dataset D E S one may write Up- = V + K, where VD. K : R + R are continuously differentiable functions. In addition suppose that there exists a constant c > such that supze3" (V)= <
(10) Then for > 0,a 7 1 one has that the algorithm (D) = (rF)) is (Es, -iiffrrliite private and (a. differentially private for
(fr(z, - (x, E.
c. Furthermore, V K
is L-Lisschitz, that
(K VK(y)) < L/z alx-y// yl.
for all 2, y Rd, and also strongly convex, that is there exists a >> 0 such that for all x. y E Rd.
<s - C (o(()) Ea aCC((T44 and -
(VK()) - VK(v), x-
- y) 2 allE - yll.. (13)
Fixing adjacent datasets D' E S, we use Gir- sanov's theorem to define measure Q under which ] is equal in distribution to (xP)tejo;r under P.. Using bounds on the assumed discrepancy between the drifts (10), we may control the Radon-Nikodye Nikodym derivative dP/ dQ in such a way as to obtain the result applying Lemmas 4.1 and 4.2. Full details are presented in Appendix B.5,
Proof.
Theorem 5.2. Suppose Assumption 5.1 holds and let A,(D) x be the 1-th state of the ULA targeting TD with step-size E (0. 20/1.)) Then, for 8 >> 0) and a " 1, A,(D) is (Es, (.55))ddifferenialll private and (at, sa) Rényi differentially private for
(XP")te(o;))]
E8 = C3 + v Ca log(1/0), En = a03/4 2(++1) where C3 (, a- + +12
5. Privacy of Langevin-based algorithms in the non-convex setting
Proof. The proof here uses Proposition 4.5. One considers continuous time interpolation of the ULA algorithm (12), at which point it just suffices to show that the closeness condition (9) holds for the continuous time interpolation. Full details are given in Appendix C.I.
In this section we obtain (Rényi)-DP for both the trajectory and the final value of two Langevin- based MCMC algo- rithms: ULA and noisy SGD. All bounds in this section are derived from Propositions 4.5 and 4.6.
Note that the above bound does not depend on the number of steps. Furthermore, since recent analysis like (Chewi et al., 2022) suggests that ULA recovers the true posterior in Rényi divergence 7 - 0 and n. - xo, taking the limit as 7 0 in Theorem 5.2 suggests that true posterior is differentially private with C3 > 0 replaced with C4= c( 2(L+1) + 1).
5.1. Sampling from Bayesian posteriors with ULA
Consider a posterior distribution with density with respect to the Lebesgue measure on dd of the form
TD (x) e (u)
(11)
a
for Un: Rdd - R.. We can approximately sample from ap with ULA, that is the Markov chain
Now consider the privacy of the entire chain under slightly different assumptions.
Assumption 5.3. There exists constant c > 0 such that the posterior πD in (11) satisfies for any adjacent datasets D. D' E S and all x E Rd
2 2 1 (VD(==?) + /2y2a411 (12)
with initial condition xpP = E Rdd and where (zn) n2 is a sequence of i.i.d. standard Gaussians on Rd. and 7 >0 0 is the step size. ULA arises as the Euler discretisation of the overdamped Langevin diffusion and has been shown to be successful for sampling from Bayesian posteriors under
(VD(z) (UD( <c.
Note that the following result places no requirement on the step size, but does depend on the number of steps.
7

---

DP Guarantees for MCMC Algorithms
Theorem 5.4. Suppose Assumption 5.3 holds and let Ap(D) (op...... R) be the path of ULA up state E N. Then, for 8 > 0, a 2 L, the algorithm Ap is (Ea, 81-diferrentialy private and (a, (aa)-Rééé differentially privatefor for
Theorem 5.6. Suppose Assumption 5.5 holds and consider
the algorithm A,(D) = =h described in (15) with y (0, 2a/ L22) and stochastic gradient of size S m. Then, for 8 > 0 and a > 1, one has that Ag is (E6, 6) o)-differentialy private and (ar, -Rééné differentially private for
= = Cs(n//44 log(1/)) ea = aCs(n)/4, where Ct(n) = nye2.
Es = C6/4 + VC log(1/)),
Ea = aC6/4,
2(+11 where Cg c² 2 11 + 1)²
Proof. We use the continuous time interpolation of (12), along with Proposition 4.6. Then since (x.,..., J ) is equal in law to mapping from (XF )ee the result follows from the data processing inequality (see Theorem in van Erven & Harremos (2014)).
Proof. The proof here is similar to the proof of Theorem 5.2, with minor alterations due to the stochastic gradient and the inverse temperature parameter B >> 0. Full details are given in Appendix C.2.
Theorem 5.6 is only a minor refinement of Theorem 5.2, and in particular the privacy guarantee does not improve with the size m of the dataset. However, in the strongly convex case where each Ve is constant, the following theorem (similar to Theorem 2 in Chourasia et al. (2021)) shows that privacy does increase with & m.
5.2. Noisy stochastic gradient descent
In this section we study the DP of stochastic-gradient variant of the ULA. This algorithm is essentially noisy version of the stochastic gradient descent and can be used to minimise the loss function
m Σ (D( == m
Theorem 5.7. Consider the setting of Theorem 5.6, but suppose that for any datum d E 'D with 'D E S one has that V v,,(I, d) is constant in x E Rd. Then, for ō > 0 and
E d.),
(14)
a > 1, one has that Ag is (Ex, 8) difffrrrentl private and (a, (...aa))enn -Rényi differentially private
where we assumed the dataset is of the form D idi....,dmi The algorithm consider is driven by the following Markov chain:
EB = C7 + (olo0/1/6),
Ea = aC7/4
2 = x 2-2 E dd + 227/B2n+1, (15)
where C7
28
2(++1) / a 71.772 + +1
1EA
where E: Rdd y + R. (An)næ1 a sequence of inde- pendent random variables uniformly distributed on subsets of (1,...,m) m] of size & m, the step size is y > 0, and (In)n>1 is sequence of i..dd standard Gaussians on Rd, independent of (An)a31- Here f(x, d,) is interpreted as the loss incurred for datum d,. We remark that the algorithm (15) is known in the MCMC literature as stochastic gradient Langevin dynamics (Welling& & Teh, 2011).
Proof. The proof can be found in Appendix C.3.
It is an open problem as to how m and affect the privacy of the noisy SGD algorithm in the setting of Theorem 5.6. However, the following result on the path of noisy SGD improves with the size s & m of the stochastic gradient.
Theorem 5.8. Consider the loss function (14), and suppose there exists c >> such that for every D, e S and e D,d' d' D' one has that
In order to prove DP of the algorithm, we shall work under the following assumption the loss function.
V d) - Vel(x,d')
Assumption 5.5. Consider the loss function (14), where
Then, for > 0 and > 1, the algorithm A² = (xp,..., x2 shown in (15) is (Es, d)difffernttilly private and (a, Ea) RRényi differentially private for
((z, d) v(z, d) + k(x),
for functions Rd X R and k Rd - R that are once continuously differentiable. Furthermore, Vk is I.- Lipschitz and for a > 0 one has V d)l < for any x E Id and any datum d, as well as
E8 = Cs + V log(1/0)) ea = oCs/4
where Cs(n)
86 32 12y
(Vk(z) - Vk(y), x >>> y11
Proof. The proof is very similar to the proof of Theorem 5.4. Full details are given in Appendix C.4.
We then have the following result.
8

---

DP Guarantees for MCMC Algorithms
The results of Ryffel al. (2022) and Ye & Shokri (2022) suggest that one may obtain superior bounds by fully ploiting the randomness of the stochastic gradient. However, for simplicity we do not consider this in the current work.
Acknowledgements
All authors acknowledge funding by the European Union (ERC-2022-SyG, 101071601). Views and opinions ex- pressed are however those of the authors only and do not nec- essarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Gareth O. Roberts has been supported by the UKRI grant EP/Y014650/1 as part of the ERC Synergy project OCEAN, EPSRC grants Bayes for Health (R018561), CoSInES (R034710), PINCODE (EP/X02811//I), ProbAI (EP/Y028783/1) and EP/V009478/1.
5.3. Commentary on Bounds Presented
We have studied two kinds of dimension-indeeendeee pri- vacy guarantees: for the final draw, and for the entire tra- jectory of an MCMC chain. In particular, our bounds for the privacy of the final draw in Theorems 5.2 and 5.6 are uniform-in-tinme in a non-convex setting on an unbounded space, which addresses Question 1.2 and provides an up- per bound for Question 1.1 in Altschuler & Talwar (2022). Also, unlike the results of Altschuler & Talwar (2022), our bounds do not depend on the size of the state space (which is unbounded), and do not blow up as the step-size goes to O. In this sense, we therefore generalise the results of Chourasia et al. (2021) to a non-convex setting. Indeed, our results match Chourasia et al. (2021) in the strongly convex regime.
We thank Mengchu Li and Shenggang Hu for the useful discussions.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. We believe by extending the theoreti- cal study of differential privacy, practitioners will be able to design methods that better protect the privacy of individuals.
On the other hand, our results for the entire trajectory we improved on known composition bounds for (c, ()..)-pric pprivacy, matching composition bounds for Rényi privacy. This re- moves the need for complicated (c, 5-DD privacy account- ing, and provides a simple framework which extends natu- rally to the continuous time case. In particular, our 8)- DP bounds in Theorems 5.2 and 5.6 feature uniform val- ues of 5 0, and O(n + / / log(/ dependence on the number of steps n, whilst the advanced compo- sition bounds presented in Kairouz et al. (2015) achieve E = O(n + Volee + (Evn/8))).
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS 16, pp. 308-318, New York, NY, USA, 2016. Association for Computing Machinery.
A Altschuler, J. and Talwar, K. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022.
6. Conclusions
We have presented variety of results on the differential privacy of MCMC algorithms. Our results clarify the im- portance of choosing a Bayesian posterior distribution that has good DP guarantees, or else an MCMC algorithm can- not be expected to both private and close to convergence. Our results imply that it is crucial to design the MCMC algorithm together with the Bayesian model, in order to allow an end-to-end private inference. We have also dis- cussed novel approach to prove DP based on bounding the Sadon-Nikodym derivative of the algorithm. This strategy allowed us to obtain new non-convex results that extend the known privacy properties of Langevin-basee MCMC algorithm. We expect that a more careful analysis could allow extensions of our results to more general assumptions on the posterior distribution. Our approach can be applied to very general randomised algorithms and not only those considered in this article. We leave extensions to more com- plex settings such as Bayesian federated learning for future work.
Asoodch, S. and Diaz, M. Privacy loss of noisy stochastic gradient descent might converge even for non-convex losses, 2023.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS *14, pp. 464-473, USA, 2014. IEEE Computer Society.
Bierkens, J. and Duncan, A. Federated bayesian computa- tion via piecewise deterministic markov processes. arXiv preprint arXiv:22 13116, 2022.
Chewi, S., Erdogdu, M. A., Li, M., Shen, R., and Zhang, S. Analysis of langevin monte carlo from poincare to log-sobolev. In Loh, P.-L. and Raginsky, M. (eds.), Pro- ceedings Thirty Fifth Conference on Learning Theory,

---

DP Guarantees for MCMC Algorithms
volume 178 of Proceedings of Machine Learning Re- search, pp. 1-2. PMLR, 02-05 Jul 2022.
Heikkilä, M., Jälkö, J., Dikmen, O., and Honkela, A. Differ- entially private markov chain monte carlo. Advances in Neural Information Processing Systems, 32, 2019.
Chourasia, R., Ye, J., and Shokri, R. Differential privacy dy- namies of langevin diffusion and noisy gradient descent. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021.
Hu, S., Aslett, L., Dai, H., Pollock, M., and Roberts, G. O. Privacy guarantees posterior sampling under contami- nation. arXhv:2403.07772, 2025.
Kairouz. P., Oh, S., and Viswanath, P. The composition theorem for differential privacy. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37, pp. 1376-1385. PMLR, 2015.
Desfontaines, D. and Pejó, B. Sok: Differential privacies, 2022.
Dimitrakakis, C., Nelson, B., Zhang, Z., Mitrokotsa, A., and Rubinstein, B. I. P. Differential privacy for bayesian inference through posterior sampling. Journal of Machine Learning Research, 18(11):1-33 2017.
Karatzas, I. and Shreve, S. Brownian Motion and Stochastic Calculus, Graduate Texts in Mathematics (113) (Book 113). Springer New York, 1991.
Durmus, A. and Moulines, E. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. The An- nals of Applied Probability, 27(3):1551-133) 1587, 2017.
Li, B., Chen, C., Liu, H., and Carin, L. On connecting stochastic gradient meme and differential privacy. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 557-566. PMLR, 2019.
Durmus, A. and Moulines, E. High-dimensional bayesian in- ference via the unadjusted langevin algorithm. Bernoulli, 25:2854-2883 2882, 11 2019.
Minami, K., Arai, H., Sato, I., and Nakagawa, H. Differen- tial privacy without sensitivity. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, 2016.
Durmus, A., Moulines, E., Naumov, A., Samsonov, S., and Sheshukova, M. Rosenthal-type inequalities for linear statistics of markov chains. arXiv preprint arXiv:2303.05888, 2023.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEEE, August 2017.
Dwork, C. Differential privacy. In International colloquium automata, languages, and programming, pp. 1-12. Springer, 2006.
Neal, R. Bayesian learning via stochastic dynamics. In Hanson, S., Cowan, J., and Giles, C. (eds.), Advances in Neural Information Processing Systems, volume 5. Jorgan-Kaufmann 1992.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Halevi, S. and Rabin, T. (eds.), Theory of Cryptography, pp. 265- Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
Paulin, D. Concentration inequalities for markov chains by
Erdogdu, M. A., Hosseinzadeh, R., and Zhang, S. Conver- gence of langevin monte carlo in chi- squared and rényi divergence. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, vol- ume 151 of Proceedings of Machine Learning Research, pp. 8151-8175. PMLR, 2022.
marton couplings and spectral methods. 2015.
Robert, C. P. and Casella, G. Monte Carlo Statistical Meth- ods. Springer. 2004.
Roberts, G. O. and Rosenthal, S. General state space Markov chains and MCMC algorithms. Probab. Surveys. 1:20-71, 71, 2004.
Ganesh, A., Thakurta, A., and Upadhyay, J. Universality of langevin diffusion for private optimization, with ap- plications to sampling from rashomon sets. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Con- ference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 1730-1773. PMLR, 12-15 Jul 2023.
Roberts, G. O. and Tweedie, R. L. Exponential convergence of langevin distributions and their discrete approxima- tions. Bernoulli, 2(4):341-363 1996.
Ryffel, T. Bach, F, and Pointcheval, D. Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics. working paper or preprint, January 2022.
Geumlek, J., Song, S., and Chaudhuri, K. Renyi differential privacy mechanisms for posterior sampling. Advances in Neural Information Processing Systems, 30, 2017.
Song, S., Chaudhuri, K., and Sarwate, A. Stochastic gradi- ent descent with differentially private updates. In 2013
10

---

DP Guarantecs for MCMC Algorithms
IEEE Global Conference on Signal and Information Pro- cessing, GlobalSIP 2013 Proceedings, pp. 245-248, 2013.
Vadhan, S. The Complexity of Differential Privacy, Pp- 347-450. Springer, Yehuda Lindell, ed., 2017.
van Erven, T. and Harremos, P. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Infor- mation Theory, 60(7):3797-3820, 2014.
Wang, D., Chen, C., and Xu, J. Differentially private em- pirical risk minimization with non-convex loss functions. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 6526-6535 PMLR, 09-15 Jun 2019.
Wang, Y.-X., Fienberg, S., and Smola, A. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pp. 2493-2502, PMLR, 2015.
Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11),
pp. 681-688. Citeseer, 2011.
Ye, and Shokri, R. Differentially private learning needs hidden state (or much faster convergence). Proceedings of the 36th International Conference on Neural Informa- tion Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc.
Yildrım, S. and Ermics, B. Exact meme with differentially private moves: revisiting the penalty algorithm in a data privacy framework. Statistics and Computing, 29:947- 963, 2019.
Zhang, W. and Zhang, R. fa-fast mh: Private, fast, and ac- curate metropolis-hastingg for large-scale bayesian infer- ence. In International Conference on Machine Learning, pp. 41847-41860. PMLR, 2023.
Zhang, X. Strong solutions of sdes with singular drift and sobolev diffusion coefficients. Stochastic Processes and their Applications, 115(11):805-11888 2005.

---

DP Guarantees for MCMC Algorithms
A. Proofs and general results for Section 3
In this section we give proof's and general statements relative to Section These rely on the following definition.
Definition A.1. Let μ and be two probability distributions (E, (E)). Their total variation (TV) distance is
|| v/IV = sup Iμ(B) v/B)/. BEB(E)
A.1. Auxiliary result for Proposition 3.2
The following result analogous to Proposition 12 Minami al. (2016).
Proposition A.2. Let {uD D 8} and {VD D S} be two families of probability distributions that satisfy
I|D - VDl & for any D E S. If (ND D E S} is (e, differreetlll private, then {VD " E is (c, 8 B(e +1)- differentially private.
Proof. Let D'D' E S denote two adjacent datasets and B be measurable set. First, we observe that under our assumption and by the definition of the total variation distance we have (px(B) - Vp (B)l < B. This implies following inequalities for any
(B) (B) + 3, (B (D 3.
(16)
(17)
Using these inequalities well as the (s, 0)-DP μ. we find that
(B) (B + < < (B) +
3B) +
which concludes the proof.
A.2. General result for Proposition 3.3
Proposition A.3. Let {uD D 8} and (VD :D S} be two families of probability distributions that satisfy [|n VDllTY & 3 for any D E S. Let > 0, ā E ((+ and suppose (vD 'D E S} is not (c, diifffrrrrel private. Then, {ND D E S} is not (e, 5 - (1 + e² ) diifeifferet private.
Proof. Let D, D' E S denote two adjacent datasets and B be a measurable set such that
PD' (B) > (B) + 6,
i.e. such that the definition of DP for the family {up D S} is violated. Now, applying the inequality (17) followed by the inequality above we find
2 uD) - 3. PD (D) > (B)
Then, we apply inequality (16) to find
I' (B) > (B) + (1 c5)3,
which proves the result.
12

---

DP Guarantecs for MCMC Algorithms
A.3. General result for Proposition 3.4
Proposition A.4. Let {uD S} and {UD E }} be two families of probability distributions. Assume {VD D S} is -...J..fferenttiall private and {PD D S) is not (E for 6,. > dv, i.e. there exists at least pair of adjacent datasets D, D' 8 and measurable set such that
PD (B): é (D 6,.
(18)
Define the set of pairs of adjacent datasets for which (18) holds:
S = ([D,D') E x D' are adjacent and there exists B such that (18) holds).
Then, for any (D, E S there exists D E (D, D') such that
lub - MollTV T (6p 8y).
Proof. We take any pair of datasets (D, DJ) 3. Notice that (18) implies that
(B) < e "== (BD(B) - e =
Moreover, (EP means that
VD( > e (D) - e 55
Using both inequalities we find
(B((B) VD(B) < = - e =,) + - por (B) - v (B) < -e (6, 8y) + " (B) 1/D' (B))
Suppose that ||ND VDr VDrl|TY || ( for some constant 0 < & 6, 8v. This implies that (iD: (D) & G.
Therefore, find
(D (B) (D( < = 5, 5)
Since 5, - 8, - - by construction, taking the absolute value we find
(BD(B) PD > (8, 8, - ()
By the definition of TV distance
IpD - "D||TV > (B) vD(()) > e E6 16,,66000
- 8, -))
Clearly, when I| - -pp rv & Ç does not hold, it must be that || Vp ll > 5. This shows that there exists a dataset
D E (D, such that either [|ug VollTV > (or I|m - " || e e (6p - 8 - -). Therefore it always holds that
||4 Vig lr > min (6, - 8, - -{)
Optimising the bound for Ç [0, 8, - 8z), we find that the lower bound above is maximised for Ç* - (5, 8z), which satisfies the equation 5* = c (6, 5, - S*).
A.4. General result for Proposition 3.7
Consider the randomised algorithm
A(D) gp +L,
(19)
where gp is random variable that depends on the dataset, and satisfies Assumption 3.5 and independent gp. We make the following assumptions, which the general version of Assumption 3.6.
13

---

DP Guarantecs for MCMC Algorithms
Assumption A.5. Let D, D' S denote adjacent datasets. that
There exist 1j > 0, < 1 that are independent of D, D' such
P ((gp
gD' & n)) 1
Assumption 3.5 and Assumption A.5 are enough to obtain the following guarantee on the differential privacy of the randomised algorithm (19).
Proposition A.6. Let be the randomised mechanism defined (19), where L independent of gD for any E S. Suppose Assumption A.5 holds, well Assumption 3.5 for n as in Assumption A.5. Then A is (e, 6 + diifferreetl private.
Proof. Let B be any measurable set. We find
(AA)) e B) P (A(D) E B, 190 gD < <n) (P((AD) E B, 1, gD > 11)
(20)
The first term on the right hand side of (20) can be bounded using Assumption 3.5. Indeed, Assumption 3.5 can be used since we are on the event gD
9D' & 1) and because L and gD, 9D' are independent. Following this reasoning, we find
P (gD + B, gD gD < m)
P (gD L BB gD < 1) -
((A(D') E B) 8.
In the last inequality we simply discarded the event {l9> gr < m). Applying Assumption A.5 we can bound the second term in (20) as follows:
((A(D) E B, 1g - DD > 1)) < P (gg - god > n) < 8.
We have obtained the result.
A.5. Proof of Proposition 3.10
Let D, D' E S be two adjacent datasets. We introduce joint process (XP: XP ) such that (XP) and (X >==1 independent Markov chains respectively with transition kernels Po and Po. and initial distributions vD vpr. We now define two sets, B₁ and B2, that represent respectively Assumption 3.8 and Assumption 3.6:
N
B =
Σ n=1
f(x
= < Cs for = DDD'
N
and
N
1 N
< 2CC + 71 70) }
B₂ =
Σ
(XP))
1 E ((XP)) n=1
N
n=1
Now notice that B, C B2 under assumptions, and hence P(B2) > P(B)). Indeed, an application of Assumption 3.9 gives
1 N
N f(x -D(( + +|x=(f)- -TD +
f(X2)
f(XP)
Σ
f(xP') -TD((f)
N
N n=1
N n=1
==1
20 8 + +
Then, notice that, since the two chains are independent, we find
PBB = ( Σ ((x)) - To(S) & CG.N
E(x") - mD(l) < <CaNN)
P
N
Hence, by Assumption 3.8
P(B,) > (1 = -1 125 82).
Therefore, we have obtained P(22) > (28 82)
The result then follows by Proposition A.6.
14

---

DP Guarantecs for MCMC Algorithms
B. Proofs and auxiliary results for Section 4
B.1. Proof Lemma 4.1
Consider measurable set C. X and denote = A(D), A(D)). derivative is larger than a constant as
Let us introduce the set where the Radon- Madon-Nikodym
{ w
dP
Ke
(
e
dQ
Then we can decompose P(X E B) as
P(X B) = Eexx k.] k.I B[Dxxe
Hence, since by assumption we can control the Radon-Nikodym derivative with high probability, in the sense that (Kę) 6, find that
B[1xeB < 6.
On the other hand, we have
dPP dQ
B[Ixeelks Eo
1xeBlke
< < [1xe]]= TTT(P B),
as required.
B.2. Proof of Lemma 4.2
By the data processing inequality (Theorem 9, (van Erven & Harremos, 2014)) one has
D. (P(P ((D) || P A(D))) = Da A(D)
1 A(D)) < (PIIQ..
The result then follows by the definition of Rényi DP in (2) since
dP d
dP
EQ
E
B.3. Girsanov's theorem SDEs
Here we apply Girsanov's theorem to obtain the Radon-Nikodym derivative of the law of two SDEs with different drifts. The precise formulation we choose here is chosen so as be able to apply the result the diffusion (7) featured in Section 4.2.
We shall assume Novikov's condition (21).
Lemma B.1. Consider two processes X for i 1.2 on a filtered probability space
PP) that solve the SDEs
dx: = =(x k(E)> (n(e)) dt + 22/3dWe.
ax² = g(X2 nale) dt + udt + 22/3dW,
where X3. X3- = wo E Rd. (Wz) is standard Brownian motion, R& Rd is a function, (0) 10, oo) satisfies k(t) & t, (m))so is stochastic process independent of (Wi) and is Fe-adapted process. Let the SDE given for each = 1,2 have a unique strong solution, and suppose for > 0 that
/
111
1
exp
|uel dt) <c.
(21)
Then there exists a measure Q such that the random variable (X))1e(o.r) on the probability space (2,F (Fi) Q) equal in law to (X?) (X))eE(O.T) on the probability space (2, (Fi)izo, P), and furthermore
d
(V2, cxp(
( /33 [' (u,, aW.) 8 1//0 1d
exp
(22)
dI
15

---

DP Guarantecs for MCMC Algorithms
Proof. For l let define the new process
We = V % u.ds + We
We may now use Girsanov's theorem find a measure Q such that (ee)ee is Brownian motion under Q Particularly, under (21) one has by Corollary 5.13, Section 3.5 of Karatzas & Shreve (1991) that
exp (V2 2 (u., dW,) 4
B
uu lss
2
a -arttnaaat under P, so by Girsanov's theorem, i.e. Theorem 5.1, Section 3.5 of Karatzas & Shreve (1991), one has that (W, xeeoor) is Brownian motion under Q given by (22). Then since may write
ax; g( x(e) (l(()) )d + + 2/3dW,, X. = E IR
and since both SDEs have unique strong solution one sees that (et))) defined on the probability space F, (Fe)ezo, Q) must be equal in law (e))) defined on (9,, (Fo).
B.4. Bounds Stochastic Integrals
In this section present well-known bounds for exponentials of stochastic integrals.
Lemma B.2. Let un be (Fi))aoommasuurable process such that for some T, K >> one has suPrEjo,T] & K. Then
E exp (unnd & TK
Proof. Since we have that [uel < K almost surely, one sees that for every 2>
2 J. M, 2ds
E exp
co.
Therefore by Corollary 5.13, Section 3.5 of Karatzas & Shreve (1991) one has that
exp (U
(J
(w..dd..)
dW.) 2 % uno [uoldds)
a martingale. Then using the assumed bound [ua| < again one has
E exp (L. (W.) T
< E exp S1, (M.. dW,)
2 /
1 //''
luoldd
=1
at which point the result follows.
Lemma B.3. For un as in Lemma B.2, one has for any a >
P ([ (u,, aW,) > a
a²
< exp
2T
Proof. Let v > 0 and a E R. By Markov's inequality
IP ((. (u., dW.) > >a) P exp 1 l/ (us, dw:)) > )(T) < aayg
/ (us aw:))
exp
so that applying Lemma B.2 one has
PP pf (us dW.)
(W,, > 0) < - <e-auttikkp 1312
The result follows by minimising v.
16

---

DP Guarantecs for MCMC Algorithms
B.5. Proof of Proposition 4.6
Let us fix adjacent datasets D S. Then by the assumptions and the version of Girsanov's theorem presented in Lemma B. one sees that there exists measure Q under which (XP))ec(o)) is equal in law to (XP))e )x under IP, that is
pe (xt be(o.T]
= P
and furthermore
dQ dP
B 2
dW)) ////0 7 [n(x22)) x(0) Pate))
-
for
Mxxn)) fæz n, D) (.),,
Then, Lemmas 4.1 and 4.2 give that DP and Rényi-DP can be obtained by controlling respectively the tails and the moments
of dP
Let us first focus on the DP bound. For any > 0, let := T23/44 cv BT log(1/8). Since [h| & c by assumption, one has
P
dP
$
P
exp
- -V2 2
188 / (M(x (e))
3
exp
Jo
% /
(0)) (a())))))))
d0
3 -
8 2T² ))
P
exp
V 2
(h(X R()) Ma(o).
exp
Ex
4
J' (-
B
= P
h(XD
k(t)> nn(t)), dw,) > cv 37 log(1/5)
2
Now, applying Lemma B.3 for ue =
M(X2 k(t)) nx(t)), which under our assumptions satisfies |ua| & &0v3 we find
dP aQ
> 6
& a.
Finally, Lemma 4.1 gives the wanted (s, 6)-DP bound.
Now we derive the bound on the Rényi-DP for a Lemma 4.2 shows that it sufficient to bound
dP
B(a 11)
/
L J. (M(XRe)) (a 1y 2 -
E
=
exp
4
We can bound the first term using that ((XP
((())))) (x())))))) & e, while the second term can be dealt applying Lemma B.2 for
Ue (1
(8/2) k())> nn(t)). This gives
dP
a-1
B(a 9(a-1)
((1 (111-00) (f((1-0a) MA(XD ((1x na(o)). noco).aw.))
E
< exp
E exp
d
4
& Greala -
- -1)
By Lemma 4.2 this implies Rényi-DP with e = Tca
B.6. Proof of Proposition 4.5
Let us assume > 1, noting that the result holds by Proposition 4.6 for T & 1. Let us fix adjacent datasets D, E S and let us define the process (Zi) by
dz, fo( dd) + wedt + 22/BdW, Zo = xo E Rd
17

---

DP Guarantecs for MCMC Algorithms
where uy is supported on i [T' 1, 7) and in particular
4 == [= (()):)) Bx(e)) - fD(Za na(e) - (Zr-1- -
Then, for E [T 1 one has
Z, - XP - -XP-PP1 f"
(ID(Znto): (n(o)) + - (x- k(a)s Te(o))
ds
T-1
-TT-1 -XP-1 [" (ZT-1 - -X-
T-1
(T -1p-1-
and hence ZT XPp almost surely. Furthermore, since (7) has a unique strong solution for each dataset one has that 7 = xP for 1 E [o, T 1] almost surely. Therefore by assumption one has for [0, T that
72 - = -
Furthermore note that, for E [T - 1,T],
Zz X D' = (T - -
< I - -X-11
CC
Hence, for E [0, 7] one has
Zx((t) - -xx(1) & C.
Using (8) one may therefore bound
luel & T. Zx(o)| + +
Now observe that by Lemma B.I, under the measure Q given as
dQ exp (v
B
T L
9 T T-1
(m,, dw,)
Rdl alP, )
T-1
one has that
p2 (2e)eeto
= =P
=((XP)
(23)
Moreover, since Zr X almost surely, by (23) one has that
pe Xp
P0 ZT
P
Now, we wish apply Lemmas 4.1 and 4.2 to obtain the wanted guarantees respectively on the DP and Rényi-DD of randomised algorithm. For any 5 > 0 and 1, let us set ε C2/4 /C2 log (1/5) and Ea aC2/4, where C2 3 + + c)a. Proceeding as in the proof of Proposition 4.6 one may show that
dP
IP
3 E6
8,
(P(I(Q & Ear
dQ
which is sufficient to apply Lemmas 4.1 and 4.2.
18

---

DP Guarantecs for MCMC Algorithms
C. Proofs for Section 5
C.1. Proof of Theorem 5.2
Let us fix adjacent datasets D, E and consider two versions (a m2>) and (Ι )n2 of the ULA algorithm (12)
Jaz1 be driven by the same sequence (zn mm1 of iid standard targeting TD and Tp respectively. Let (x mn and (= D' Gaussians, Let us define
6n = x xx
so that by the strong monotonicity and L-Lipschitz assumption V one has
Je, ~VK((z)) - VVK(=, < (1 2na + \e)
Now let us show
0 - 2 + 222 < 1.
(24)
For the lower bound one can show by standard calculus that the minimum value attained for > 0 in the above expression is 1 - a²² L2 To see that this is greater than 0, note that by the monotonicity assumption (13), applying
one must have
VK (z) - VK(y) > a/æ yl.
and therefore must have L > The upper bound in (24) follows simply by the assumption y E (0, 2a/L3). Then since -I < - z/2 for [0, 1]. one may conclude
l,n (VK(2,) (v)"))) & 71 222
By the assumption that that VVI, VV < c, one therefore has that
|en+1l < exx (V -V (VV - -NVP (x,")
(1 70 + 7 /2) + 2yc.
Iterating this bound from n = (since co = 0) one obtains for all n > that
2c
lenl & a- aL222
(25)
Now let consider the following interpolation of the ULA algorithm. Let define Kiy 20) + [0, oo) by (t, /Lt/r,, that is, the projection backwards onto {0, 7, 2y, Then consider the continuous time process
dxp -UD (1) ( dt + v2dW, x.P xO R
and likewise for D'. It is casy to verify that since the coefficients of the drift are fixed in-between the dime-diseretisation grid 2y....... one has that the law of X is equal to the law of (x:²), ), and likewise for D'. Furthermore, since X. and xP are driven by the same Brownian motion, one may apply (25) to conclude that
2c
sup 2
X (c)
X2, <
a LL212
So as to satisfy the assumptions of Proposition 4.5 we need to extend this bound from grid points (t,() to the whole of t >> 0. To see this note that
XP -P-XP XP x (t)
XD (t- (E-x(())VUU6x22,0))) (X2
(26)
and furthermore for arbitrary v.y Rdd and
0, if one defines
f(t) = | + yd |z| + (a y) + +2 1/
then since /" > 0 the function f cannot have a local maximum anywhere. Therefore
sup [(1) & max ((a) tE[a,b]
19

---

DP Guarantecs for MCMC Algorithms
Applying this principle (26) one sees that
XXP XP
2c
sup
t00
a
7122/2
2c Therefore one sees that the assumptions of Proposition 4.5 are satisfied for L, c > 0 as in the Proposition, and C' = and the result therefore follows by choosing T nry
a-
C.2. Proof of Theorem 5.6
As in the proof of Theorem 5.2, for adjacent data D ..., (dn)...,dm): D' (d% (d1:...,dy, dmm) we show that x. and xR almost surely close. The strategy here is essentially the same. Letting en = xn =n as before, one has
2
7 Σ 8
(Vi(=))
enn 1--222 2 Σ (en, Vh(2.)) v)(22))
cn
11
iEAn11
2 Σ
(vh(2 - vk(a,
iEAn+1
so that since by the Lipschitz assumption and the fact An+1 {1, ... m3 is of size 8, obtains
Σ Vk(z)))
<LLlen
iEA,
Then applying the convexity assumption obtains
len 2 Σ (V <1 2a + 1em?)
(27)
iEAn41
so that since before one has 0 & 1-12a + T,2g² < 1, one may square root that
|en+1l = len 7 (Vk(=>) 2) Vk(a 1² ?
Σ iEA.41
Vev de) Vau( (d))
(28)
iEAn+1
so that using the assumption Vzu(;-)] one sees that the bound (25) from before also holds in this setting.
Now let us find a continuous time interpolation of the SGD process (15). For the stochastic gradient we consider the process
(ne)e2 given for n E N and & E (ny, (n + 1)7) as 17₁ An+1, where (An)nii is the sequence of i.i.d. random variables
uniformly distributed on subsets of size s & m of {1, 2, ..., m). Then for every data D (II...., one may define the process (YP))s )120 as the solution to the SDE
d. D
Σ zET
vel( (1))
dt + 22/
(29)
where K.y is the backwards projection {0, 7, 27....} as in the proof of Theorem 5.2. Then it is easy to verify that the law of myy is equal to the law of D at which point one can use the strategy from the proof of Theorem 5.2 to obtain that
sup - Y, < t0
2c
a 7L2
at which point as before the result follows from Proposition 4.5, paying attention to the value of B > 0 assumed in the definition (15) of the SGD algorithm.
C.3. Proof of Theorem 5.7
Here we modify slightly proof of Theorem 5.6 previously. Specifically, note that D = (d1,... dm) and (d,...,, d,,, are adjacent then only one of their entries different, that there exists E {1,2, m) such that d, + d', however for
20

---

DP Guarantecs for MCMC Algorithms
j ... m) such that j one has d, =dz- Therefore, since have assumed vo(:, d) be constant for every d E DD may bound
Σ Vau(En, Vzu(an d;)l
207
1EAr+1
and therefore using (27) and (28) one has that
2cy
ent1l & +
and as a result
2c
suplen n²l
S(7L2/2->))
Then extending this bound to the continuous interpolation (29) as in the proofs of Theorems 5.2 and 5.6, and applying Proposition 4.5 as before, the result follows.
C.4. Proof of Theorem 5.8
The proof here is very simple: note that the assumptions imply that for every pair of adjacent datasets D, D' and E Rd. since An+1 is a subset of size & m of (1,2...., m,), one has D = (d1, dm), D' = (d',..., d",. that differ in only one element, so
1 Velr, c/c..
V ((
iEm
Therefore may apply Proposition 4.6 (29), and then since the law of (Yo Y.P ...YY,) is equal to the law of (xl ..... x..,,)) and (YPP, .YP,... ...,.) is equal to mapping from (Y)) the result follows from the data processing inequality (see Theorem in Erven & Harremos (2014)).
21


Reviews:
[{"review_id": "Z7uS5stwZ1", "reviewer": "Reviewer_dztJ", "summary": "This paper present theoretical results on differential privacy guarantees for Markov Chain Monte Carlo (MCMC) methods. They develop DP guarantees for both full chains and for the final state of the chain, and demonstrate how these results can be applied for specific instances of MCMC dynamics.\n\n## Update after rebuttal\n\nThe authors have answered my questions and I believe with the promised clarifications that the paper will be a valuable contribution.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for the careful comments. In the revised version of the paper, we will incorporate all their comments and fix all the typos, notation clashes, and other issues that were mentioned by the reviewer. Below we reply to the questions that the reviewer raised:\n\n- **Sorry for the basic question but what does it mean to \"choose\" a Bayesian posterior that has good DP properties? Do you just mean that you need to choose a model-prior combination that results in differentially private posteriors in order for any of the guarantees you provide to hold?**\n    \n    Indeed, we mean exactly what the reviewer wrote. We will clarify this aspect in the revised version of the paper.\n    \n- **What are $\\mu$ and $\\nu$ without subscripts?**\n    \n    We believe the reviewer refers to Proposition A.2. This was indeed an imprecise notation. We meant to refer to the families of probability distributions $\\{\\mu_{\\mathcal{D}}:\\mathcal{D}\\in\\mathcal{S}\\}$, $\\{\\nu_{\\mathcal{D}}:\\mathcal{D}\\in\\mathcal{S}\\}$. We will use the correct notation in the revised paper. \n    \n- **Should it be $\\leq$ at bottom of page 11?**\n    \n    Here there was a typo before the inequality that the reviewer points to. Since we use the strict inequality on line 590, it follows we have strict inequalities also in lines 597-599. For this reason, we have a strict inequality also in the display at the bottom of page 11. \n\n- **Re. “Suppose now that $\\lVert \\mu_{\\mathcal{D}'} - \\nu_{\\mathcal{D}'} \\rVert_{TV}\\leq \\zeta$ for some constant $\\zeta<\\delta_\\mu - \\delta_\\nu$.” – is this Assumption 3.1 in action?}, and also: \\emph{In the final inequality, where did the min over the two arguments come from?**\n    \n    In the revised version of the paper, we will clarify our proof strategy.\n    At this stage of the proof of Proposition A.3, we show that if $\\lVert \\mu_{\\mathcal{D}'} - \\nu_{\\mathcal{D}'} \\rVert_{TV}\\leq \\zeta$, then it must be that $\\lVert \\mu_{\\mathcal{D}} - \\nu_{\\mathcal{D}} \\rVert_{TV} > e^{-\\varepsilon}(\\delta_\\mu-\\delta_\\nu-\\zeta)$. Alternatively, $\\lVert \\mu_{\\mathcal{D}'} - \\nu_{\\mathcal{D}'} \\rVert_{TV} > \\zeta$. Hence, in either case, the two distributions are \"far\" in TV distance either for $\\mathcal{D}$ or for $\\mathcal{D}'$.\n    \n    We do not know whether $\\lVert \\mu_{\\mathcal{D}'} - \\nu_{\\mathcal{D}'} \\rVert_{TV} \\leq \\zeta$ or $\\lVert \\mu_{\\mathcal{D}'} - \\nu_{\\mathcal{D}'} \\rVert_{TV} > \\zeta$, but regardless we know that for $\\tilde {\\mathcal{D}} \\in \\{\\mathcal{D},\\mathcal{D}'\\}$ we have the lower bound shown in the equation on lines 613-614. By taking the minimum, we take the less stringent lower bound, which always holds. Finally, we optimize for $\\zeta$ to obtain the largest lower bound. This is possible since $\\zeta$ can be chosen arbitrarily. \n\n- **What is $\\tilde \\delta$ and how does it relate to the $\\delta$ that is assumed to exist in that Assumption?**\n    \n    This was a typo. In Assumption A.4, we should have written \"There exist $\\eta,\\tilde{\\delta}$ such that ...\"\n\n- **In the first factor of the RHS of the equation on top of page 13, shouldn’t this be $\\tilde\\delta$?**\n    \n    Indeed, we will correct this in the revised version.", "claims_and_evidence": "Clear and convincing evidence for the proofs with which I could properly engage (all up to Appendix B.3), after that everything looks ok to me but I am less confident about given that I do not routinely use these theoretical tools.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "I went through all the proofs in detail up until Appendix B.3. The proofs in Appendix B.3 and onwards I checked, but as stated above I am less confident about commenting on given that I do not routinely use these theoretical tools.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "From my perspective the relation to the broader literature is strong. The authors connect well to both background literature on MCMC and privacy, so I do not see issues here.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "I think the paper is clear and well-presented. The introduction to differential privacy and Renyi privacy was good and well-paced. I especially appreciate the efforts the authors went to to provide hyperlinks in both directions from propositions and proofs, allowing me to easily jump back and forth between statements and their proofs presented in the Appendix. To my knowledge, the work is original and in my view presents significant results at the intersection of MCMC and privacy guarantees.\n\nJust a few comments on improving clarity: \n\n- $P_{\\mathcal{A}(\\mathcal{D})}$ is used in Definition 2.2 on Page 2, but not defined until Page 5 (as far as I could see) – it was reasonably clear from context what it meant, but I think for improved clarity it would be beneficial to have defined it earlier.\n\n- I didn't like the overloading of notation, e.g., $\\eta$ is first a measure on $(E, \\mathcal{B}(E))$ but then a real parameter appearing in the discussion the DP of Monte Carlo estimators", "other_comments_or_suggestions": "Here are what I think are some typos I spotted:\n\n- In the line preceding Section 3, the divergence $D$ uses a comma rather than $\\Vert$ to separate arguments, inconsistent with other instances of this divergence\n\n- Section 3, 2nd paragraph: did you mean to say $(\\epsilon, \\delta + \\beta(e^{\\epsilon} + 1))$-DP of $\\nu_D$?\n\n- Final sentence of first paragraph of 4.2, and in the proofs in the Appendices, you write $(X_T^D)\\_{t \\in [0,T]}$ rather than $(X_t^D)_{t \\in [0,T]}$ and I imagine the latter is what you want so that the index actually appears somewhere?\n\n- Appendix B.1: final equality should have $\\mathbb{P}$ not $\\mathbb{E}$ on RHS", "questions_for_authors": "**Conclusions**\n\nSorry for the basic question but what does it mean to \"choose\" a Bayesian posterior that has good DP properties? Do you just mean that you need to choose a model-prior combination that results in differentially private posteriors in order for any of the guarantees you provide to hold?\n\n**Proposition A.3** \n\n- What are $\\mu$ and $\\nu$ without subscripts?\n\n- Should it be $\\leq$ at bottom of page 11? \n\n- Re. “Suppose now that $\\vert{\\vert{\\mu_{\\mathcal{D}'} - \\nu_{\\mathcal{D}'}\\vert}\\vert}\\_{\\text{TV}} \\leq \\zeta$ for some constant $0 < \\zeta < \\delta_{\\mu}−\\delta_{\\nu}$.” – is this Assumption 3.1 in action? \n\n- In the final inequality, where did the min over the two arguments come from?\n\n**Assumption A.4**\n\nWhat is $\\tilde{\\delta}$ and how does it relate to the $\\delta$ that is assumed to exist in that Assumption?\n\n**Appendix A.4**\n\n$\\delta$ in first factor of RHS of equation on top of page 13, shouldn’t this be $\\tilde{\\delta}$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4x4SnIq7wc", "reviewer": "Reviewer_iGVP", "summary": "This is a theoretical work studying DP and MCMC algorithms, focusing on:\n1. Connections between mixing, the privacy of the exact posterior, and the privacy of intermediate iterates.\n1. The privacy of Markov chains based on Langevin diffusion, e.g. the Unadjusted Langevin algorithm (ULA).\n\nI view the central new result as a uniform-in-time bound on the privacy loss of ULA in a certain non-convex loss function. Informally, we require the loss to be strongly convex outside a ball. The key step in the proof is to show that, for coupled versions of this process run on adjacent datasets, the iterates are never far apart.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful comments, and particularly for the suggestion of relevant connected work in the literature. In response to specific questions, we have the following responses:\n\n- **The informal takeaways from Section 3 I view as obvious. It is not clear to me what value the quantitative versions add...**  \n  The takeaways from Section 3 are indeed rather intuitive, but we did not find any such result in the literature. On the contrary, several papers proposed novel MCMC algorithms with DP-guarantees of the one-step transition kernel, motivating these as means to perform differentially private Bayesian inference. Our results from Section 3 (e.g., Proposition 3.4) make it very clear that such MCMC algorithms cannot achieve their goal of giving samples that are close to the posterior distribution unless the posterior distribution itself enjoys DP. This strongly encourages a shift in the approach to differentially private Bayesian inference.\n\n- **Section 4 claims a \"novel proof strategy to obtain DP guarantees of MCMC algorithms,\" ...**  \n  We shall make this aspect clearer in the next version of the paper, including a discussion on the following points. In Section 4.1, we give rigorous statements on how to obtain DP using the Radon-Nikodym (RN) derivative of the laws of the randomized algorithms for two adjacent datasets. This is much more general than the result in the notes the reviewer mentioned, but it is indeed not intrinsically a novel approach. However, thanks to our formal statement, it becomes clear that the DP of MCMC algorithms based on diffusions can be studied with Girsanov's theorem, which indeed gives an expression for the RN derivative of interest. Finally, we obtain results for the algorithm that releases only the $n$-th step of the chain with a novel perturbation technique, once again relying on Girsanov's theorem.\n\n- **The submission claims to solve Open Problem 1.1 from Altschuler and Talwar (2022), but (i) the submission gives an upper bound for a specific family of distributions and (ii) the submission gives no lower bound.**  \n  It is true that we do not calculate exactly the optimal privacy parameters. We thank the reviewer for noting this, and we shall be more precise in the revised version. However, we do believe that we address Question 1.2 (*Does the privacy loss of Noisy-SGD increase ad infinitum in the number of iterations?*) and make progress towards Question 1.1 (*What is the privacy loss of Noisy-SGD as a function of the number of iterations?*). We note that optimal privacy bounds are only known in the Gaussian case (see Theorem 3 in Chourasia et al. (2021)) and are unlikely to be tractable in general.\n\n- **The paper says \"we improved on known composition bounds,\" but then says \"this essentially matches bounds presented in Chourasia et al. (2021).\"**  \n  Indeed, the improvement in composition bounds is only in comparison to known bounds for $(\\varepsilon, \\delta)$ privacy, and not in comparison to known Rényi composition bounds. We thank the reviewer for noting this and shall make this point clearer in the revised version. Chourasia et al. (2021) proves a similar result using PDE machinery.\n\nRegarding the Questions for authors section.\nThe references provided by the reviewer are very interesting and explore pertinent connections. We are going to add them to the revised version of the paper, together with a discussion on the differences with our work.\n\n For these references and every work in the literature of privacy of Markov chains we are aware of, one of the following holds:\n1. The domain of the process is bounded.  \n2. The privacy bounds degenerate with the number of steps.  \n3. The deterministic part of the Markov kernel is contractive (i.e., the gradient of a strongly convex function).  \n\nThe main novelty of our work is that we prove privacy bounds without 1, 2, or 3, and use different and novel technical tools to do so. The tools used to prove privacy in [1] are either increasing bounds on Rényi divergence (see Lemma 2.2) or composition bounds that require noise that increases with time to be uniform (see Lemma 3.1).  In [2], all results are either on a bounded state space or degenerate with the number of steps (for large $T>0$, the RHS of (21) will be greater than $1$). Chourasia et al. (2021) considers a more similar setting and utilises a quite ingenious PDE argument to show uniform-in-time privacy bounds for a single draw from the SGD chain. However, in order to obtain explicit bounds, the authors have to assume strong convexity of the loss function. In comparison, we use a hybrid pathwise-perturbation approach, wherein we show that the two processes in question are almost surely close, then show the Radon-Nikodym derivative of their laws is mostly small by means of a perturbative argument and Girsanov's theorem. We are not aware of any such argument in the privacy literature.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I inspected parts of the theoretical arguments closely and believe them to be correct. Overall I think the theory is sound.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "This submission has serious issues here. There are key references missing (see below) and, with the current version, some readers might walk away misunderstanding the connections to existing work.\n\nHere are a few issues I observe.\n1. The informal takeaways from Section 3 I view as obvious. It is not clear to me what value the quantitative versions add. (For example: \"Any MCMC algorithm that is asymptotically exact will fail to be $(\\varepsilon,\\delta)$-differentially private for some $n$ when the posterior itself is not $\\(\\varepsilon,\\delta)$-differentially private.\")\n1. Section 4 claims a \"novel proof strategy to obtain DP guarantees of MCMC algorithms,\" but it seems to me to be the normal strategy for proving approximate DP. I ask a question below.\n1. The submission claims to solve Open Problem 1.1 from Altschuler and Talwar (2022), but (i) the submission gives an upper bound for a specific family of distributions and (ii) the submission gives no lower bound. \n1. The paper says \"we improved on known composition bounds,\" but then say \"this essentially matches bounds presented in Chourasia et al. (2021).\"", "essential_references_not_discussed": "[1] study the privacy loss of Langevin diffusion. [2] give uniform-in-T bounds on the privacy loss of DP-SGD in a non-convex setting.\n\n[1] Ganesh, Arun, Abhradeep Thakurta, and Jalaj Upadhyay. \"Langevin diffusion: An almost universal algorithm for private euclidean (convex) optimization.\" arXiv preprint arXiv:2204.01585 (2022).\n\n [2] Asoodeh, Shahab, and Mario Diaz. \"Privacy loss of noisy stochastic gradient descent might converge even for non-convex losses.\" arXiv preprint arXiv:2305.09903 (2023).", "other_strengths_and_weaknesses": "none.", "other_comments_or_suggestions": "none.", "questions_for_authors": "Without answers to the following questions, I cannot recommend acceptance.\n1. How does your proof strategy in Section 4 differ from that of [1, Section 1.1.1], for example? How does it differ from the approaches in Chourasia et al. (2021) or Ganesh et al. (2022)?\n1. Can you sketch how your paper needs to change in light of the extra citations?\n1. In particular, can you re-summarize how your technical contributions improve upon existing work?\n\n[1] https://dpcourse.github.io/2021-spring/lecnotes-web/lec-09-gaussian.pdf", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wG12gdgPIB", "reviewer": "Reviewer_kjX6", "summary": "This paper analyzes the differential privacy (DP) guarantees of Markov Chain Monte Carlo (MCMC) algorithms, focusing on both general MCMC methods and specific Langevin-based variants. It establishes that the DP properties of the posterior distribution are crucial for ensuring the privacy of MCMC samples, showing that if the posterior is not differentially private, the MCMC chain cannot be either. Using Girsanov’s theorem and a perturbation technique, the authors derive DP and Rényi DP bounds for the entire trajectory and final iterates of the Unadjusted Langevin Algorithm (ULA) and Stochastic Gradient Langevin Dynamics (SGLD). Their results improve on standard composition bounds by providing uniform-in-time privacy guarantees, particularly in non-convex settings, which were previously challenging.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their useful comments and remarks. We are going to incorporate them in the revised version of the paper. Below we address the questions from the \"Questions for authors\" section.\n\n- **Proposition 4.6. Is \"for any x, y, s...\" missing?**  \n  Indeed, we will add this in the revised paper. \n\n- **The authors claim that \"In particular, we find that the DP of the posterior is the crucial starting point to perform ...\"**  \n  We shall clarify this aspect in the revised version of the paper.  \n  Indeed, in Proposition 3.4 we do not make an assumption on the stationary distribution of the Markov chain. This is because such an assumption is not required to obtain the result, and moreover, our statement then applies also to biased MCMC algorithms such as the unadjusted Langevin algorithm. In essence, the result states that the law of a differentially private MCMC algorithm can be far from any probability distribution that has worse DP guarantees. In our context, we are particularly interested in the distance to the posterior distribution, hence we state the result in such a form. The Proposition then applies very broadly to any MCMC algorithm with a DP guarantee after $n$-steps that is not satisfied by the posterior distribution.\n\n- **Can the authors discuss the connection between Assumption 5.1 and the log-Sobolev inequality? Section 5 considers the non-convex setting. Does the function serve as a strongly convex regularization? Could the authors explain how it is used in deriving the results for algorithms where discretization is needed?**  \n  The reviewer brings up a very interesting connection with structural properties of the target, one which we are interested in exploring in future works. It is true that under Assumption 5.1 the target density does obey a log-Sobolev inequality. However, it would not be possible to prove privacy bounds solely under the assumption that for each $\\mathcal{D}$ the posterior $\\pi_\\mathcal{D}$ obeys a log-Sobolev inequality, since this is not enough to ensure the densities are close (for instance, by shifting the target densities).  \n  The assumption of a strongly convex part $K$ of the target posterior could indeed be a strongly convex regularizer, either for a Bayesian prior or a loss function, and we shall mention this in the revised version. We write $U_{\\mathcal{D}}=K+V_{\\mathcal{D}}$ since the former part induces a contraction and the latter part induces the processes to move apart. This is the same for the discretization and for continuous-time processes which target $\\pi_\\mathcal{D}$.  \n\n- **In Proposition 4.6 (Line 283) and Line 865, could the authors specify: \"almost surely\" with respect to what probability measure?**  \n  Thank you for bringing this to our attention, we will clarify this aspect. The distinction between being almost surely true for $\\mathbb{P}$ or $\\mathbb{Q}$ is not significant since the measures are absolutely continuous and therefore have the same null sets (this is always true for measures constructed via Girsanov's theorem). We shall make this clearer in the revised version. More generally, we only consider randomness induced by the algorithm, while the dataset $\\mathcal{D}$ is always considered fixed. \n\n- **Could the authors provide intuition on how this path-wise analysis is better than the advanced composition theorem of DP? Does the discretization reintroduce DP accounting similar to the composition-style analysis? Can the authors further clarify how the resulting order is better than previous results?**  \n  It is true that the results for the entire trajectory (Proposition 4.5, Theorem 5.4, and Theorem 5.8) essentially match those given by Rényi composition bounds. However, they exceed those given by the advanced $(\\epsilon,\\delta)$ composition bound and thus remove the need for complicated privacy accounting. We shall make this clearer in the revised version.  \n  However, the results for the final draw from the Markov chain (Proposition 4.6, Theorem 5.2, and Theorem 5.6) are new and use novel probabilistic techniques. In particular, these results are uniform in time, which is never possible with composition-based analysis. Additionally, they apply to processes taking values on the whole space with non-convex assumptions. We are not aware of any work in the literature that considers this setting.", "claims_and_evidence": "See questions", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "Yes. I checked the proof of Lemma 4.1. See questions", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "See questions", "other_comments_or_suggestions": "- Proposition 4.6. Is \"for any x, y, s...\" missing?", "questions_for_authors": "- The authors claim that \"In particular, we find that the DP of the posterior is the crucial starting point to perform Bayesian inference. This fact is supported by Proposition 3.4, which shows that if the posterior has weaker DP guarantees than the MCMC algorithm, the law of the MCMC chain after n iterations is far from the posterior in total variation distance.\" However, in Proposition 3.4, the $\\pi$ is not defined as the stationary distribution of the transition kernel, which may leave a gap between Proposition 3.4 and the claim on the DP and convergence rate. Could the authors provide an example of MCMC that satisfies Proposition 3.4 (since it is a lower bound)?\n\n- Can the authors discuss the connection between Assumption 5.1 and the log-Sobolev inequality? Section 5 considers the non-convex setting. Does the function $K$ serve as a strongly convex regularization? Could the author explain how it is used in deriving the results for algorithms where discretization is needed?\n\n- In Proposition 4.6 (Line 283) and Line 865, could the author specify: \"almost surely\" with respect to what probability measure?\n\n- Could the author provide intuition on how this path-wise analysis is better than the advanced composition theorem of DP? Does the discretization reintroduce DP accounting similar to the composition-style analysis? Can the author further clarify how the resulting order is better than previous results?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8ICW0lxobG", "reviewer": "Reviewer_WFdZ", "summary": "This papers studies differential privacy\nand R\\'{e}nyi differential privacy \nfor Markov chain Monte Carlo (MCMC) algorithms\nfor the path and the final value of the algorithms.\nThe general results are then applied\nto study two popular MCMC algorithms, \nthe unadjusted Langevin algorithm (ULA)\nand stochastic gradient Langevin dynamics (SGLD).\nThe paper establishes the privacy\nguarantees uniform in number of iterations, and the bounds\non the privacy on the privacy of the entire trajectory. \nAs a result, this answers an open question (Question 1.1. in Altschuler and Talwar (2022))\nabout uniform-in-time differential privacy guarantees\nin a non-convex setting on an unbounded space. \nThe results generalize the results of Chourasia et al. (2021)\nto a non-convex setting, and match theirs in the strongly convex regime.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for the positive review and for their comments. We will incorporate the reviewer's suggestions in the revised version of the paper. Below we reply to the questions that the reviewer raised:\n\n- **In the very beginning of Section 3.2., do you need any assumption on $f$?**  \n  We do not directly need to state assumptions on $f$ straight away, but restrictions on $f$ indirectly come into play to ensure that the assumptions that follow are satisfied. We will add a comment about this in the revised version of the paper. \n\n- **In the last line in Lemma 4.2, it is better to write $(\\alpha,\\varepsilon)$-Rényi-DP instead.**  \n  We agree and will correct this.\n\n- **Currently, Proposition 4.5. is about privacy of the path, and Proposition 4.6. is about privacy of the final iterate...**  \n  We agree with the reviewer and we will incorporate this change in the revised paper.\n\n- **In the first equation in Proposition 4.6., is it (uniformly) for every $s$? Please make it more clear.**  \n  Indeed, here we forgot to mention that the result should hold uniformly over $s$, as well as for any $x,y\\in \\mathbb{R}^d$. This will be fixed in the revised paper.\n\n- Regarding the weaknesses of the paper: we agree that the assumptions we consider are quite restrictive, but these should be compared to the existing literature. It is likely that relatively strict structural assumptions are needed in any case for the class of algorithms we consider. Regardless, we are going to add a discussion about the assumptions as suggested, highlighting their weaknesses and when they might be satisfied.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The paper seems to be rigorous though I don't have to check all the proofs details.", "experimental_designs_or_analyses": "N.A.", "relation_to_broader_scientific_literature": "The paper establishes the privacy\nguarantees uniform in number of iterations, and the bounds\non the privacy on the privacy of the entire trajectory. \nAs a result, this answers an open question (Question 1.1. in Altschuler and Talwar (2022))\nabout uniform-in-time differential privacy guarantees\nin a non-convex setting on an unbounded space. \nThe results generalize the results of Chourasia et al. (2021)\nto a non-convex setting, and match theirs in the strongly convex regime.", "essential_references_not_discussed": "N.A.", "other_strengths_and_weaknesses": "Strengths\n\n(1) The paper is well written.\n\n(2) The analysis seems to be rigorous.\n\n(3) As the paper claims, the paper answers an open question (Question 1.1. in Altschuler and Talwar (2022))\nabout uniform-in-time differential privacy guarantees\nin a non-convex setting on an unbounded space. \n\n(4) The results generalize the results of Chourasia et al. (2021)\nto a non-convex setting, and match theirs in the strongly convex regime.\n\nWeaknesses\n\n(1) The assumption (equation (8)) in Proposition 4.5. seems super strong to me. \nAs a result, when applied to ULA and SGLD, the Assumption 5.3. \nis super strong.\nCan you add some discussions on some real examples that satisfy such an assumption?\n\n(2) Even though the results generalize the results of Chourasia et al. (2021)\nto a non-convex setting, the non-convexity here seems to be quite restrictive, in the sense\nthat it is simply a strongly convex and smooth function plus a function whose gradient\nis uniformly bounded.", "other_comments_or_suggestions": "1) In the very beginning of Section 3.2., do you need any assumption on $f$?\n\n(2) In the last line in Lemma 4.2, it is better to write $(\\alpha,\\epsilon)$-R\\'{e}nyi-DP instead.\n\n(3) Currently, Proposition 4.5. is about privacy of the path, and Proposition 4.6.\nis about privacy of the final iterate. However, when you present the corresponding results\nfor ULA for example, you present the results for the final iterate first (Theorem 5.2) and\nbefore you present the results for the path (Theorem 5.4). I think it is better to make\nthe ordering consistent.\n\n(4) In the first equation in Proposition 4.6., is it (uniformly) for every $s$? Please make it more clear.", "questions_for_authors": "See my comments for weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this is a well-written paper, proving and gathering useful theoretical results and tools to study the differential privacy properties of MCMC algorithms. This paper is theoretical with no empirical work, but I don't think this is a problem: all the theoretical results follow a clear narrative so that their correctness and validity seems reasonable, and there isn't an unreasonable amount of proofs stashed away in the appendix. The reviewers have provide some suggestions to improve this work, and the authors have offered some ways to incorporate these: please read the discussions again carefully while preparing the final version.

Some comments I have (in addition to those of the reviewers):
1. Reviewer iGVP mentioned some of the results in Section 3 are "obvious". I think they are still useful and the rest of the paper still has more than enough contributions. However, I wonder if the example cited: Corr 3.3: "there exists an n such that the MCMC output is not DP if the posterior is not DP" can be strengthened to "there exists an n_0 such for all n > n_0, the MCMC output is not DP if the posterior is not DP"?

2. Lemma 4.1: isn't this essentially the usual interpretation of (\epsilon,\delta)-DP with likelihood ratio replaced by Radon-Nikodym derivative. That is, \epsilon,0 DP with a \delta probability of failure is exactly (\epsilon,\delta)-DP (see e.g. Lemma 7.1.5 of Vadhan 2017, "Complexity of differential privacy"). I think something similar is probably true for Lemma 4.2. I think the RN-derivative framing is still useful for the applications with diffusions, but I'm not sure how novel these lemmas actually are, and I think these existing results should be elaborated in the paper:.
Decision: Accept (poster)