Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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).
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. 

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

It 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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.
2. 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.
3. Section 5 is really an incomplete analysis. 
summary_of_the_review: Overall, I consider the contribution of the paper is quite restrictive. 

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

In 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

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

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

Also, 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
algorithm 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.

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

On page 4, the parameters n; c; xl; xh; gamma_1 etc are not explained properly.

The Figure 1 is referred as Figure 4 – should be corrected.

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

Spelling errors:
-On page 4: “known” should be “know”
-On page 4: “a well known results” should be “well known results”!
-On page 6: “peeked” should be “peaked”
-At many places in the text, “i’th”, “j’th” etc use the math symbols without Latex mode.
-A lot of places, full stop is missing (both in text and in Lemma statements).

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 
main_review: Strengths:
1, It is interesting to know that SGLD can result in unbounded privacy loss during the middle of the sampling procedure. 
2, Figure 1 clearly illustrates the main idea of the claiming point.

Weaknesses:
1, Theoretical results in this paper are based on Bayesian simple linear regression problems as shown in Eq(4) page 3.
However,  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. 

2, 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. 

3， 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)$?

4,  The manuscript is not ready and needs to be further proofread. For example, comma and period are missing in many places:
"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
It also should be "steps" in "but there will be some step in which SGLD will result in unbounded loss of privacy."
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. 
However, 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.
review_title: null

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