Can Stochastic Gradient Langevin Dynamics Provide Differential Privacy for Deep Learning?
Authors: Guy Heller
Ethan Fetaya
Venue: ICLR 2022 Submitted (2022)
Keywords: differential privacy
bayesian inference
sgld

Abstract: Bayesian learning via Stochastic Gradient Langevin Dynamics (SGLD) has been suggested for differentially private learning. While previous research provides differential privacy bounds for SGLD when close to convergence or at the initial steps of the algorithm, the question of what differential privacy guarantees can be made in between remains unanswered. This interim region is essential, especially for Bayesian neural networks, as it is hard to guarantee convergence to the posterior. This paper will show that using SGLD might result in unbounded privacy loss for this interim region, even when sampling from the posterior is as differentially private as desired.

CAN STOCHASTIC GRADIENT LANGEVIN DYNAMICS PROVIDE DIFFERENTIAL PRIVACY FOR DEEP LEARNING?
Anonymous authors Paper under double-bling review
ABSTRACT
Bayesian learning via Stochastic Gradient Langevin Dynamics (SGLD) has been suggested for differentially private learning. While previous research provides differential privacy bounds for SGLD when close to convergence or at the initial steps of the algorithm, the question what differential privacy guarantees can be made in between remains unanswered. This interim region is essential, especially for Bayesian neural networks, as it is hard to guarantee convergence to the poste- rior. This paper will show that using SGLD might result in unbounded privacy loss for this interim region, even when sampling from the posterior is as differentially private as desired.
INTRODUCTION
Machine learning and, specifically, deep learning models show state-of-the-art results in various fields such as computer vision, natural language processing, and signal processing (e.g.. Carion al. (2020): Devlin al.] (2019): Ballvii & Andrewsd (2021)). Training these models requires data, which in some problems, c.g., healthcare, finance, can include private information that should not be made public. Unfortunately, has been shown (Fredrikson al.. (2015): : Carlini al. 2021 that private information from the training data can sometimes be extracted from the trained model. One common approach handle this issue is Differential Privacy (DP). Differential Privacy is a framework that ensures that the distribution of training output would be the same, even if we switch one of the training participants, thus ensuring privacy.
As privacy is usually obtained by adding random noise, it is natural to investigate whether Bayesian inference, which uses a distribution over models, can give private predictions. Previous works have shown that sampling from the posterior is differentially private under certain mild conditions (Wang et al. (2015): Foulds et al. (016))] Dimitrakakis et al. (2017)). The main disadvantage of this method that sampling from the posterior is generally hard. The posterior usually does not have closed- form solution, and iterative methods such as Markov Chain Monte Carlo (MCMC) are needed. While theoretical bounds the convergence of MCMC methods for non-convex problems exist (Ma et al., 2019), they usually require an infeasible number of steps to guarantee convergence in practice.
Stochastic Gradient Langevin Dynamics (SGLD) is a popular MCMC algorithm used to approxi- mately sample from an unnormalized distribution (Welling Teh 201T). The privacy guarantees of this specific sampling algorithm are interesting as it not only returns a sample from the posterior, which can be private, but the process itself of stochastic gradient descent with Gaussian noise mir- rors the common Gaussian mechanism in DP. Previous work Wang et al. (2015) gives two disjoint privacy analyses: The first is for approximate sampling from the Bayesian posterior, which only relevant when the SGLD almost converges. The second uses the standard DP analysis utilizing the Gaussian mechanism and the Advanced Composition theorem (Dwork & Roth 2014), which only applies for limited number of steps and is not connected to Bayesian sampling-
From these two lines of research, differential privacy bounds for SGLD are provided for its initial steps when close to convergence. Neither of these cases is suitable for deep learning and many other problems, as one would limit the model's 's accuracy, and the other is unattainable in a reasonable time. Consequently, the privacy properties of SGLDD in the interim region, between these two private

---

