Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a theoretical framework for analyzing the privacy loss of Noisy Gradient Descent during its execution. Using the Renyi divergence as the differential privacy metric, the authors aims to understand how much information leaks for an optimization function
$\frac{1}{n} \sum_{x\in \mathcal{D}} \ell (\theta; \mathbf{x})  $ and for  the dataset $\mathcal{D}=(\mathbf{x}_1,\cdots,\mathbf{x}_n).$

In order to do that, they interpolate the discrete algorithmic method of "Noisy Gradient Descent" to its stochastic continuous analogue, the famous stochastic differential equation of Focker-Plank Equation. The authors carefully construct this tracing diffusion process among two consecutive steps such that $\theta_k = \Theta_{t=\eta k}$ but $\lim_{t\to \eta (k+1)} = \Theta_{t=\eta(k+1)}$ , where $\theta_k, \Theta_{t=\eta k}$ are the  discrete/continuous parameters for the optimization. This semi-continuous interpolation permits the authors to analyze tightly the information disclosure of the initial method of Noisy Gradient Descent using Gaussian perturbation for the case of 
of smooth and strongly convex loss functions.
main_review: Originality & Quality:

The way that I review this paper is more like studying a "positional" paper that aims to introduce a novel framework for the analysis of iterative algorithms. Actually, with the way it is written, I found it closer to an Adaptive Data Analysis paper, where we want to find the minimum bits of information that we are able to disclose to the users without violating the Renyi-DP guarrantee for Noisy-GD.
While I have written papers in (Noisy) Gradient-Descent Optimization, Langevin Dynamics and Statistical Differential Privacy, I have never
been exposed in this corner of the literature. 

