Differential Privacy Guarantees of Markov Chain Monte Carlo Algorithms

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:

• In the very beginning of Section 3.2., do you need any assumption on $f$?
  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.

• In the last line in Lemma 4.2, it is better to write $(\alpha,\varepsilon)$-Rényi-DP instead.
  We agree and will correct this.

• Currently, Proposition 4.5. is about privacy of the path, and Proposition 4.6. is about privacy of the final iterate...
  We agree with the reviewer and we will incorporate this change in the revised paper.

• In the first equation in Proposition 4.6., is it (uniformly) for every $s$? Please make it more clear.
  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.

• 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.

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.

• Proposition 4.6. Is "for any x, y, s..." missing?
  Indeed, we will add this in the revised paper.

• The authors claim that "In particular, we find that the DP of the posterior is the crucial starting point to perform ..."
  We shall clarify this aspect in the revised version of the paper.
  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.

• 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?
  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).
  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}$.

• In Proposition 4.6 (Line 283) and Line 865, could the authors specify: "almost surely" with respect to what probability measure?
  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.

• 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?
  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.
  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.

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:

• The informal takeaways from Section 3 I view as obvious. It is not clear to me what value the quantitative versions add...
  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.

• Section 4 claims a "novel proof strategy to obtain DP guarantees of MCMC algorithms," ...
  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.

• 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.
  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.

• The paper says "we improved on known composition bounds," but then says "this essentially matches bounds presented in Chourasia et al. (2021)."
  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.

Regarding the Questions for authors section. The 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.

For these references and every work in the literature of privacy of Markov chains we are aware of, one of the following holds:

1. The domain of the process is bounded.
2. The privacy bounds degenerate with the number of steps.
3. The deterministic part of the Markov kernel is contractive (i.e., the gradient of a strongly convex function).

The 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.

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:

• 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?

  Indeed, we mean exactly what the reviewer wrote. We will clarify this aspect in the revised version of the paper.

• What are $\mu$ and $\nu$ without subscripts?

  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.

• Should it be $\leq$ at bottom of page 11?

  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.

• *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: In the final inequality, where did the min over the two arguments come from?

  In the revised version of the paper, we will clarify our proof strategy. 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}'$.

  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.

• What is $\tilde \delta$ and how does it relate to the $\delta$ that is assumed to exist in that Assumption?

  This was a typo. In Assumption A.4, we should have written "There exist $\eta,\tilde{\delta}$ such that ..."

• In the first factor of the RHS of the equation on top of page 13, shouldn’t this be $\tilde\delta$?

  Indeed, we will correct this in the revised version.