sections, of high importance. One could speculate that since the initial steps of the algorithm are private, and it converges to the posterior that is also private, then sampling at the interim region will be private as well. If so, SGLD could be considered solution for training differentially private deep neural networks. Unfortunately, as we will show, this is not the case.
This work provides counter-example based problem, showing that approximate sampling using SGLD might result an unbounded loss of privacy in the interim regime. Moreover, this loss of privacy can even occur under strong conditions when sampling from the posterior is as private as desired, and the problem is complex even stronger conditions than what we can assume for most Deep Neural Network problems. This implies that special care should be given when using SGLD for private predictions, especially for problems where it is infeasible to guarantee convergence.
Our Contributions:
Bayesian linear regression
2 RELATED WORK
Several previous works investigate the connection between Bayesian inference and differential pri- vacy (Wang al. (2013); Foulds al. (2016): Zhang al. (2016); Dimitrakakis et al. (2017); Geumlek et al. (2017), Ganesh & Talwar (2020)) None of these papers provide guarantees over is Wang al. (2015) that specifically investigates stochastic MCMC algorithms such as SGLD. As mentioned, its analysis only covers the initial phase and when approximate convergence is achieved.
SGLD differential privacy in the interim regime. The closest work
As many of the privacy bounds require sampling from the posterior, SGLD is to be used, it requires non-asymptotic convergence bounds. Dalalyan (2014) provided non-asymptotic bounds on the error of approximating target smooth and log-concave distribution by Langevin Monte Carlo. Cheng & Bartlett (2018) studied the non-ase aa-mmmttttiicc bounds on the error of approximating a target density p" where log p" is smooth and strongly convex.
For the non-convex setting, |Raginsky et al. (017)) showed non-asymptotic bounds on the 2- Wasserstein distance between SGLD and the invariant distribution solving Itô stochastic differential equation. However, to provide (e, differential privacy, an algorithm should produce a distribution that is O close to neighbouring databases. Total Variation (for details about Total Variation Tsybakov (2008) is a more suitable distance for working with differential privacy. Ma et al. (2019) examined target distribution p", which is strongly log-concave outside of region of radius R, and where In p" is L-Lipschitz. They provided a bound on the number of steps needed for the Total Variation distance between the distribution at the last step and p" be smaller than e. This bound is proportional ( ). where is the model dimension. This result suggests that even little non-convexity will render running until close to convergence impractical. A conclusion from this work is that basing the differential privacy of SGLD on the proximity to the posterior is impractical for non-convex settings.
BACKGROUND
3.1 DIFFERENTIAL PRIVACY
Differential Privacy (Dwork et al. (2006b ay: Dwork 201 1): Dwork & Roth (204)) is definition and a framework that enables performing data analysis on a database while reducing one's risk of exposing its personal data the database. An algorithm is differentially private if it does not change its output distribution by much due to single record change its database.
Definition 1. Approximate Differential Privacy: A randomized algorithm M D + Range M) is
(e. difffrrrentl private if S Range(M) (M) and (VD, D E D ||D - Đ < 1) eq. holds.
D. are called neighboring databases, and while the metric can change per application, Hamming distance is typically used.
Pr(M(D) E S) exp(e)Pr(M()) e +
(1)
Mironoy (2017) suggested Rényi Differential Privacy (Definition B a relaxation to differential pri- vacy, and way to translate RDP guarantees into approximate differential privacy guarantees.
2

---

Definition 2. Rényi Divergence Rényi 1961 the Réyni divergence of order v iss
For two probability distributions Z and Q over R,
(z A 1
log E [(
Q(z)) (22(2)
2(xz)
Definition 3. (v, RDD:P A randomized mechanism f D + R said to have e-Rényi differential
privacy of order v, or (v, RRDP in short, if for any adjacent databases D, D E D eq. holds, where Dy is Rényi divergence of order v.
D(((D))I((D) SE
(2)
Lemma 3.1. (Mironov (017)) Proposition 3). If (U,c)-RDP, also satisfies (e + ferential Privacy for any
log v-1, 8) Dif-
3.2 STOCHASTIC GRADIENT LANGEVIN DYNAMICS
Stochastic Gradient Langevin Dynamics (SGLD) is an MCMC method that is commonly used for Bayesian Inference (Welling & Teh 2011). The update step of SGLD shown in eq. 3 where 0, is the parameter vector at step J. My is the step size at step j. p(0,) is the prior distribution, p(3a [9)] the likelihood of sample Y given model parameterized by 8j. b is the batch size, and n the database size. SGLD can be seen as a Stochastic Gradient Descent with Gaussian noise, where the variance the noise is calibrated the step size.
0j+1 =0, 2
0,+
71 Ve, Imp(0,) + n
8,
In In 10)) + VTS
(3)
1y uni 1,....n]. { 10
common practice in deep learning is use cyelic Stochastic Gradient Descent. This flavour of SGD first randomly shuffles the database samples and then eyclically uses the samples in this order. For optimization, there empirical evidence that it works as well or better than SGD with reshuffling, and it was conjectured that it converges at faster rate Yunn et al. (2021)) Cyclic-SGLD the analog of cyclic-SGD for SGLD, where the difference is the use the SGLD step instead of the SGD step. For simplicity, will consider cyclic-SGLD in this work.
METHOD
Our goal is to prove that even when the posterior is as private as desired, sampling using SGLD for steps can be non-private as desired. This requires analysing the distribution of SGLD after T steps, which is hard in the general case. However, we show that we can get the desired behaviour when looking at a simple Bayesian linear regression problem where everything Gaussian with closed-form expressions. Our result is summarized in theorem
Theorem 1. v 5 < e.5. there exists domain and Bayesian inference problem where single sample from the posterior distribution is (e, 8) differentially private, but, there number, T, for which performing approximate sampling by running SGLD for T steps is not (E',8) differentially private.
As e' can be as big as desired, and e can be as small as desired, a corollary of Theorem is that could always find problem for which the posterior is (c,8) differentially private, but there will be a step in which SGLD will result in unbounded loss of privacy. Therefore, SGLD alone can not provide any privacy guarantees in the interim regime, even if the posterior is private.
To prove our theorem, we consider a Bayesian regression problem for linear model with Gaussian noise, defined in eq. domain D defined in eq.

---

get tight bounds the differential privacy in y fr +
8~ NNO,
0~ a00,00
1
logplu/z, 0) -3 0xr) log (2tT 1og(2x/11)
2
D(n, 71, Th. F1, 01
{a,, Vill Vi cl S ; 2i, Uz. c, E Ryoi 21 x; S 2n
(5)
We assume that x > 3 and that 71 <
n, C, 21, Th, " are parameters of the problem (c. F1, Th. and " are used, together with the database size n, bound the database samples a chosen region). For every e, and 6, we will show there exist parameters n, C, Th, that have the privacy properties required to prove Theorem | The restrictions on the dataset simplify the proof but know the parameter we are trying to estimate. Later we show in subsection 4.3 that they can be replaced with a Propose-Tess Tespos--Test-Peee Rele-Re phase. We will address the problem Bayesian Linear Regression for the model described in eq. oon domain DD Bayesian linear regression problem on domain D. This problem has closed-fore solution for both the posterior distribution and the distribution each SGLD step, thus enabling each case.
bit unnatural it assumes we approximately
The heart of our proof is showing that for big enough sampling from the posterior is (e, 6) differ- entially private, with e O( while for SGLD there exists a step in which releasing sample will not be 5) differentially private for é' Ω ). Therefore, by considering instances of the problem where c ~ On $ /e) and n big enough, sampling from the posterior will be (c, 6) dif- ferentially private, while there will be SGLD step in which releasing sample will not be (e', d) differentially private for e' = ((ne).. We note that the bounds contain dependency over 5, but since are using fixed and equal 5 for both the posterior and SGLD privacy analysís, omit from the bounds for simplicity.
255
(u, -2yNdgg
20
0.0
0.0
0.2
0.4
0.6
0.8
100
1.2
(step)
1e8
Figure 1: A value indicative the distance between the distributions of samples from two SGLD processes running neighbouring databases for the linear Gaussian model. For details on Ps, p. , of see subsection 4.2 The parameters used for this experiment (n 1149019, a = 0.1,8 = 1, 1.8, x; = 0.9, 71 = 0.1, 22 = 1.001, 1165165) ensure (1.6, 0.01) differential privacy when sampling from the posterior.
Figure D depicts an indicative value of the distance between the distributions of samples from two SGLD processes running adjacent datahases for the Bayesian linear regression problem. As
4

---

will later show, SGLD on one of these examples is Gaussian while the other is mixture of Gaussians. We plot + E; (Me-pi) where is the mean of the single Gaussian at timestep 6, μ
[oi)²
the mean of the i'th Gaussian component at timestep t and (of)² its variance. We can see that close the initial iterations and convergence (which implies
though the distributions differential privacy in those areas), in the interim region, they are significantly apart, which implies lack of differential privacy.
4.1 POSTERIOR SAMPLING PRIVACY
To prove Theorem we first need to show that 48 < 0.5,c, there exists domain and a Bayesian inference problem where single sample from the posterior distribution is (e, 6) differentially pri- vate. In order to do so, this section will consider the differential privacy guarantees provided by one sample from the posterior for the Bayesian linear regression problem on domain D.
We begin by using well-known result for the closed- form-solution of the posterior distribution for Bayesian linear regression problem (see Bishop (2006) for further details). By using the parameters of our problem, get Lemma 4.1
Lemma 4.1. The posterior distribution for Bayesian linear regression problem on domain D is
Σx J.343
D) = N000,,,
(6)
a 23
B
Using the posterior distribution, one can calculate the Renyi divergence between every two neigh- bouring databases, thus getting expression for the Rényi differential privacy, as shown in Lemma
Lemma 4.2. For Bayesian linear regression problem on domain D, such that n. max + 10 2i
1 + n f }. one sample from the posterior is (v, Rényi differentially private. O zt for >>>>>>>> t
22
2
DJ
2/
6
2(n 1)07
(n ( 1)x7
(V
vz
2
+ 2v3
10"
9
1
()
(c+n
(1 + x 3)22
n
1c+nos
2v3
9 (x73)²
n²-m 2 10
7/3
n3
We can show that for e >>> + each of the terms bounded by O E The first and second terms are bounded by O()). The third term bounded by (122111) Noticing that n n (11)))))))
22 T we get that the third term is bounded by (( As >> n²,, the fourth term cnltm v.. the term is bounded by O =a +
is bounded by O O(=n"), ), and since en 7
Lastly,
since >>>><> n 2+, the last term is bounded by O For the full proof, see subsection A. in the appendix.
Translating the Rényi differential privacy guarantees into approximate differential privacy terms can be done according to Lemma 3.1] which gives Lemma 4.3
Lemma 4.3. With the conditions of Lemma 4.2 sample from the posterior is (c1 + 8)
In A) w-1
differentially private.
By choosing such that In()) < and then choosing n big enough such that c < 2, we get that v-1 the posterior is (c, differentially private.
4.2 STOCHASTIC GRADIENT LANGEVIN DYNAMICS PRIVACY
To complete the proof of Theorem D we need to show that even if one sample from the posterior
is (e, d) differentially private for Bayesian linear regression problem on domain D. it does not
5

---

provide any guarantees the privacy of SGLD for that problem. In order do this section will first consider the loss in privacy when using SGLD for the Bayesian linear regression problem on domain D. and then, together with the results of section 4.1
will prove Theorem
In order to show that SGLD is not differentially private after initial steps and before convergence, it is enough to find two neighbouring databases for which the loss in privacy is as big desired in those steps. We define neighbouring databases D and D2 in eq. 7 and consider the Bayesian linear regression problem D1 and D2. We set the learning rate be ? (a (a-nz
D1 = {0t,3e :2; 2; = The yi = c }
D2 = { U4 3, The Vi = TA m U
2h
Th 2
To tightly analyze the differential privacy loss when approximately sampling via SGLD at each step, we need to get a closed-form solution for the distribution for each step. For database D1, the solution Normal distribution. For database D2, different shuffling of samples produces different Gaussian distributions, therefore giving a mixture of Gaussians.
We look at cyclic-SGLD with a batch size of and mark by 0z. the samples on the j ''th SGLD step when using databases D1 and D2 accordingly. Since D1 samples are all equal, the update step of the cyclic-SGLD is the same for every step (with different noise generated for each step). This utdate-step contains only multiplication by scalar, addition of a scalar, and addition Gaussian noise, therefore, together with conjugate prior results in Normal distribution for 0z: ((5;; P5 af).
For D2, there is only one sample different from the rest. We mark by r the index in which this sample is used in the cyclic-SGLD and call this order r-order. Note that there are only different values for and, as such, effectively only different samples orders. Since every order of samples is chosen with the same probability, r is distributed uniformly in [1,... n). We mark by 07 the sample on the j't multiplications by scalar, addition of scalar, and addition of Gaussian noise, and since the prior is also Gaussian, then 0 is distributed Normally, (i ; (,, (a5)²). As is distributed uniformly, f distribution mass is distributed evenly between all 0j, resulting in a mixture of Gaussians.
SGLD step when using r-order. Since, for given order, 0z is formed by series of
Intuitively what will happen is that each Gaussian components .0, as well as 0y. will move towards the similar posterior Gaussian. However, at each epoch, 8 will drag a bit behind because one batch gradient is smaller. While this gap can be quite small, for large n, the Gaussians are very peaked with very small standard deviations; thus, they separate enough that we can easily distinguish between the two distributions.
According to approximate differential privacy definition (Definition [] it is enough to find one set such that p(0; E S) > e'p(0, E 5) + to show that releasing 0z is not (e, private. We choose S {s|s Hj} some step we will define later on. clear from symmetry that p(0, > 145) = 1/2, and by using Chernoff bound we can bound p(0; > 14)).
Lemma 4.4. p(0, p3) < Ei_repp
exp(
(M4- -D
2(07)
Using Lemma 4.4 we can upper bound the mass of 0, in S, and thus lower bound the difference between 0 and O distribution masses in S for some step j. To Lemma 4.4 we first need to
lower bound (e) "ay-a5"* a5) for a certain step. This is done in Lemma 4.5
(
Lemma 4.5. 3k Z>o such that (Aq--1) Pla+
2 E ). for big enough.
(6
To prove Lemma 4.5 we first find closed-form solutions for 0 ()+ (x41j distributions (Lemma Using the closed-form solutions, we find a lower bound over (((x+1)a ())+)))² as function of kt which applies for all & (Lemma A.2). To upper bound (0(++1)m)² we find an approx- imation the epoch in which the data and prior effects the variance are approximately equal,
A.1

---

marked k. We choose the step in which we will consider the privacy loss (īk]+ +1) and show that ) is upper bounded at this step (Lemma A.4). Using the upper bound on the difference in
(6 +1k1+1)n
means and the lower bound the variance, Lemma 4.5 is proved. By using the lower bound from
Lemma 4.5 in Lemma 4.4 we get Lemma 4.6
Lemma 4.6. For the Bayesian linear regression problem over database D1, such that n. is big enough, 37 Z000 such that approximate sampling by running SGLD T steps will not be (e, 8)
private c < (0())),4 < 0.5.
From Lemma 4.3 we see that sampling from the posterior is (c, 8) differentially private for c = (G ). From Lemma
that for SGLD, there exists step in which releasing a sample will not be (6',6) differentially private for = 2 ) Therefore, considering instances of the problem where e On Vtn sampling from the posterior will be (e, 6) differentially private. However, there will be an SGLD step in which releasing a sample will not be (e', 6) differentially private for é' = (nee). Since we can choose n to be big desired, we can make the lower bound over as big as we desire. This completes the proof of Theorem
4.3 PROPOSE TEST SAMPLE
Our analysis of the posterior and SGLD is done on restricted domain 'D defined in eq. 5 These restrictions over the dataset simplify the proof but are bit unnatural as they assume we approxi- mately know c, the parameter we are trying estimate. This section shows that these restrictions could be replaced with a Propose-Test Test-Release phase (Dwork & Lei (209)] and common practices in deep learning.
When training statistical model, it is common to first preprocess the data by enforeing it in a bounded region and removing outliers. After the data cleaned, the training process is performed. This is especially important in DP, as outliers can significantly increase the algorithm's sensitivity to single data point and thus hamper privacy.
Informally, algorithm 1 starts by clipping the input to the accepted range. It then estimates weighted average of the ratio di. (line 12) and throws away outliers that deviate too much from it. The actual implementation of this notion is a bit more complicated because of the requirement to do so privately. Once the database is cleaned, algorithm privately verifies that the number of samples is big enough, so the sensitivity of p(0 W)) to a single change in the database will be small, therefore making sampling from p(OlW) (e, 8) differentially private. This method is regarded as Propose-Test Test-Release, where we first propose a bound over the sensitivity, then test if the database holds this bound, and finally release the result if so.
We define Remin in eq. 26 in the appendix to be the minimum size of W for which the algorithm will sample from p(0) W) with high probability. We will show later on that this limit ensures that sampling from p(0 W is (c, 5) differentially private.
We define p(0 W to be the posterior for the Bayesian linear regression problem over database W. From Lemma 4.1 follows that p(0) ()) has the form of
Elewndew Tith8
p(0 = NO0;
a ((ewwee 279
a Σ (nLDeww 27,8'
Claim 4.1. Algorithm 1 is (5e, 26) differentially private.
By claim C.9 steps 6-13 are (3e, differentially private. By corollary C.3 steps 14-19 are (2c, 6) differentially private for given m and n2. Therefore by the sequential composition theorem, the composition is (5e, 26) differentially private. The claim proved by noticing that if steps 6-19 are private with respect to the updated database (after step 5), then they are also private for the original database.
Claim 4.2. When replacing line 19 with sampling via SGLD with step size 1) (ata 2 3 By then
(T(m)) Eno - E such that the updated algorithm is not (c, 8) differentially private Ve e Ryo, 8 if ranfoor for T(m) steps.
7

---

Algorithm Propose Test Sample
Input: D = {Ti, y4 ) Parameters: 6, 0.5, 21 > 0, 21, 0,8 A E (1.3). (0.2).m (p2.
I: for i 1.2..... .N do
2: I; + m, 21}
3: I; + min J
4: Y: f max(y::0) 0}
5: end for
6: in <- Ri - log 23 + (
7: V = [1 v: s 111)
8: n2 + IV|
log + (
9: if n2 S 1 then
10:
return null
11: end if
12: m < Lisgnee
D(rewev o7
in m + Lap( 1 2(m 112
(n 1)2t
14: W + [(xi yi) 1 ml S n22
15: nw < W log( 28 + Lap(?)
if nww Temin then
17: return null
end if
19: return sample from p))[W)
Proof sketch (See appendix for full proof). We first note that by choosing P+ P1, the sensitivity of m grows slower than the bound over the distance !: - m/. Therefore for n, big enough, samples for which R = m will be included in W with high probability. Consequently, databases D3, D4 E D will reach, with high probability, to step 19, which from our previous analysis over SGL.D (see subsection 4.2 will cause an unbounded loss privacy.
P1 Ps >
D3 (Ti, Wi Ib, n1," Wh
(8)
D4 (Ki, Jh; ni an
U FA
2 1
Th
5 WASSERSTEIN DISTANCE AND DIFFERENTIAL PRIVACY
As we have shown in Theorem region. That means that to get private samples using SGL.D, one must limit the number iterations, thus utilizing the Gaussian mechanism, run until approximate convergence. Therefore, interest to get non-asymptotic convergence bounds for SGLD so that we guarantee privacy after known number of steps. Previously, several works have given non-asymplotie bounds; however, some of those do so for the 2- W-Wassesstein metric (Raginsky et al. al. (2017); Cheng et al. (2018)). This unfortunate the 2- Wasserstein metric is unsuitable for differential privacy easy create two distributions with 2- Wasserstein distance as small as desired but with disjoint support.
cannot give any DP guarantees for SGLD in the interim
of
It is, however, interesting to ask whether combining bounds on the 2- 2-Wasserstein metric with Lipschitz continuous probability densities will allow us to get privacy guarantees. The intuition why this should be enough is simple: If p, are two distributions with small 2-Wasserstein distance, then there is (under mild conditions) a mapping, f : X' + X, such that the pushforward maintains fiP = 9 (i.e. for each measurable set S qS)) p(f fffff((S (S)) and that E,IlIz [( One can assume that p(x) ss (x())) and (zx) Rs (z)) as x ze f f(x) with high probability. Unfortunatcly, this intuition does not hold exactly, the map f can change the density considerably but still be
8

---

pushforward by changing the volume. For example, if we assume f is smooth and bijective, get the standard change of variable formula such that p(z) = (f(()) det(Jy)), so p(r) = g(f(x)) only if [det(Jr)] zz 1. This issue becomes more severe as the dimensionality increases.
For completeness, will share results connecting p(æ) q(x) when W2(p, q) is small, and both distributions are I-LLpschitz continuous. This bound scale poorly with dimension, and such ill-suited for SGLD deep networks, but can still be useful for Bayesian sampling in low-dimensional problems.
For distribution we define the density (x) as the average of p(z) on ball of radius À centered around x px(x) vofa(A] S1zt00) p(x + 2)d2, where (x) is the ball in Fd of radius À centered around and vola(A) is its volume.
Claim 5.1. For L-Lipschitz continuous distribution we have 1p(x) PX(x)1 S AL.
Theorem 2. Let P. Q be absolutely continuous w.n. the Lebesgue measure in R with finite second- moment and L-Liisccitzz continuous densities p, q. If W2( < <, then have
vola(A)
(Vol(AA) (oola(> (x) ( 2XL + vola() c)
px(x) <
wola(A - c) (x(x)
The proof is extension of the proof of theorem 2.1 in Walker (2004) to dimensions larger than 1. The detailed proof is in the supplementary material.
It is easy to see that as vala dimensionality as it requires extremely small give non-vacuous results.
())
x1+
the bounds usefulness quickly diminishes with
This, however, can still give useful results low-dimensional problems.
CONCLUSION
As shown this work, while SGLD has interesting connections privacy and some guarantees, caution is required if one wishes to use it to get private predictions. This is especially important for models such deep neural networks, where is infeasible guarantee convergence.

---

REFERENCES
Eren Balevi and Jeffrey G. Andrews. Wideband channel estimation with a generative adversarial network. IEEE Transactions on Wireless Communications, 20(5):30493300 -3660, 2021. doi: 10. 11099TWC.2000:34471100
Christopher Bishop. Pattern Recognition and Machine Learning. Information Science and Statistics. Springer- Verlag New York, 2006.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan- Jan-Michael Frahm (eds.). ) Computer Vision ECCV 2020, pp. 213- 229. Springer International Publishing, 2020. ISBN 978-3-030-58452
Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss,, Katherine Lee, Adam Roberts, Tom B. Brown, D. Song, U. Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In USENIX Security Symposium, 2021.
X. Cheng and P. Bartlett. Convergence of langevin meme in kl-divergence. In ALT, 2018.
Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Underdamped langevin MCMC: A non-asymptotic analysis. In Conference On Learning Theory COLT, 2018.
Arnak Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79, 12 2014. doi: 10.1111/rssb.221 12183.
Jacob Devlin, Ming-Wos Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre- Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies. Volume (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.1865/11/N11-1422 URLhttps:
//ac otgp///ooooooo/1991////////
Christos Dimitrakakis, Blaine Nelson, Zuhe Zhang, Aikaterini Mitrokotsa, and Benjamin I. P. Ru- binstein. Differential privacy for bayesian inference through posterior sampling. Journal of Machine Learning Research, 18(11):1-39, 2017. URL http:://jmmz: wttpa//rrrggppppp////11/
15-257. htmml
Cynthia Dwork. A firm foundation for private data analysis. Commun. ACM, 54(1):86-95, January 2011. ISSN 0001-0782.
doi: 10.1145/1866739.186667 1866758.. URL https://doi... /ttp::///oo.oo///////
1145/1866739 866758
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. Proceedings of the Forty- First Annual ACM Symposium Theory of Computing, STOC '09, pp. 371-380, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585062. doi: 10.1145/ 11451 36414.44100 1536466
1536414.1536466.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 93-4))221110000000 August 2014. ISSN 1551-305X. doi: 10. 10.1561/0400000042.
URL
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. Advances in Cryptology EU- ROCRYPT 2006, 25th Annual International Conference Cryptographic Techniques. volume 4004 of Lecture Notes in Computer Science, pp. 486- 503. Springer, 2006a. doi: 10. 00.1000/11766677 29. URL https://iacr..ot www./rrci/a/aeeeeee eurrerrpe2/00//000453///0 90000333300044443. pdf
the Theory and Applications of
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin (eds.), Theory of Cryptography, pp. 265-284, Berlin, Heidelherg. 2006b. Springer Berlin Heidelherg. ISBN 978-3-540-33732-55.
10

---

James R. Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of privacy-preservngg bayesian data analysis. In Uncertainty in Artificial Intelligence, UAI, 2016.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Confer- ence on Computer and Communicattions Security, CCS 11,, pp. 1322-1333, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450338325.
doi: 10.1 10.1145/281010.
2813677. URL https://doo org/ 0. 1141/1442225 G 03. 2813677
Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence analysis of discretized langevin memc. ArXiv, abs/2010. 14658, 2020.
Joseph Geumlek, Shuang Song, and Kamalika Chaudhuri. Renyi differential privacy mechanisms for posterior sampling. In Advances in Neural Information Processing NeurlPS, 2017.
Alison L. Gibbs and Francis Edward Su. On choosing and bounding probability metrics. Interna- tional Statistical Review, 4094)54 2002.
M. Gil, F. Alajaji, and T. Linder. Rényi divergence measures for commonly used univariate contin- uous distributions. Information Sciences, 249:124-1311 2013. ISSN 0020-0255. doi: https://doi. org/10. atticcle//11/5002005553333
3.06.018. URL /tttps:/ sci www.iieneedrrr.............
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I. Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116(42):2088 1 20885, 2019. ISSN 0027-8424. doi: 10.1073/pnas. 182003316.. URL https: / /wwww /www.pna.... org/content/ 11 6/42/20881
Ilya Mironov, Renyi differential privacy. CoRR, abs/1702.07476, 2017. URL http:://aaxxx org/abs/1702. 07476
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1674-1703, PMLR, 07-10 Jul 2017. URL
mlr. wttp:psss/////sssssssssss/s/////
.html
Alfréd Rényi On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, pp. 547-561. University of California Press, 1961.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519.
Martin J. Wainwright. Hligh-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Stephen Walker. New approaches to Bayesian consistency. The Annals of Statistics, 32, 2004.
Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and
stochastic gradient monte carlo. In Proceedings of the 32nd International Conference on Ma- chine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2493-2502, Lille, France, 07-09 Jul 2015. PMLR. URL https: http///pttpcp.cpppptppppppp mlr pI..p33es/337 wangg15 ht.ml
M. Welling and Teh. Bayesian learning via stochastic gradient langevin dynamics. In ICML, 2011.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and gd? In Conference on Learning Theory, COLT, 2021.
Zuhe Zhang, Benjamin Rubinstein, and Christos Dimitrakakis. On the differential privacy of bayesian inference. In AAAI Conference on Artificial Intelligence, 2016.
11

---

A SGLD AND POSTERIOR PRIVACY
Proof Theorem
Define
1
3
2h
71 >
12
>
1
+
71:
21
2
2 2ln(g)
+1
11 - max
a
a
(e cR - 2) +
20 }
20x 1
2h
8
2
(2 1) )
16 1m
n1 max [1 +
-, 1 11+1
(1 + 8
27
2
9
cxi
10
1623 (z) 3)
10
9
())
)11
(1 + 10
th
2f
3
-2
4v (of a + 0)
[11
)) 2
(1 + 10 of
1
of B
th 11
2
1
n1 max(1 (1 + 10
+
17
x/
32
201 )²
"p = max (n1, (m
n2, n3, ((é (66--ni In 8))e
3
a
U1 m 1 22
Cp = ?
We consider the Bayesian linear regression problem over database Dj (defined in eq. with n "p and c = Gp. Since np > n1, the problem holds the constraints of lemma [A66] Consequently, there exists step for which one approximate sample from the posterior using SGLD is not (e", 6) private
for all e" such that e" <e e 3
3
(2( + ln.5.5 - 8). From eq. 10 the choice of np
3222
promises that é' S c the posterior using SGLD not (E',8) differentially private.
3². (
)² + In0.5 - 8); Therefore approximate sampling from
201 32a7.
Since n2 > n2 and np ny, the problem holds the constraints of Claim D.30 Therefore one sample from the posterior is (c,8) differentially private.
3
) Cp 3² + In(0.5 - 6) 2 d'
201
32x
np
2 2 (e' (0.55 5)) 3.
32. 8 p220) 201
3
a
(10)
32n 1 3
2220 201
2(122 1) 2 22 ln(0.5 8))e p
3
a
np 2 ((' - ln -5)e कंं
32x
jz 201
) -
A.1 POSTERIOR SAMPLING PRIVACY
Proof Lemma 4.1 eq. II is known result for the Bayesian inference problem for linear model with Gaussian noise with known precision parameter (B) and a conjugate prior (Bishop) (2006) 3.49-4.51. for details). By choosing the basis function to be Φ(xx x,, working in one dimension,
12

---

and choosing my 0, a- we get the linear model defined in eq. described in Lemma 4.1
4 and matching posterior
p(w/ t) (w; m., SN); mx (S mo + +300t); SN So + 335
(11)
By definition 3 for a single sample from the posterior to be (v. e') RDP, the Rényi divergence of order between any adjacent databases needs to be bounded. We consider two adjacent databases D, D D, and w.l.o.g, define that they differ in the last sample (where it is also allowed to be (0,0) for one of them, which saves us the need to consider also a neighbouring database with size smaller by 1). To ease the already complex and detailed calculations, definitions in eg 12
Proof Lemma 4.2
D (i::i:) U (Ti, Vn D 2: U (fn.0n)
(12)
1i q
Σ 4:24
According to Lemma 4.1 and with definitions in eq. 12 the posterior distributions are
B(g + Inlin)
1
p(0)D) (,;))
0²
a (z )²)
a + + xn)
(13)
3(q + 8n
p) NO i ;3); p p=
(2
+ (2 &n)
By Gil al. 2013), the Réyni divergence of order D (fillf)) for fi, f2. uni-variate normal distributions with means Pl, P2 and variances 01, d2 accordingly. is
Do(Ailff2) = In σ1 + " 1)
1
of
1((m - 12)² (o²);
02 2
2
(o = vo (1 v)o
Therefore, for p(0 and D) the Rényi divergence of order as shown in eq. 14 omit the subscript for (a²), since is clear from context to which distributions it applies.
where
1 1/2 1)
6²
1 1v(u A)
((((() D)) In
(o2)
2 (o²);
(14)
(03); = u)o²
According to claim D.25 (a²); 0. Therefore the value D, (p(() D). )))()) exists. In order to
prove Rényi differential privacy, each of the terms of (p(p(( D) ), ())) bounded separately.
The bounds on each of the terms are proved at claims D.26 D.27 and D.28
By Lemma 4.2 sampling from the posterior (v, 6 RDDP, therefore by Lemma 3.1 sampling from the posterior is also (e1 In(4) ,- differentially private.
Proof Lemma
13

---

A.2
STOCHASTIC GRADIENT LANGEVIN DYNAMICS PRIVACY
Proof Lemma 4.4
p(O; > w5) = Σ pl0 My) p3) 07) -
Σ M0; - -1g 14 - (3j D2) (2) 051D2) =
1
p(0; [1 M4 D2)
11
1 exp( (1) - 23)
2(05)²
Where the inequality holds due Chernoff bound (For further details, see Wainwright (0199
Proof Lemma 4.5 By lemma A.5 for n max 13 27 (e
2)++
2243 200 x
eq.
15
holds for some E Ryo. We can see that this lower bound is dominated by _/ therefore proving Lemma 4.5
(M(TK)+1)n Pm( )2
3
)²(_)²
2e
(0t (1(11+1)m
11
32x
n
(15)
11 max/6, 1 22
Proof Lemma 4.6 By Lemma A.6 for max x न.
-2)
x/ there
20 3 20
exists T E Zo (Marked in Lemma A.6 as [b]] such that running SGLD for the Bayesian linear regression problem over D₁ for T steps will not be (c differentially for < e', defined in eq. 16 and 0.5. Since dominated by f.. this proves the lemma.
3
{ + +n(5.5 - 8)
é d' 22g
2
32x
(16)
la = max 6, 1 + 2 40
A.3 STOCHASTIC GRADIENT LANGEVIN DYNAMICS DETAILED ANALYSIS
In order to ease the analysis of the SGLD process, markings in eq. 17 are used, Th O, (, c, are as defined for the Bayesian linear regression problem, and 1j defined in subsection 4.2
[1 =
7( + n, Å [1 3/ (a + nl Th 2 = 2
" n
2/2
" nc
Th 2h 2
(17)
2
2
Lemma A.1. The forms of 0r 1m are
k Σ (1 + Σ
n-2
n
0 (k+1)a 1)a 0.8 (m-
+
1=0
i=0
1=0
0.11 0o(Asm-2jht1+
(k+1)n
Σ (p+ VTEidA- + -T(xa--
Σ (p+ VEn)A->>
Σ (
14

---

Proof Lemmal A.7 Welling & Teh (2011) define the SGLD update rule as in eq. 3 This rule can be
applied to the Bayesian linear regression problem over databases D1, D2 as following
1 09 7 Vo,p(0;) = -8,a
p(0,) = N(0,; =n =n) = In V2Ta
p(0z)
2
p(u))0,) N(y; 0, 0 Imp(vil8;) Inl
(yi 8,
Ve, (u,1(1,10,) = (y:- 0,01) +
0j+1 - 01 + 2 -0, + n ( 0, + Vn
0 " (a - +n2, + 1
n + Víšz =
2
2
0 " (a + -n=z + ner 3- + n
"
2
2
By using standard tools for solving first-order non-homogeneous recurrence relations with variable coefficients, the value of 0z can be found.
01 0==-x= âA=
00 P
VOC
R
p+
VTC
1Ai-1
1=2
00Å1-11 + +00+ VTEEA
+ (p VIg)
11-1-(111-
00i1~11 + (0+ V C0+ VTS)
1-11(i-1)
0021-11 + + VTJA
(p + TT
x==
n-
n-1
00ix~11 + p1n-1 + Σ
E' Σx X
X' + VH
Now by defining a new series- 01 1k+ = c1 kn + C2 and using the tools for solving first order non-homogeneous recurrence relations with constant coefficients, the value of kn can be found
01
8m. = cti
+
= 01 +
c2
hi=
C1
1=2
2=
k-2
k-2 C2
024 k-1 + C2
cj = (fuc) + c22
k-1
cj
mm0
im0
n-2
0 1(A-~11 + (pxn-1
VT
X²)
(Ax--1p.
1=0
1=
The proof for oz is done in similar manner.
Corollary A.1. 8 (i++1)m N(0()+1)m' Piotij (0 ((++1)n)))
Lemma A.2. Mentn Pan--n 2 - ner
M(n (A - (
atno?
Proof Lemma A.2 The proof of this lemma is separated into two cases, for 1 and for 1.
For r = 1, it is easy to derive eq. 18 from lemma A.1 using E(oo] = and E[g] = 0.
n-2
1m px-11 (1
(1 = 0
1=0
1=
(18)
n
Pkntn = p Σ
Am
+
pp=11
Σ T
1=
15

---

We use the sum of geometric sequence to get
pA--1 E(sth-l1ys = (pl 1-1 -n1
+ 1 1 (14"-1)&t1.
0 X
1 iA"-1
j=0
Therefore the difference between the means can be lower bounded:
Pn Pkutt= =
1 ((+1)m
1 An-1
1 (AA
1 An-1
(p(
1 ) +
10(
+ 1)
1 - A"
1- 2d=-1
1-
1 - (k+1)n
nex²1
(1 (1- X*) 1- (1A(1-1)ykt3 nex²3
(1 - 1 ( + -
1 \"
a + nx 3
1- id--1
a nr
(1 )
2cI²3
(dslm11ykkt nex2
(1 - 1m-1 11-
( + マ
1
+ n
1 اip-1
a + noy
ncx23 3
(1)(n-1)88t2 (1 1n { + 3
[11
1)m
_ || =
a + nx 8
1 _qa-1
ncx28 8
12 aa( - (++1)(++2(0-1)) + (k+1)) 1) ( (j++1 - x++1)(1 - 10113)1
a + nx 8
1- 1a-12
3
(n+ (1+ - )
a + n
1 - 1-11
ncx²8 B
(k+1](n-1) (2++1 (
a + n
nex²3 3
An11 a + nz 5
) (1(-1) - 2htl)
where equality holds from claims D.I equality holds because x < 2 < 1. This proves Lemma
D.2
D.3 equality
** holds from claim D.5 and the in-
A.2 for 1.
For the case of r > 1, from Lemma A.I it is easy to see
0r21 (k+1)m
1100
1=0
1-1
n-2
n-1
Σ (2 +
X + V
Σ
X
1=0
1=0
1=
n-
pA- p Σ
X² +
EX
1=0
0
Therefore M12 follows
1k+1) 1)m
2
A-1
n-2
n R-r-1
[l I x11 x(( +
11 +
Σ
+
Σ
x
1=0
16

---

Consequently the difference in means for r >> 1 can be lower bounded:
Mkntn - *kh+t==
2-
k-1
n- 2
A" A 13
Σ
12 + x
(11 (11 1014--
+p Σ トター
==
1=0
1=0
n-
k-1
n- (d 1P +
Apit2 Σ
Σ
1³} + \" xm - p) =
j=0
1=0
x-2
\" p()
Σ x+
1=0
5=0
n-2
(d0+2) + (10+1 -(+1)
X T0 (p- - p) =
1=0
1 1- X-11
+ -x- ncr
1m 0(4 - )(t1)
a + nr [>(1 - )
1-1
4 1 (A--1))
3
-1 + ! + \ x - p) =
1- 1- (1 - 1n
x
4
1 - ---1
+ \- ncr 3
A" 1"-rabn-17 ((n-1) 1) p() k+1 - 1
[(> - -(]+
1-1
a + nx 3
10 1x))(m-1)]
+ )m 1) g++ - ) + 1
(p- - -p) =
1 11=-1
A"-r 3C 3
k((n (k( (2 14 (1- + nc 3
no 3 [(1 1)
a no7 3
1-11 1 12 a 1 11
+ 1k( - ] + (p- - p) =
1- 12--1
An-r ncxR
- 84+1 - --11 -1tt0)
1|+
nof 9
--- ncx B
+ 1- 13 [3 St)M(n-1))]
(A
+ (p (p- P) =
+ no 3
1 1
1n ncz 3
Abnn11)
1) (8/t1 - -
a + nzz 9
An- ncz 3
(1 1- - 1-110
12 aall - 2()
+ (p-
no 3
1 1-
ncz 3
1n-1
(k 1) 11+t1 - (
a + no 9
An ncx 3
() - - \" 1--1 1-21220(1 2((b(1-1)11
+ ---T p) >m
a no 9
1 dr^-1
X 11 ncx B
(1 -
+ no? 3
where equality holds from claims D.6 and D.7, equality ** holds from claim D.10 holds from claim D.I and equality **** holds from claim D.11 and À >>> X.
equality ***
17

---

Lemma A.3. For 23, > 3, n
z00 200
1
3le
R+ such that upper bounds defined in eq.
19
hold all k:
())+)))))) s 10/1
111=-1924
(19)
(o-(1))) 6(11"
Proof Lemma A.3 easily computed from first general upper bound on km )a is found at eq. 20
The proof will be separated into two cases, r and 1. (o can be
the fact that both the noise and prior are distributed normally.
(ohnta)²= == = - (1)(x11))((42)) +1
1
Σ
2 (2222(n-11p-
a
==
(A) (1- 11)22
(1((--1))((+-1)11
+11
2
1=0
n-1
2
(1 (++11) s
1=0
(20)
n-1
2
X 2
17
j=0
(A 1)n
ri)
Σ
X 21
77
i=1
- -
(1)
2
1 2-2
where the inequality holds because À <
By claim D.12 this upper bound can be further bounded for S
2n loga (+-)(11127) -
such
that eq. 21 will hold, therefore proving the bound for r =
1 -(1h++)) 1)m
(dx(n (2 + yu
< 2(4) 1))
(21)
1- 2-2
For 1, (o ) can be bounded following
18

---

(ohuta)²=
x-2
k-1
R-
Σ
121
1as=~1122
Σ 1
5=0
Σ
2 + - (21=-1)22 (21"-1)2 ( 5
==
(dAn (1 11/3 h-2
n-1
Σ \
Σ
Σ ^ 1
1=0
Σ
2i + (2X-~1)22 (Axm
==
k-1
(d4 (dam-1)9) 1 (i^m-1)2h + m((im-
24
1
Σ (11m-11)3
Σ 1
X
4=
1=
n-1
k-1
n-1 Σ
(21m-1)2k ) +
11((m-1)22
2 +
(^An-1)2)
2 +
x
~*
1m
j=0
1=
1=0
2(2x~-1je) ($Am-1)2h ( + 1(Ax~~111 2k
7-1
2 +
k-1
11
R-1
Σ
a
0m0
j=0
0m0
(22)
where inequality follows from and > 1, inequality ** follows from S n, and inequality *** holds from claim D.15 x2y) 1, this bound can be further developed
For S 2n
loga( 14
2 (1
k-1 +
2((x--1)21
-1xm + n(( 11
25
(A Td
25
Σ
1=0
1=0
1=0
(23)
(
The inequality holds from claims
D.12
D.14 which provide the bound for 1. All that is left is
to prove that 1 loga( ( 14 mq (1-12)
O. which is done in Claim D.22
2n
Lemma A.4. Mark is
1 log,
(1x=)) 1, for the conditions of Lemma A.3
2n
1t uz
5 + 20 (2x=-112 1 (A2(m-1))2Th1
(o (oppen)
p2 6((2>~)) (A (o Thjtn
Proof Lemma A.4 This proof will be separated into two cases, for > and for r For > 1, the bound found eq. 22 has no dependence on the choice of k. therefore holds also for [k]. This bound was, in turn, developed for & at eq. 23 using three claims. If these claims also hold for [h], then the bound in eq. 23 also holds for [k] and the lemma is proved for > 1.
Claims
D.14
D.12
hold for all k: <
1 loga (1-x5))))) and since [k]
+
2m
27 log
they holds for [k] Claim D.15
was proved for k, hence also holds for
x
[
19

---

For 1, the bound found at eq. 20 is applicable for all k, hence
- 2(1]+++))
(o (1k)-))))) (Ax=-))((())1))) _ + +
1- X-2 I ((x=-))((())))) _
- 20
where the last inequality holds from claim D.17
Lemma A.5. For i defined in Lemma A.4 the conditions of Lemma A.3 and
max 2 m3. (e 2) (5555)
(nnm - Pr Whin nin )²
# a 3
2 e
)
(o (okintt )2
32x 3
U1
1 = max + 2e 27.
Proof Lemma A.5
(1kkjuta
P
(x--1
noo R atmer
> (z) () - A(
21 01(AAm-1)22 (AAm-1)1
9k]ttt
X2]4](m-1) 1) (A--1
n (116]+1
2141+21)2 -1k)+t))
aem 8 (2--1
(ÅTh)+1 )
atne 0
atnz
81 (AAm-11-
Bi(AA--1)21 [\Tl
112(r-1)
nca 3
- 111
ax2(r-1)
nco7 3
Alkl+1
)a
)²(1
11a )² 2
111
a no? 3
11
a + nx
a> ax2(r-1) 1r- 1)
nco 3
(2 - (1-(1--
))
a + nog .
(a no 3)2
(a Ino28)
1()
nco 9
nn 3
)2(
)²2
a + no ,
(a + n 3)2
(a +a++$n=?p) 2n=²3)
112(r-1)
new 3
i/ f 3
112((-11)
ncx2 3 )2
n 3
)2(
)2 2
(2nx² B)² )²
111
a + no 3
(a + no B)2
21
2n 3
11)
( (
12
(r-1) 1)
3
{-1² >
"1
Ama k
11
32
1)
3
a
3
2
32x
3
32x
n
where first inequality holds from A.3 A.4 and the definition of U1. the second incquality follows claim D.17 and claim D.22 fourth inequality holds under the assumption of na > - n and last inequality holds from claim D.19
Lemma A.6. For the Bayesian linear regression problem over database D,, the conditions of LemmalA.S and k as defined in Lemma A.4 approximate sampling, by running SGLD ([k]+1)m steps, will not be (e, 8) differentially private for
8 < 0.5, <e- - a
3
)2
In(0..5 -65 8)
201
32.
3
01 = max (6, max(6,
+ 20 x
I it is enough that there is one group, S, such that ((0((1)+1) E Di) > e00 (1(( E D2) + 8, to show that releasing (1fk)-1jm is not (c, private. Consider S {s|s -Dm From claim D.23 and since ((k))1)) ~ 24 holds. The conditions for the right term to be smaller
Proof Lemma A.6 According to definition
N(O, ((k)+1))i/(((1++ 02 (1k)+1)m) ). eq.
20

---

than 0 (thus making the approximate sampling not (c, private) are found in eq. proving the lemma.
25 therefore
2 a
(())
d'pl@(rk)+an) E SSD)) + 5 p(0 E & c'c
$22
+ 0.5 (24)
6-
1v
32
[g)
+ - 0.5 <0
6-6
322
(g)
0.5 6
(25)
) 2 < In (0.5 - 8)
6
201
32
C
C<6
24
a
2
C 2 In (0.5 8)
201
32x
n
B PROPOSE TEST SAMPLE SUPPLEMENTARY
Umin which is used in algorithm
is defined following
2 ll(
V
+1
+ 2hH - 11
2 (1 + 8
(v (V-1),
1),
16rBxt
= max
)r
mm
x
10 E.T
32v
(x + xx,
)m) 2-
9 (=) B)²
10
32
(z +
)) 2-201
9
(x)
10
(26)
8v
a + 3)
mm)
9 2
8v
(z) a
+ 8)
10 218
24 10v
+ v x
T82 = max [ +
1
x
B
x
Denin max (n61, 7122 01 7
max(n61,
22
C PROPOSE TEST SAMPLE PRIVACY
Proof Claim 4.2
We set the algorithm parameters in eq. 27 and matching databases Ds. D1 defined We note that we only define lower bound over ni. which will be updated later on.
eq.
P3
1.15; p2 0.45; P1 1.25, m1 0.49;
fn/2
1
1
1
11 max{2
log 4- log
100p 20+10ps
(27)
28'
25'
8 3: 24 =1
a =
Mark the return value of the algorithm as r, the event the algorithm running on database Dy and W D3 A Dy: the event of the algorithm running database Da and W D4 A A and
21

---

S f > pa). where N4 is the mean of the sample distribution at the SGLD i'th step given database D3 (Similarly to as defined in subsection 4.2) We will show that Ve E Ryo, 8 < à 3n1 such that eq. holds.
E > P(rE +
(28)
We first show that
P D2 D3)= = 0
(29)
PirESAA; D₂) = 0
Notice that the algorithm can return result in S only if reached step 19. Consider an event where
the algorithm reached step 19 and Ab.. From Ayy 3(ii Me) E D3 such that Mi - -m| 2 n²² However, since ((z, y:) E D3 zz = then V(z,, 21) D3 2 m| > n2 and therefore
[W| = 0. Under the assumption that sample from p(010) returns reull then in this case the algorithm
also returns null and therefore P(r E S A Abpy! Da) = 0. Same arguments hold for D4.
Following eq.
29
prove eq. 28 it is enough prove eq.
30
P(r S) As) D P(r E S Aa) - 56 >n E P(r E S)D,, Aa)+ + e P E S4 (AA + e S A.) +
(30)
From claim C.1 Abound, such that Vng > Ahound, inequality holds. From Lemma 4.6 for big enough 37 E Zozo such that eq. 31 hold (Where 65 < 0.5 according to the claim conditions). Therefore, 3k, Aboundd E R20 such that Vn1 > Ibboudd e'' > kn 2(1-pa) and eq. 31 hold. As
P3 > 1, by choosing n > max (obonnddd ($) 20 } get that e' > e. Consequently, by choosing 1 > max(Nbound, Thoundy (+) 3103-13 }. inequalities * and *# hold, and the claim is proved.
é' 1==0(n(0s-11) P(r S\Da, Aa) > é P(r (SD4, A4)+
(31)
Claim C.I. 3nhound E Zgo such that the probability for algorithm 4.3 to reach step 19 with
W- D& (marked event A) is greater or equal to 1 - 50 for all n1 Aboundd
Proof. Mark the event of nw > Rmin m E [m n² m + n A n2 1+p2-0.1 0.1
> 7iT A mn S
n1 A V = D as B. Since Ps B) = it follows that Ps) 2 P(A A B.Ds)
P(A D₂) D3) = Ps)) Therefore if 3ng such that Vn, > ny. P(B)Ds) 2 58
the claim is proved.
P(B[Ds)
P(m E [m ng² m + n²t A nnw > Amin D3, V = D, n2
1+p2-0.11
> ni ni S n1)
P(n) 1-p--1-0. 0.1 nt V = D, n - nı, Da) P(V D,ri S T1 <11)s)> >
P(m E (m n²² m + n A nw min D3, V Dnng 1+p2-0.1 -.1
> b 1ī S n1) 36
P(nw > Mmin D3, V = D, n22
1+p2-0.11 > p1 1i - nn, m E [mm n m + n
P(m E (m n , + n! D3, V = D, n2
m
1t 0.1 7 n m1 - >
P(nw > Dmain D3, V= D, D.
1+p2-0.1
> nl! nu 2 n1 m E [m n m + n 48 -8
1-55 56
(32)
22

---

By corollary C.I and claim C.3 for nı big enough first inequality holds. By claim C.4 for ni big enough second inequality holds, and by claim C.3 for n1 big enough third inequality holds. Therefore for n, big enough eq. 32 holds and the claim is proved.
Claim C.2. For nı > max 1 11pp 44 log 28
2
P(A 2 nl nn Sm))s) 2 1 28.
Proof. Mark the noise added at step 6 as 1
P(Rft 2 n²²
I n1 D3)
1
1
P((n1 +1
log
01 2 n1 A +1
log
S mm
26
28
1
1
P((n +1
log
2 03 ^ 1
-
log
12) =
20
c
26
1
1
P((n1 + 1
log
P1
2 1 A 14
log
D3)+
E
20
é
28
1
1
1
P((n1 11
log
11
"
1
log
D3)
2
c
26
28
1
1
1
P((n +1
log
2
03
A 14
-
log
D3)
20
28
1
1
1
P((n1 + 1
-
e
log
28
2 n
|4| 1 log 28
c
D2) P(L4 S
log 28
D2} 2
1
P((n 2- log
P1
n D3)
26 1 26
26
Where last inequality holds from following equation
1 -
1
1 log 1 exp( 1
P(LL S log =
2P(4 S log
26
26
E 28
E
28
Last equality holds since nı 1110p
7 ni
< 12)10n
11
0.1
(2 and therefore
(n1 - 2 log t ym > ) > n1
-0.1
= =11 03
Corollary C.I.
10p1
vn, > max
4 log 28
P(V = D3 A m S mn) 21-1 25.
2
1 199+10p2) _42 log 1
Claim C.3. For n > max
25
P(n
P(n)-p2-00 111---00111 0.1
> n D3, V = Dz, n1 mm) 5.
Proof.
P(n2 0.9+p3 > iff D3. V = D3, S m1) 2 P(n 0.0+ > nn
D3. V = Dz)
1
P((n1 - 2 log 26
0.9+p2 > nz" (n) 2 [V| 2- log
2
e 1
28
P((m1 2 log e 28
0.9+p2 > n²t D2) 8=1-6
where the second inequality holds since P(Lap(? 2) < 1 log 1/2 < 8, and last equality holds since
(nj - 21 log 28 0.9 > (2 > n 1+ 022 = nf
Claim C.4. Ang, E 7 such that
ii(1) > 1 1-6 6. Vm > nib : P(m E [m n2 m ng')] D3, 122
0.9+p2
23

---

Proof. Mark the noise added at step 13 as (
P(m [m nlz m + nl
D3, n2
0.9
> Kg
P(1 E [-ng" n2 D3, n2
0.
> fi?1) 2
1
1- 2(, exp(-n2²
ni 2(122 - 11- 1) 229
12(
1+ ((122 1) 1,09
1 expp(
11.2t (2(112 1) 1) + x
Since n2
0.9+ > -19 then n = =o(n2 ((2) and therefore for n2 big enough the exponent is smaller than 6.
Claim C.S. 3riby E Zso such that
Vnn > niby p(nw > Mminl |V| = D3 A n2
p.
> ii A i [m - nl² m + ng²), D3) 2 6.
Proof. For abbreviatioo mark event B as B = IV = D3Anz 0.9 > n Am E [m-n m
Mark the Laplace noise used step as and the Laplace noise used step 15 as 12.
P(nw > Mminn B, Dz)
P(n1
log
+12 > Mmin BB Dz) >
20
1
1
1
1
P(n1
log
log amin B, P()
log 8
)
20
6
1
1
1
P(n1
log
l2
> Mmin Ale log -
B3)
28
2
1
1
8
P(n1
log
log 5 Amin Da)
7)
26
8
P(n1
log
log
Amin B, Dz)
26
2
1
1
1
P(n1
log
log
Tmmin 11 < log
B, P(14
< log B Dz)+
20
E
E
1
1
P(n1
log
log
Ammi Ah 2 log
B, Dz)
-
20
6
2
1
1
8 2
P(m1
log
log > Mmin
log
B, D3)
log
B, Dz)
28
E
e
2
1
1
P(m1
log
log Mmin
log
B, Dz) -
28
8²
From B holds that |m - m < 02 and therefore mn < m + ng² and for the case of 1 < 1 log }
it holds that n2 < n2
- log
1 + _ log < <n + _ log J. Therefore mn < m + (ni + log )
25
62
As Amin = Omaxx (ma,, mi] }) then for the case of 4 < log &/ and B, holds that Nmin
22
}} Omaxx(n, 203 52 ,n o(m). therefore Ampb, such that Vna >
O(max{(n + p2 _n"
14bb Ti 2 log 25
log h Amin. Consequently, Vn, nub P(n 2 log 1 log 1
24
Mmin (11 < 1 log 3, B, Da)
Definition 4. A randomized function f(X,y) x x Rd + R, is (c, didifferrent private with respect to X if C IR, and VX, & x : || X|| < 1, eg. 333 holds.
P(J(X,)) v) E S) < ( v) SS)+
(33)
24

---

Claim C.6. Calculating nn, n2 is (2e, 0) differentially private.
Proof. Since ny differ by up 1 for neighbouring databases, calculating ii is protected via the Laplace mechanism. Since for a given ño the value [V] can change by up to for two neighbouring databases then calculating n2 is (e, 0) by the Laplace mechanism. Consequently from sequential composition theorem the sequential composition is (2e, 0) differentially private.
Claim C.7. P(nz I [VIID, -1-6 - 8.
Proof. Mark ~ Lap(?))
1
P(n2 $ DV ú1) = P([VI
log
1 S [VI|D, (1)
26
1
log 26 1 - 6
P(I < log
D m1) =
exp(
20
Claim C.8. Calculating mn is (c, differentially private with respect to D for given #1, n2 and n2 < [V.
Proof. Mark by D neighbouring database to D. and V as induced by this database. If V V then the claim follows trivially. case the V's differ, assume w.l.o.g that [V] 2 [V], and that V = IV| then they differ in their last sample. Define q = /e Ziys. =
Σ (VVeeeVVV 27.
9 g+ 1
q QVv
+ कंvl
x z
g8%v
+ z
+ - - - 2111112 5
(2 + ++2 29vv)
q
Ai -
+ i 11
200 + +
20
1/
ni
+
)
(2 x2)²
(2 2/)²
2 = Fz
(2 + 277)²
nf11 (
2
+
1
2x
Rift
2(n2 1) 1) + x
||
VI([
1)
n2
(2 - 1)z$
n2 - 1)xt
therefore by the Laplace mechanism calculating mn is (e, differentially private.
Claim C.9. Steps 6- 13 are (3c, 8) differentially private.
25

---

Proof. Mark D as neighbouring database,
P(in E (S
P(m E S)D, in = n1 "2 = 01, r2
-2 D)2r
J
{
P(m E S|D, f1 = -,, = = 02 = -
p(m E S = n,, =
=,
S
[
P(m E S|D, nn = =r,, = r2)p(11 = ,
= = -2g + S
P E S)D, in -. = r2)p( r1, r2 = 0 S
1,, n2 = r + == P(m S in n2 r2)pp rı,
2² P(m E D) +
where inequality follows claim C.7 and inequality ** follows claims C.8
and C.6
Claim C.10. Steps 14-19 are () differentially private with respect to D for [W] < Rmin and given 022 m.
Proof. Mark ~ Lap(?), and D neighbouring database. Eq. 34 proves the claim.
D, |W| < Dymin: m. n22)
P(S n [D W| < Pemin; mit, 112)
P(S n (neull]|D | < Tomnn mi, 112) S
(34)
e e n {mult)| |W| < Remin m. n2) + 5 <
P d, m, n22) +
where first inequality is true from eq. 35 and the Laplace mechanism for nw.
P(null) D. [W| Amin m, 122)
1
1
P(aw < Domin + log(
|D,[W| < Pemin: m, n22 2
25
(35)
P(1 < log(
) 2 1-6
28
Claim C.11. Step 19 is (e, differentially private with respect D for [W] 2 Mmin and given 72, m.
Proof. For a given 722, m and a neighbouring database, the group W can change by up to one sample. Mark n |W| and m.. From eq. 36 it follows that W E D. as defined in eq.
12
(36)
n
n
82
As W E D. n 2 R41, and n 2 n42, the problem of sampling from W) for [W] 2 nmin holds the constraints of claim D.29 Therefore sample from W)) is (c,8) differentially private. I
26

---

Claim C.12. Steps 14-18 are (c,0) differentially private with respect to D for [W] mmin and given m, n2.
Proof. Only data released is nw, and since the sensitivity of [W] given m, ng is 1, then the Laplace mechanism ensures (c, 0) differential privacy.
Corollary C.2. Steps 14-19 are (2e, 6) differentially private with respect to D for [W] > Temin and given mh 12.
Corollary C.3. Steps 14-19 are (2e, 6) differentially private with respect to D given m. n2.
D AUXILIARY CLAIMS
This subsection contains simple claims used to simplify the reading of the proofs. Claims described in this subsection uses the marking defined in eq.
Claim D.1. PI-x-
nea
a+naj 9
Proof Claim
D.1
ncr3. 3 ar + nx a + n
0 A
nCC h.
ncx
1 - (1 / (cx + 11 2 )2))
Claim D.2. p 1--2"11 + pd
nea 3 atno;
(1 \n).
Proof Claim D.2
1 1- 1 1-X + p\=11 pl
1- \"11 A"
pl 1-X"
H 3
a nor (1 - An)
1-
1 1
where the last equality holds from Claim D.I
Claim D.3. p( -(-=>"-) + px--1=
nen a+no
+1)
Proof Claim D.3
1n-1
1 - A
1 n- pl
- 21
11
p(
+ pA p\- pl
p
1-
p(
1
A"(
1
x + 1) -)
nexR.1 3
(1
X2 3
( x-1
1)
1
1-X
nzt
where the last equality holds from Claim D.I
Claim D.4.
+
ga.
Proof Claim D.4
1
A
+
3
\ -
- (1 7 (a + nx 3))
+
3
(1
1
(a
1
2 B))
4
4
4
2
4
!
a
+
nx 3- - (a+ + nx²B)]
3
2
422
Claim D.5.
(1 - (1- -1m-1) - (1 -
4 1)==
1ー-1 1 31
42 a - (² + M(m 1) (1 1n 12)
27

---

Proof Claim D.S
1 -11-(21h--)) -- 3
X
3
1
x-1
1) + 1 (AA
1-=1 j
+
4
1
3
1-11
x x
1) +
1 1-1
(-
x
+ {
4
4
4
(
3
1) + A 11 (1-11- + 9 1²11 )1=-11)
3
X"
+
3
1) 1 (1-1
3 4 - 1²1 - )--1i)) =
4
A" 1/3
k( 11 (1*(1 1- ( ( + 3
1x - (--))) =
24
4
X"-1 1
+ A
(kn 1) (1* - 1-1 (1
31
42
1²11 - (--11))=
24
A 1n-173 13
\²1=-1 31
42 a + 2 (( 1) (2 ( 12 1²1 -))-
24
An11 3n
a11 -(* + 2m (1+ - -1 - )m-11)
42
where equality holds from claim D.4
n- x1 = A(1 - ) Claim D.6. A EΣ 10 E
neug B atnaz
Proof Claim D.6
n-2 p
1 Ahn
=' x ncx 3
p 1
>
x
Σ 1=0
X
pd
(1 - )bm)
1-x
a + nx B
-==
i=0
Where equality * follows from claim
D.I
Claim D.7. A -
2 x =
11
atna (1 ^3 (3A-1 f)
ne 3
1-2--11
Proof Claim D.7
k
n-2
(n- 115 11 p+ p
X²| =
j=U
i=0
(A--1 A)*
x-1
1- 1\j* ner n
1 A- 1 a + no + -1
1
1 1= X
1- x
Where equality * follows from claims D.I D.3
Claim D.8.
x - X + 11 1) = (1 -
-
Proof Claim D.
_ 1 11t + 1i+ 3
2 x- + 2
x (1- - -1a-1) - | (1 x" ( X + 1)
1
3
x+ (1 - (1m-t) - | (1 1- (}+
3
42
(1 - ( {4+1) 1
42
where equality * holds from claim D.4
28

---

Claim D.9.
A(1 - (1-
- -- -- +2)==
(A --1((1 - 1)
- 1114(n111)] + A4(0-1((11
Proof Claim D.9
+ - +12))=
A(1 - \ (1 - X" 1"-11) 15) - 1(1 - (A" (1-)1)))) -
A- í 1²1(1
3
/) Ak 111 1/10 1s + A1
4 (---== + +
3
1
1
- 1 - 1²1(1
3 x
7)
11(1 1xt ) ((t2 + (1
33
4
A- í - A" 1((A - 44 4
1)) 1 (1 wyy ) - (4+1 + {++1 1
>- (331)
=
42
A- î - - 'i(1- 1"-1\(1 - () + 31
a)) )
(1 1) ( + 1 n-
3
[x]
42
42
(A () 1 1- \ 3
aa(1 1*) 1))] + 1 πp )x* x
42
Where equality follows from claim D.8 and equality follows from claim D.4
Claim D.10.
A(1 - Akm) - i 1 - 1s)*
1 1- \- 1 (1- 1t
( + 1)1
3
4
(A- 1)+ 1=11 12 (k26(1-12)]
+ xk(n
- 11t1)..
1- 1==1
Proof Claim D.10
A(1 - (tm) - i 1 (A- 1)*
1 -- 1 V X" 3 --1 1 [MM..d
(A 1)(1 11--1)= + \ 212 x (alnn))]] + Ak(n (1 21 11 - [
(1 - )1==1)
A" 1 a X(2b(n-1)3]
(1 (2-1) +
12
x
- 1
Claim D.11.
n a
(1 - 1+
A"
129a(1- S D1] + (p- p) > 0.
1=1--1
29

---

Proof Claim D.1l
(A -i+ A" 1n-133 [1za(1 - )()(()-1))]
(p -Ā)=
a + nx
1 - 1in-1
mcrg8
() - - 1--1 [1 - 1 (+)h(n-11)]
2 nnco - 1/²
a + no
1 1- 1A=-1
2
ncn
11
(a + nz²23 (1
7 (a + nz23))+
a + nx
2
2
A"
(3 [1 - {(1b(n-1))]
3 イ
ner
1 1 W
42
3
37 (m=²3) B) +
1--1 42 (*)
3
(= 12
+
a + no
2
42
ncrp
10-123a(11 - i (x))(111))]
33
31 nx23
+ncx
a atnrj n
- 11=-1
42
42 a + no?
nerg a 1
1 - (*))((=1))]
3 $111
nn2 3
+ +nco
a + no g) > 0
1-1--1
42
where the last inequality holds because A, i < 1 and a > 0
Claim D.12. 1 > x 2 1-1-111-- 2-2 2mm+)3m 1-x-
is true for k S 1 loga [1=
2n
Proof Claim D.12
> x 2 1 x- 2kn
x-1 - x x- < - x- -k2n
1 - 2-2
a1
x2
11
(1 - 1) > 1
26n 1 = 1+ 12 11
(x-2 - 1) 1 2kn
a
an
- (1 - X2)) = ks
1
k 2
log (1 +
loga
2n
[3)
2n
1+ 1 (1 - X2)
Claim D.13.
((x(m=11) > 17 Ei= X26 (822262221 is true for k S 2n
logx(
( 1t om (1 x3)
Proof Claim D.13 First note that the inequality can also be written as 1 1>1) 1) Ero 2
(AA (1)m=-)))-- k)
Secondly, the right hand term of the inequality could be upper bound as eq. 37 Therefore for the
claim's 's inequality to holds it is enough that - 2 n 111 2nk
which proved by claim D.12 to be 1-x-
true for ie < 2n loga( 1+ 2y )
30

---

Tr ()(--1))20-1
(d(n <a>s
==0
j=0
1
2
1))(-1))((k-1)
77
{2n(k-j)
j=0
(37)
nk-1
1
X2nn-nnj-il Franj+t 17
22
X
nk
17 - x 2-(kk+11))
22nk 2nk
11 -2
1-1-2
1- X
1=1
Claim D.14. (AA"-11)2k 2 1(Am=11)2k
E1z X is true for l S
2m loga ( It on (1-xa)
eq. 38 holds because X, Á < 1. By multiplying both sides with Ei= X get Then noticing that the right term equals the right term of claim D.13 and hence smaller than the left term of the claim, the claim is proved.
Proof Claim D.14
eq. [3]
(2x=-1224
<
(1x
(38)
==
k-1
1\Am-1132 122k
2
11
((rn-1) 2)
Σ 2
(39)
==0
1=0
1=0
Claim D.15. The inequality
(Ax--1)2 (
(
+
(
A-1
n-1
R-P
2
1=0
holds for 22 13 3,n
2as
3
# 3
Proof Claim D.15 Left hand side can be lower bounded according to eq. 40 while right hand side can be upper bounded according to eq.
41
Therefore it's enough show that
2 L 2km + n - > 1- T- which according to eq.
2kmn
42 is equivalent to showing that
(2nx 3 1)
+2(22 > O. Since
a claim D.19 applies and therefore
20z
ah + Consequently it's enough to show that (2nx - 1) 2(b+1)n +2(e . -11 > 0.
which is true for 2 > 3 by claim D.16
n-1 (11-1125
(Ax- 1- +
126
(11--1925
1
(40)
n-1
1 1- \ 2kn
2
2km
2jn
2 = 22n
1
2kn
1
X2
j=0
2=0
First inequality holds because and
1, and second inequality holds because À
X
31

---

1 - 2
x
11
2
1)
(41)
X
i=0
Inequality holds because À < 1 and r >
1
1- 22hn
> 1- 2
g 2k
+ 1 X2
1 X²
12 -12
+ 11/220 (1 - )2km)) > 17(1 - 2²n)
(1- 12) 1 1 12
13m + -n)(222
22(k+ -1 >
1
(a + 3) - 2²) - 2 + -((2) - 22(k+11n 11) 0
α
(42)
(a + nz - (1-
1
- (((k+])m + +2(2221 - 22(k-1)a 1)a 1) > 0
-
+ n
(2(a + na 1) 1 - + +2(22 1 2((++1)m - 1) >
α
212(k+1)m + (2nx2 g- - 1) 1 22(k++1y + 2(2 (2(K+1)a - 1) >
a
(2nx - 1 2((++))p + 2(2222 - -1)
Claim D.16. For x28 >> 3 the inequality (2e -3 1) > 0 holds.
Proof Claim D.16 It's easy to see that the inequality holds only if 23 2 In
-2
Since -2
< 3
claim proved.
U
Claim D.17. For as defined in lemma
A.4 and the conditions of claim D.19
1)
> x 21 1 2 +1)m 111m
h + (a + nx? +
1 - X-2
Proof Claim D.17
A 2[kk++)j
X 2(k+2))
21 1 loga( (
(1 (1-12) -1+2)n
1
X2_
1 1- X²
1 - X2
1nga(
1 1
(1)))
- -1
[1 1 (1 - {اi1 2n
17
= 1)
1 X2
1- X2
(1
2n 1
\ -2n -1
(X-2n 22 1)
77
an
+1
= - -2n
1 1 X²
1 1- X2
(a (x2 + 18
1 1
(
-1)
( 1)
a
a
(a +
nxa
2
3)
(a + nx 3) +
where the fourth equality holds from eq.
43 and the second inequality holds from D.19
17
- 1 "[1 (a nx
11(a + nx² 2) + (5 + n))
(43)
1
(a + nz2 + (a nx
(a n + !
32

---

Claim D.18.
1
3 n
Ak 0:
a + nx? B)2 - (a + 2)
Proof Claim D.18
A
(a + nx 3) (ax + nx
kc 21 i
a 2
(a + nx? B)2 (ar + n
1
(a+nx"p)z
a² + 2n a. + |nx23)= 0: nr
n
1 Where first inequality holds because À < X. Claim D.19. For the conditions of claim D.21
a + an + (nz² 3)2 0 n
(a + n (a + 12223)
2n 2 6 24z
+ nr
Proof Claim D.19
The proof is easily deduced from claims
D.20 and D.21
Claim D.20.
lim (1 n-000
2m c 3
+ nz23
In(1 ainar
Proof Lemma D.20
From eq. 44 it is enough to find lim,
In(1
Since limm-+00
otne2a
0 and both the numerator and denominator are differentiable
0.
around co, the use of L' L'Hôpital's ' rule possible as shown eq. 45 This proves the claim.
la(1
(1
2n
In o4nz4z) 20 2n In(1 otnuts)
(44)
+ nx2B
lim
dn
d
In(1
attna
lim
2 (a+nz233 3- ()a++
lim
2n
2
(45)
10000
d
2n
(nx² 8)2
x 2
Claim D.21.
d
1
Vn
(1
y2n < 0.
2ax2 B
x² dn
+ nxx
Proof claim
D.21 d
First, simplified term for the derivative is found eq. 46
1
d 2n Inf1
22
a
dn
a + 2x23
dn
x²8
(1 a + nx23
a nx23 2n In(11
2n
(ax + nx2
(46)
atnz28
1
2nxr
(1 a + nx²3
[2 a + nx²3
(ar + nr23 A lower bound for the In term can be found using Taylor's theorem shown in eq
1)(a + nx²B)
47 where
0 < S at
1
In(1 a + nx23
2 (11 E)² a a nx 3²
a + 2x
(47)
1 1
)2
+ 2x
2
nr23
33

---

From equations 46 and 47 it is enough to find the terms for which (a+nz=g (a aature + (a+tn="3)> holds. A simplified version of this inequality is found at 488) and it can be easily seen that for > 2 n + 1) n 3 z
no²3
this inequality holds.
nx?
1 1
(a + nx? 3 - (a + nx <
a + 2 + 2 (a + +n=
(48)
< 20 + 2nxx 3a 2a 2na² B + a + nx² B - =
0 < nx² (2a - 1) + a2a - 1) -1
Claim D.22. For n
0 (e 2) + 2 and the conditions of claim D.19 k as defined in
lemma A.4 is positive.
Proof Claim
D.22
The claim's 's inequality is simplified eq. 49
i > 0
1
loga(
X2) - 1 > 0
2n
1+ an
loga(
) > 2n
1 1 (1 X2)
In
1+ ory (1-
> 2n
In
In(
< 2n In À
1+ [x)
(1 X2)
(49)
In
< In X
(1 X2)
1
< 2m
14
1
(1 - X2)
07)
1
A 2n <+
(1 X2)
01)
-
1
(1 X2)
am
By claim D.19
2
2n 11
< x 1, therefore it is enough to find terms for e 20 -1 11
X2),
at
which is done at eq. 50, which proves the claim.
1 x2) to. -1 O7)
an(e -1) < (1 - x2))
anle 3 1) < (1
71(0 (a + nx2,8))
"
(50)
a 1) < (a n²
(a na: 9)²
1
a 1) < (a n)
2
1
ale - 2) + 2
< no
a (e मे 22) +
< n
3
2x B
34

---

Claim D.23. For as defined in lemma A.4 and the conditions of lemma A.5
p(0 p(0(1k)+1)) > 1164++1pm D) S 201
243
(3252
(2))²
Proof claim D.23
p(0 (TK++1) > M(rk)+1mmlD) I
(A(1k)+11mm - P(r )
exp(-
)
2
(1k+1)n )2
a
3
2 )2)))-
exp(
-
201
32x 3
n
r=1
exp(
3
)2
())))
2v1
32x23
n
Where the first inequality holds due to lemma a,4 second inequality holds due to lemma A.5
Claim D.24. for n > + 10th u, B.
the inequality to (ax + (= + x²))) v x²t holds.
to (n- 1)) and vz > u( x22) Therefore a sufficient condition will be that t (n 1) > vxj. which is equivalent to n >
Proof Claim D.24 Notice that 1o (2) t
1
10v
B
Claim D.25. For the (o²)e as defined in eq.
14
(0 R
>0.
Proof Claim D.25
1-v
(o"); = vo² + (1 - v)02- a (
a (2+
(51)
v(a + +a+
(2 - 22.
(2+
(a+ (z $3)
Therefore, sufficient condition is that a + (z + 22)3 + v(22 - > 0. Since the condition of
Lemma 4.2 dictates
10 " then claim D.24 holds, which satisfy this condition.
Claim D.26. For the Bayesian linear regression problem domain D, and ô defined in eq.
14
In
< 2(n 1)x7
Proof Claim D.26
Consider
m
(n- (n=1)a?
422 x²
323- - 2
a + (z #2)8
h
(52)
1)
2 + x
(2 2
a (z + 2
Where eq. 52 holds trivially for fr < En. therefore it is assumed that 2n > In- From eq.
52 by
Taylor theorem and < Ç < c following inequality holds
e 1 - (a1) 1 >1+
a+
a +
Consequently, because the natural logarithm is monotonically increasing the following equation also holds
1 1 In a a 2,)3 a (z + xx.)3
c1
In 6
x Therefore In g < [m-1)ø]
35

---

Claim D.27. For the Bayesian linear regression problem domain D, the conditions of Lemma 4.2 and (a²) ā defined in eq.
14
1 (v 1) In
8²
V 2 2((n (1)
1
S
-0)
2
(o2)²
1 1)
va
Proof Claim D.27
consider C1 ((- -va
VJ
vBa7
C1 = (n 1)at V.r
2"
a+ (n 1)af vBar 2"
v.3(3 x
2
+ (2 + x²) 3- - vB22
+ (2 + x v xx 22)
a+ (2+
-1
(2 x2)3 + #B( 82)
1
(a+ (z + 2 ()) (= 22)3)
-
a+ (2 + 22)
at x23 v3(2 17)
0²
(a²)²
Where inequalities holds under assumption that n > >1+2 and last equality holds from eq. 51 Therefore, by using Taylor theorem and 0 S C following inequality holds
of
e (c) 1+ 2
e = 1 + +
(o²);
From this inequality, and because the natural logarithm is monotonically increasing In [o=t S et therefore (v In
6² S 51 1)c, _ ----1 pz
(1) 1-1((nn 1)27 v
(0
Claim D.28. For the Bayesian linear regression problem on domain D. the definitions of eq. 14 and the conditions of Lemma 4.2 the value v (μ-ū)² is bounded by 2 (m=)t
2vB(
I
20B(
(22,, x1,3) (c+ (c+n2))
+ /
(x + 2),
(c + n2
10
9
n
2m
10
9
(x)
22-21
10 6
3
n
Proof Claim D.28
First bound 1|2 - A1)
InHla
q + In
IA- A B1
a +2)))8
+ (2+
(g Fn (a (2+ 1) (q
(2+ x3)33)
(a+ + (2 (2
qig 3 + anllan + Fn.nn 3 xn.,, q an #nin 3 in
(2)))
$3 22
en - 22 - - knIn) + B 2n (n
9n
31
(2+ 12)
8
(a (3
+ 2 (,
28
36

---

Therefore,
(1 11)
(o²);
+ { a+ + v ann)
(
)-1
(a (0+1===2330004++))) (a+ (2+ +2,)3)
(a ( -))
10 (++ ( (1++)))))
32 2m ++ (5) + x1,3) + =m
0 (
(2x + (1+0) (
(
(1=++))))
(20
)
5na7
3,
3)
x B)m nT1)
32
V
(x) xx,3)² n2n
(nz})2 2
2
to
(1) ())) a B/
(c (c+
+ - ( + 2/,33
(c+n2y
2v
2
n 2:3
of
(1 B)2
22-21
10 2/8
n23
10
Inequality is true because Lemma 4.2 conditions dictates that n >> 1 +
z 10v
and according
to claim D.24 this promises that
10 (a (z x2)))
v( xn Inequality follows from
>> (n 1)21 = nzg.
Claim D.29. For the conditions and definitions of Lemma 4.3 one sample from the posterior 5) differentially private for the following terms on and v.
v= == 2ln(f)
e
8
+ (
n 2 max
+
1,
v
(1
2
160Bat
271
T0 G
16r3
(23
[c (
9
()}
in + 3)
4v
(
(c {
Proof Claim D.29 By Lemma 4.3 sample from the posterior is (c1 ln(2)
w-1 5) differentially
For each of the 6 terms of é1 + Im(?) w-1 a lower bound on n and is found at equations 53
private.
54
57 58 such that the sum of terms is upper bounded by e. These bounds match the claim's guarantee over n and v therefore proving the claim.
55
56
For term In( +
In
2
(53)
2
In
+
1/
6
37

---

For term
(a- 1
S
2(n 1)
16
(54)
n n214 1+
47 E
For term {u 1)
va
(n-
1)27 187-ve0 v.
1
11 1)
(n 1)x1 vV -
16Vx
(v 1)
- (n - 1)x2 - Vz
(55)
2
16vx
+v xx
2
(v (-11) 1)
2 1 +
( - 1)
= 1 + v
(1 + 8
2
Ex7
x
For term 2v non 2
J
20
5
9 n
271
16
S 71
122
(56)
10 I
16
32
4
2
h
c
For term 2v (4) (xx -+) (c-n"))
1o (ag f)2
(x 2v3(
() (17,3)
+ 11
(c+ (c+n2)))
10
3)
n1-71
16r3
(a (
+ o
n² "
(c (c
(57)
9
3)
10
1653
(e [e+ (
(2)3)2
(2+n71)² nd
For term
1
(1f a + 11,
(2+22))
2
1 63
n
10
( a + x
n
2
(C +c++171) 727
(58)
9 " 93
4v
(x
+ 2 1
(c + n ))
6 3
10
38

---

Claim D.30. For n2 ,n < <92 2 and the conditions and definitions of Lemma 4.3 one
sample from the posterior (e, () differentially private for following terms on n and v.
2 2lm(2)
+1
v #
(u )
n
2 max
1 +
(1 + 8
37
r7
16v
1ー
10 Ex7
9
16r3
(2)
+ +
)1
)) 2- 2ー
10 (x)
9
(1 + 10 u
of
4v
( a
+ ))
)1
}|
1 B
(1 + 10 24
provides general lower bounds for (c differential privacy. When c == n ,2 > 7, these bounds can be simplified.
Proof Claim D.30
Claim D.29
16r8 (o] ()) (c + ))²)))=m
For condition
(xf))²
16rB
(x + x11
( (() -
10 (x) 3)2
16v8
( + (x)
n 1 S
1
1o (x)
16rB
(2
(1+
(1 + 10 10 -
(273)2
where the inequality holds since Lemma 4.3 enough that
dictates that n + 10 c 8
Consequently it's
16v3 (x7,) + 27,3)
1
T
10 (275)2
(1
(1 + 10 zf
f)
of
Following same considerations for condition
>
du ( 4
(c + n )) it is enough that
n
4D
2 + 24,9)2
)1 +
)) مोm
(1 + 10
2
2
E WASSERSTEIN DISTANCE PROOF
Claim E.I. p. are distributions with 2-Wasserstein distance We(p.g) q) 2, then we have (z), S ((Br+e(x)) +
Proof. is the claim that dP. I dn from Gibbs & Su 2002). Picking optimal coupling and using Markov inequality we get P(d(x, y) <) d
As {(i v) I (x))) C ( 7)
ÿ E (,- ((5,)) Ø) d(ā 7) > c} we ge, S (Br+c())) + e (special case of Strassen theorem).
39

---

Claim E.2. Let p.q be continuous distributions on R with Wasserstein distance W2(p. è,, and let ps.qs be their convolutions with uniform distribution on (s( We assume both density functions are L-Lipshitz continuous. For X > we have
Px(x) vola() c)) 92 (2) + vola(A 6) +2 vola(A)
vold(A)
1) AL.
(59)
vola(A- c))
Proof. We have ((Bx(x)) = P(Bx-. + P(A(x;A-E,M)) where A(2; M(z r2) ) is the annulus around x between radius 11 and 72. From continuity there exists E P(Bx(z)) such that p(z) = (x),
where vola(r) is the volume of a ball of radius in Rd From Lipshitz continuity we have vola(A)
P(A(2; À c,) & (Vold(A) - vola(A - <p)()(z) + 2XL) (1 (1-
vola(d-s) ) P(Bx(x)) + A, vola(A)
where (vola(A) vola(A e))2AL. From this, we get
vola(A- P(Bx(a)) A vola(A)
((B)-c(1)) N
(60)
Combining this with claim E.1 get
(A)
vola(A)
P(Bx(x)) S vola(A -) (P(B)-((z) + 5
vola(A (Q(B)())++A+))
+A+c)
(61)
We divide by vola(A) to get the densities Px,
vAla(A) px(x)= vola() - (x(x) +
A+E vola(d - c)
(62)
40


Reviews:
[{"review_id": "xWiOFZbWGco", "reviewer": "Reviewer_gB6E", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "1. The counterexample constructed is fairly restrictive. It is for a particular model, for a particular data set, for a particular stochastic scheme (i.e., cyclic-SGLD) and for a particular learning rate. Does the same result hold if we use the common sample in each step of the SGLD? So I doubt that this example provides general insights.\n2. According to the proofs in the appendix, k in Lemma 4.5 is fairly small. In other words, the privacy breach can occur when the SGLD has only scanned the full data set a very small number of times (less than 10 epochs, as shown in Figure 1). Thus, even for this particular counterexample, I don't think the result is practically meaningful.\n3. Section 5 is really an incomplete analysis. ", "summary_of_the_paper": "This paper provides one concrete example, showing that revealing one posterior sample generated by SGLD has the risk of a privacy breach when the SLGD sampling iterations number is moderate, while the exact posterior sampling has little risk of a privacy breach.", "summary_of_the_review": "Overall, I consider the contribution of the paper is quite restrictive. \n\nBy definition, it is sufficient to find a pair of neighboring data sets to counterprove the loss of privacy. But the results also depend on the specific setup of the SGLD algorithm, which I believe is not very proper.\n\nIn the common privacy-preservation algorithm, one typically injects Laplace or Gaussian noise. To show it works, we always need to have some lower bound of noise variance. Similarly, if SGLD preserves privacy, there are potentially some requirements on the algorithm implementation. To counter-prove that, I suppose one needs to show that no matter how one tunes the SGLD algorithm, the privacy breath is inevitable.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jPvOkjaGSHT", "reviewer": "Reviewer_1F53", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Strengths:\n1, It is interesting to know that SGLD can result in unbounded privacy loss during the middle of the sampling procedure. \n2, Figure 1 clearly illustrates the main idea of the claiming point.\n\nWeaknesses:\n1, Theoretical results in this paper are based on Bayesian simple linear regression problems as shown in Eq(4) page 3.\nHowever,  the paper mentions Bayesian neural networks in several misleading places. For example: in the abstract, \"This interim region is essential, especially for Bayesian neural networks, as it is hard to guarantee convergence to the posterior\" or in introduction \"Neither of these cases is suitable for deep learning and many other problems, as one would limit the model’s accuracy and the other is unattainable in a reasonable time\" in page 1. The authors should make it clear about their contributions. So readers can position this paper appropriately. \n\n2, Subsections 4.1 - 4.2 are proof sketches to show that approximate sampling of the posterior with Bayesian linear regression by SGLD is not differential private in some steps (Theorem 1).  It is better to put them into a new section and explicitly state their relation with Theorem 1. \n\n3， Section 4.3 tries to remove unknown c in eq 5. However, $p(\\theta | W)$ is not the original posterior $p(\\theta | D)$ based on dataset $D$ anymore.  What's the relationship between $p(\\theta | W)$ and $p(\\theta | D)$?\n\n4,  The manuscript is not ready and needs to be further proofread. For example, comma and period are missing in many places:\n\"In this section, we will consider the differential privacy guarantees provided by taking one sample from the posterior for the Bayesian linear regression problem on domain D\". Similarly, Theorem 1, Lemma 4.1  4.4 and 4.5\nIt also should be \"steps\" in \"but there will be some step in which SGLD will result in unbounded loss of privacy.\"", "summary_of_the_paper": "The paper studies the differential privacy of stochastic gradient Langevin dynamics(SGLD) as MCMC method. The paper shows that approximate sampling using SGLD may result in an unbounded privacy loss in the middle regime, via Bayesian linear regression. ", "summary_of_the_review": "The paper explores the privacy-preserving performance of SGLD and shows its privacy loss can be unbounded in the middle regime of sampling. The finding is interesting and useful. \nHowever, the authors should make their contributions clearly and some sentences are misleading. The paper should also be re-organized and proofread before it can be accepted. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "MwmrwQErgEC", "reviewer": "Reviewer_48Es", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Overall, this paper presents a rigorous analysis of differential privacy of Bayesian learning using SGLD. It uses Bayesian linear regression as a simple example to demonstrate that while differential privacy holds at the beginning of the SGLD updates and similarly at the convergence, but it may not hold during the intermediate steps of SGLD updates. Both the theoretical analysis and the empirical graph in Figure 1 backs their claim.\n\nThe paper is mainly a theoretical paper and seems to appropriately analyse the differential privacy of SGLD. The claims seems accurate although I could not verify the details of all the proof as it is fairly long.\n\nHaving said that, the paper can be significantly improved in its writing. At many places, it assumes a lot of background from the reader and uses terms without providing required explanations. For example, On Page 2, when discussing Ma et al. (2019), it mentions about  \\epsilon-mixing time bound without providing any clear context or explanation. \n\nAlso, as per my understanding, there are a couple of statements which seem incorrect: On page 2, when starting to discuss differential privacy, it says “…, a differentially private\nalgorithm promises the data owners that their *utility* will not change, with high probability, by adding their data to the algorithm’s database.” I do not think differential privacy makes any claim on utility.\n\nTheorem 1, which is a key result of this paper uses three notations: \\epsilon, \\epsilon’, \\epsilon’’. The role of \\epsilon and \\epsilon’ does not seem clear. It appears there is an error. Are \\epsilon and \\epsilon’ same?\n\nOn page 4, the parameters n; c; xl; xh; gamma_1 etc are not explained properly.\n\nThe Figure 1 is referred as Figure 4 – should be corrected.\n\nOn page 7, the sentence “It then estimates the average slope and throws away the outliers that deviate too much from the average slope.” It is not clear what authors mean by “slope” here?\n\nSpelling errors:\n-On page 4: “known” should be “know”\n-On page 4: “a well known results” should be “well known results”!\n-On page 6: “peeked” should be “peaked”\n-At many places in the text, “i’th”, “j’th” etc use the math symbols without Latex mode.\n-A lot of places, full stop is missing (both in text and in Lemma statements).\n", "summary_of_the_paper": "This paper studies the privacy guarantee of Bayesian learning using Stochastic Gradient Langevin Dynamics (SGLD). Since the SGLD updates are stochastic, it is often thought the solution can be suitable for privacy-preserving of the data that is used to train the algorithm. Using a counter-example, this paper shows that it is not necessarily correct to assume so.", "summary_of_the_review": "This paper analyses the differential privacy of the SGLD algorithm. It uses Bayesian linear regression as an example to demonstrate that while differential privacy holds at the beginning of the SGLD updates and similarly at the convergence, but it may not hold during the intermediate steps of SGLD updates. The results seem convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KtqPFJSAB9P", "reviewer": "Reviewer_AyXE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This work is quite interesting and important in the sense that SGLD is used in many works in literature and it is before proved that SGLD with specific parameter choices provides (\\epsilon, \\delta)-DP. This paper finds a counter example to the previous finding with correct analysis. However the structure of the paper can be improved. In the title and introduction, it is claimed that SGLD might not provide (\\epsilon, \\delta)-DP for deep learning. But the analysis are made for Bayesian linear regression. It is not clear to me that whether it is generalizable to (Bayesian) deep neural networks or not. \n\nOne weakness of this paper is the literature review. There are papers that uses SGLD for differentially private deep learning, it will be very useful to cite these works to understand whether these methods provide (\\epsilon, \\delta)-DP eventually or not. \n\nIt is confusing what is proposed in Section 5. It is mentioned that the bound scale poorly with dimension, but can still be useful for Bayesian sampling in low-dimensional problems. Is the method still proposed for (\\epsilon, \\delta)-DP for deep networks as an alternative? ", "summary_of_the_paper": "This paper shows that even when the posterior is as private as targeted in the beginning, sampling from posterior with SGLS might not be as private as targeted. The authors prove the theorem on Bayesian linear regression problem. They prove that for n big enough sampling from the posterior is (\\epsilon, \\delta) differentially private (DP), but there is a step in which releasing a sample will not be (\\epsilon^\\prime, \\delta)-DP for \\epsilon^\\prime=\\omega(n \\epsilon).", "summary_of_the_review": "It is important to show SGLD might not always give (\\epsilon, \\delta) differential privacy guarantee. But the text should be improved to clarify the points that I mentioned above. Maybe the title and the introduction should be revised, or some analysis could be added to show this is also applicable to deep learning.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows that SLGD can be non-private (in the sense of differential privacy) even when a single step satisfies DP and also when sampling from the true posterior distribution is DP. I believe that it is useful to understand the behavior of SLGD in the intermediate regime. At the same time the primary question is whether SLGD is DP when the parameters are chosen so as to achieve some meaningful approximation guarantees after some fixed number of steps T and the algorithm achieves them while satisfying DP (but at the same does not satisfy DP for some number of step T' >T). Otherwise the setting is somewhat artificial and I find the result to be less interesting and surprising. So while I think the overall direction of this work is interesting I believe it needs to be strengthened to be sufficiently compelling.
Decision: Reject