$[Q1]$ However, it seems strongly necessary for me to include a discussion about the technical differencies and the novel parts that authors bring with this submission in comparison with [21] ( (S.Vempala and A. Wibisono's work).

In any other case it seems that they improve quantitatively and qualitatively the private loss analysis for Noisy-GD, our main arsenal in private continuous function optimization. Thus the authors study an important problem and resolve it almost completely. The paper is mathematically rigorous and makes strong theoretical contributions.


Clarity:

Here there are my main objections with this submission. The paper is partially very well-written and partially disappointing.
For example until line 122 the flow guides the reader with good intuition behind the techniques used.
However, already there are some annoying typos, which are repeatitively present in the appendix too.

$[Q2]$ For example Eq (6). Did we lose a minus in front of $\nabla L_D$ based on Eq (5)?

$[Q3]$ Imagine the case of the mean reader who has not been exposed before in Wiener processes/Ito martingale processess.
            How did we derive the Equation between (7) and (8) line 127? 

In one spatial dimension ''x'', for an Itô process driven by the standard Wiener process $W_t$ and described by the (SDE): $dX_t = \mu(X_t, t) \,dt + \sigma(X_t, t) \,dW_t$ with drift velocity $\mu(X_t, t)$ and diffusion coefficient $D(X_t, t) = \sigma^2(X_t, t)/2$, the Fokker–Planck equation for the probability density $p(x, t)$ of the random variable $X_t$ is:

$\frac{\partial}{\partial t} p(x, t) = -\frac{\partial}{\partial x}\left[\mu(x, t) p(x, t)\right] + \frac{\partial^2}{\partial x^2}\left[D(x, t) p(x, t)\right].$
Now how did we derive the Eq  between (7) and (8)? Also what is happening with the sign "minus" in front of the gradient again?

$Comment$ Especially in the main text, and if it is possible also in the appendix, numbering all one-line equations only can help the readability of the paper. Physicists and Mathematicians of the previous century were seeking for this convinience. It is really a shame to waste it with no reason

In contrast, Lemma 1 and its proof was well-stated and written correspondingly.

Furthermore, while until section 3.1 the authors had tried to provide intuition for each step, Lemma (2) and the section 3.2 for the privacy erosion misses a lot to keep the discussion in high level.

$[Q4]$ Does the Rate of Renyi privacy loss equation belong to the novel parts of this submission? 
             Is it the first time that we derive such a rate for the Langevin diffusion?

Either in positive or negative answer, I believe that it would help again for the sake of readability to explain in a high level why we expect this kind of privacy erosion. 

$[Q5a]$ For example, is there any discrete analogue which corresponds to Eq (10) that would help the reader to understand the role of each term in this bound?

$[Q5b]$ Could you explain further the line 172? It seems that from Lemma 3, we can earn some intuition for the relation of $R_a$ and $I_a/E_a$? Could you examplify with numbers why  $I_a/E_a$ would grow monotinically with Renyi privacy loss?

Finally another important question is the tightness of the result.

$[Q6]$ On the one hand both upper and lower bound for Noisy-GD are exponential. However there is a gap in the exponent is that correct? Additionally, I did not achieve to understand the figure 1 and especially the baseline composition analysis. I would like to ask the authors to describe in details what this baseline analysis is trying to show as far as this Gap concerns.


In the appendix, I will admit that there was a significant effort to be polished and they cover a lot of background to make the paper self-contained. However there are some points that I would like a more rigorous explanation.

$[A1]$ For the Eq (40) and Eq (41) could you provide the exact statement and possibly the proof of them. Intuitively, I understand obviously the claims (in one dimension they are similar with $\int_{[0,\infty]}x^2 e^{-x}= \int_{[0,\infty]} e^{-x}$). Nevertheless, since these integration rules are used for more complex scenarios, it would be better to explain rigorously phrases like "the gradient decays sufficiently fast at infinity". Additionally, it would be better to present in a short lemma why these assumptions are satisfied in the current setting

$[A2]$ In line 535, in order to exchange the integration and derivative, we have to use some measure theory argument. Since there is no clarity about the quality of the function $(p_t/p_t^\prime)^{a-1}$, could you make this exchange a bit more rigorous?

$[A3]$ For the sake of readability, I would introduce a fact before the proof of lemma 5, to explain why Noisy-GD can be written as a convolution of a pushover distribution and the gaussian noise. 

$[A4]$ Finally in 714 (second equation) and 722 line, did you apply KKT conditions? If yes, that means that the constraint set does not include corners (can not be a simplex). Is that correct? I would like a more rigorous explanation about the optimality conditions of $\theta^*$ and the assumptions for the properties of $C$
 like they provide a proof of extension lemma adapted to their setting.


Significance:
In general, after re-reading twice the paper and its appendix, I can say certainly that this is a complete theory paper: It addresses a fundamental problem, analyzes a state-of-art algorithm, and tries to proves the algorithm's privacy behaviour optimally. It tries to describe a high-level technique for other kind of algorithms too which has an independent interest. This is the main reason that my score belongs to the positive side. I will wait the discussion and the response of the authors to my questions to re-examine again my perception for this submission

Some extra questions that I would like to ask the authors?

$[Q7 ]$ Are there other type of noises that your analysis could handle for free or with small amount of effort (like a uniform, any symmetric, log-concave distributions)?

$[Q8 ]$ Where in the proof was used crucially the smoothness and strong convexity of loss function?

$[ Q9 ]$ Multiple theoretical results prove that SGD generalizes better than GD. Is there any straightforward implication about the privacy erosion of the methods? Additionally, what would be the corresponding SDE for the case of SGD? I am asking that because in a significant amount of literature langevin diffusion is used as the continuous analogue of SGD and not GD.


limitations_and_societal_impact: I don't find any direct societal impact. All Differential Privacy & Adaptive Data Analysis results are $\textit{a-fortiori}$  important for their indirect implications to the society since they are either perscriptive by designing and analyzing new efficiently private algorithms or descriptive analyzing the behaviour and the differential privacy loss of existing algorithms. The mathematical limitations of the paper have been discussed in the main-review section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper analyze Differentially Private Gradient Descent (DPGD) for optimizing a function f, which perform gradient descent while adding Gaussian noise to the gradients. The authors consider when f is the sum of loss functions of users in a database, and we want to output a minimizer of f with approximate differential privacy. They analyze the privacy loss and error of DPGD by viewing it as an instance of Langevin Dynamics, which samples from the distribution p with pdf proportional to e^{-f(x)}. The main result of the paper is a bound on the Renyi divergences between two DPGD runs on adjacent databases. The main qualitative improvement of this bound is that the dependence on the number of iterations of DPGD, K, is something like (1-e^{-K}) when the loss functions f are strongly convex and smooth. That is, the divergence bound increases with K, but the asymptotic dependence on K is O(1). In comparison, many past bounds have a small polynomial dependence on K, since they effectively bound the divergence between the full chain of iterates produced by DPGD, rather than the final iterate. In particular, if we took K to be sufficiently large, this would enable sampling from a distribution very close to p with approximate DP. The authors show that indeed, this gets loss that has optimal dependence on dimension, epsilon, and the number of users n.
main_review: Overall, I am excited about the results in this paper. The a privacy-preserving Markov chain that has final privacy parameters independent of the number of iterations used is in some sense a "holy grail" of DP MCMC algorithms, and as the authors point out many composition-based analyses in the past are unable to achieve this. Using a Fokker-Planck equation to derive a rate of change for the Renyi divergence that decreases over a time is a very elegant way to get around composition-based analyses, and to my understanding while many analyses using similar ideas appear in the sampling literature, using this type of analysis for privacy is a novel technical contribution. As the authors mention in their submission comments, the requirement that the loss functions be strongly convex and smooth is an impractical requirement, and the use of GD instead of SGD is also somewhat impractical. However, for a theoretically focused paper I would not view these as strong limitations on the results in the paper. For stochastic gradient Langevin dynamics, the theoretical convergence rates even in weaker metrics like KL-divergence are very poorly understood, and most bounds (at least to my knowledge), especially in the non-convex setting, have large polynomial or even exponential dependence on the dimension and desired error. In addition, I'd view a work like this as a first step towards better analyses of SGD for non-convex loss functions in the future, rather than falling short of analyzing them. 

In addition, overall I felt that while the paper was technically involved, I was able to come out of reading the paper on the first pass with a good understanding of the overall framework of the authors' approach and what individual steps are needed for their main result. In terms of clarity, the only major comment I have is that it might be nice to state the past results more explicitly in the introduction to better facilitate a comparison with this paper's, but as is the authors do a good job drawing these comparisons in the text. There are also some number of typos in the text, but these can easily be fixed before the conference, and do not really affect the clarify of the result. Lastly, it might be nice to give an interesting example of a sum of loss functions that satisfy the desired assumptions to give some intuition behind the setting the assumptions place us in; it took some time for me to quickly rationalize why having finite total gradient sensitivity did not contradict strong convexity of the loss functions.

In summary, the paper uses a new analysis that cleanly avoids issues past analyses has to get a long-sought-after bound on the privacy loss of Langevin Dynamics, and is organized fairly well. For these reasons, I'd recommend accepting the paper.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates the information leakage of noisy gradient descent (GD) algorithms for smooth and strongly convex loss functions. The authors analyze the dynamics of (Renyi) privacy loss during training (over K iterations) when the internal state of the training algorithm is not observable. This leads to an upper bound on the rate of privacy loss of the released model by way of the Renyi divergence between a pair of distributions over model parameters learned on neighboring datasets. The bound turns out to be much better than that obtained using composition-based approaches.

main_review: The paper analyzes the privacy loss dynamics of a noisy version of GD where the iterates are perturbed by isotropic Gaussian noise. I found the paper well-written and the results coherently presented. Also the paper is of topical interest to the NeurIPS community, esp. in relation to differential privacy analysis of noisy versions of GD and its derivatives. 

For strongly convex and smooth loss functions, the authors show that noisy GD satisfies an isoperimetric assumption. This allows for a strong guarantee (Theorem 2 and Corollary 1) on the rate of privacy loss that converges exponentially in the number of iterations K. The authors also show that the bound is tight and enjoys a superior privacy-utility tradeoff compared to composition-based approaches. 

The assumption of strongly convex and smooth losses limits the practical applicability in deep learning and this has been acknowledged by the authors. 

limitations_and_societal_impact: Addressed by the authors. I do not foresee any potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the dynamics of privacy loss for noisy gradient descent algorithm, whose continuous-time analogue is the Langevin diffusion process. They obtain a tight bound on the Renyi divergence between the pair of probability distributions over parameters of models with neighboring datasets. They prove for smooth and strongly convex loss functions, the privacy loss converges exponentially in the number of iterations, instead of square root in the number of iterations as in composition-based analysis of the same algorithms in the literature. For Lipschitz, smooth and strongly convex loss functions, they prove optimal utility for differential policy algorithms with a small gradient complexity.  
main_review: The paper is well-written, and to the best of my knowledge the results are new. However, I have the following concerns.

(1) The paper is restricted to strongly-convex and smooth loss function, which is not true in general for deep learning applications. I'm wondering whether it will be possible to relax such assumptions. For example, in the literature of Langevin algorithms in the context of sampling and non-convex optimizations, there are studies about convergence results when the target is non-convex; see e.g. Raginsky et al. Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis COLT 2017. There are also many more recent references. 

(2) Noisy gradient algorithm is a bit restrictive. If you use SGD, the corresponding continuous time SDE is so-called stochastic modified equation in the literature, but I understand that your analysis would fail. Maybe you should mention in the paper the limitations of noisy gradient algorithm.

(3) I find some notations and math presentations a bit sloppy throughout the paper. For example, in Definition 2.1 and Definition 2.2., you wrote that for a pair of distribution p, p', but then what is p(\theta)? Is it the distribution of the probability density function? It seems to me you don't differentiate distribution and probability density function. If you use distribution, then you need to use Radon-Nikodymn derivative for instance. Same thing happens when you talk about conditional distribution in the appendix. 

(4) In the appendix, I saw you assume the loss function is B-bounded. That's quite restrictive. Somehow I didn't see that mentioned in the main paper. Where do you need to use this?

(5) In the paragraph after Lemma 3, you used the terminology PDE, but in (12), you have an inequality instead of an equality.

(6) In the sentence after (7), write "(k+1)th step" instead.

(7) In section 6, it should be "an exponential rate".

(8) In reference [7], there shouldn't be "et al." Also, you need to capitalize some words in the references. For example, langevin should be Langevin in [7], [10], [19] etc. 
limitations_and_societal_impact: The authors have stated social impact at the end of Section 1 and the limitations in the conclusion section at the end of the paper.
review_title: null

Meta-review: There were a lot of productive discussion after the initial reviews. All reviewers are happy with the results in the paper and find the paper an excellent contribution to the problem of differentially private learning. 

In particular, instead of the standard approach which shows privacy loss composes over multiple rounds, this paper provides a highly interesting new analysis that shows the Renyi-DP function (up to some order of \alpha) converges exponentially to some fixed value so that more rounds do not introduce additional privacy loss if we only release the last iterate. While the results apply to only the cases when we make some of the nicest assumptions (e.g., strong convexity + strong smoothness), it is the first result of its kind and is significantly stronger comparing to existing attempts to address this niche problem, i.e., privacy amplification by iterations.

Overall I think it's a good paper with original ideas that many readers will pick up.

Decision: Accept (Spotlight)