Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
Authors: Rishav Chourasia
Jiayuan Ye
Reza Shokri
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Differential Privacy
Noisy Gradient Descent

Abstract: What is the information leakage of an iterative randomized learning algorithm about its training data, when the internal state of the algorithm is \emph{private}? How much is the contribution of each specific training epoch to the information leakage through the released model? We study this problem for noisy gradient descent algorithms, and model the \emph{dynamics} of R\'enyi differential privacy loss throughout the training process.  Our analysis traces a provably \emph{tight} bound on the R\'enyi divergence between the pair of probability distributions over parameters of models trained on neighboring datasets.  We prove that the privacy loss converges exponentially fast, for smooth and strongly convex loss functions, which is a significant improvement over composition theorems (which over-estimate the privacy loss by upper-bounding its total value over all intermediate gradient computations). For Lipschitz, smooth, and strongly convex loss functions, we prove optimal utility with a small gradient complexity for noisy gradient descent algorithms.

Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
Rishav Chourasia", Jiayuan Ye', Reza Shokri Department of Computer Science, National University of Singapore (rishav1, jiayuan, reza) mus. edu. sg
Abstract
What is the information leakage of an iterative randomized learning algorithm about its training data, when the internal state of the algorithm is private? How much is the contribution of each specific training epoch the information leakage through the released model? We study this problem for noisy gradient descent algorithms, and model the dynamics of Rényi differential privacy loss throughout the training process. Our analysis traces provably light bound on the Rényi divergence between the pair of probability distributions over parameters models trained on neighboring datasets. We prove that the privacy loss converges expo- nentially fast, for smooth and strongly convex loss functions, which a significant improvement over composition theorems (which over-estimate the privacy loss by upper-bounding its total value over all intermediate gradient computations). For Lipschitz, smooth, and strongly convex loss functions, we prove optimal utility with a small gradient complexity for noisy gradient descent algorithms.
Introduction
Machine learning models leak significant amount of information about their training data, through their parameters and predictions [2] (5). Iterative randomized training algorithms can limit this
information leakage and bound the differential privacy loss of the learning process [3 [ 9 The
strength of this certified defense is determined by an upper bound on the (Rényi) divergence between the probability distributions of model parameters learned on any pair of neighboring datasets.
The general method compute the differential privacy bound for gradient perturbation- based learning algorithms is to view the process as a number of (identical) differential privacy mechanisms, and to compute the composition of their bounds. However, this over-estimates the privacy loss of the released model [3]19] and results in a loose differential privacy bound. This is because composition bounds also accounts for the leakage of all intermediate gradient updates, even though only the final model parameters are observable to adversary. Feldman et al. [8 address this issue for the privacy analysis of gradient computations over one single training epoch, for smooth and convex loss functions. However, in learning a model over multiple training epochs, such guarantee is quantitatively similar to composition bounds privacy amplification by sub-sampling [8] The open challenge, that we tackle in this paper, is to provide an analysis that can tightly bound the privacy loss of the released model after K training epochs, for any K.
We present a novel analysis for privacy dynamics of noisy gradient descent with smooth and strongly convex loss functions. We construct pair of continuous-tim Langevin diffusion (0 processes that trace the probability distributions over the model parameters of noisy GD. Subsequently, we derive differential inequalities bounding the rate of privacy loss (worst case Rényi divergence between the coupled stochastic processes associated with neighboring datasets) throughout the training process.
Equaa contribution. Alphabetical Order.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We then prove an exponentially-fat converging privacy bound for noisy GD: (simplified theorem) Under 1-strongly convex and 8-smooth loss function { x) with total gradient sensitivity 1, the noisy GD Algorithm| I with initial parameter vector fo (O, 2n T22) and step size rj 3
satisfies (a, Rényy DP with E = O ( - - where n is the size of the training set.
This guarantee shows that the privacy loss converges exponentially in the number of iterations K, instead of growing proportionally with K as in the composition- based analysis of the same algo- rithms. Our bound captures a strong privacy amplification due to the dynamics (and convergence) of differential privacy over the noisy gradient descent algorithm with private internal state.
We analyze the lightness of the bound, the utility of the randomized algorithm under the computed dif- ferential privacy bound, as well as its gradient complexity (number of required gradient computations). We prove the tightness guarantee for our bound by showing that there exist a loss function and neighboring datasets such that the divergence between corresponding model parameter distributions matches our privacy bound. For Lipschitz, smooth, and strongly convex loss functions, we prove that noisy GD achieves optimal utility under differential privacy with an error of order O ((,=z=) ), with a small gradient complexity of order (n log(n)). This improves over the prior utility results for noisy SGD algorithms [3) Our analysis results in a significantly smaller gradient complexity by a factor of n/ log(n)) and a slightly better utility by factor of polylog(n).
We anticipate that our work will have a positive societal impact, by paving the way for building accurate and privacy preserving machine learning systems for sensitive personal data.
Preliminaries on differential privacy
x,,) E x We refer to a dataset pair D, D' as neighboring if they differ in one data record. A measure is said to be absolutely continuous with respect another measure v' on same space (denoted as v < v') for all measurable set S, (SS) = O whenever v' v'(S) O.
Let X' be the data universe, and a dataset D contain n records from it: D (x1, (x1,X2, X2,
Definition 2.1 (177 Rényi differential privacy). Let a: > A randomized algorithm A: xm Bd satisfies (ax, Rénén Differential Privacy (RDP), for any two neighboring datasets D, D' E X", the a Rényi divergence Ra (A(D)IAA(D)) S E. For a pair of measures v. v/ over the same space with v < v', Ro (vilk') is defined as
( du dv
Ra (vlle)) a- log Ea (ull/), where Ea (ull)))
dv'
(1)
We refer to Ro (A(D)IIA(D") also as the Rényi privacy loss of algorithm A on datasets D, D', An RDP guarantee can be converted to (c, 5)-P guarantee [17] Proposition 5].
Definition 2.2 ((22 Rényi information). Let a > 1. For any two measures v,vl over Rd with
< v and corresponding probability density functions p. p', if pl0) is differentiable, the a-Rényi
v
Information of v with respect to v/ is
4 2²
p(0) (0))
p
V p(0)
La (vllv')
IE 0mu
E Omp'
a(0)a-2
(0)
See the Appendix B for comprehensive presentation of preliminaries.
3 Privacy analysis of noisy gradient descent
Let D (x1, (x1,X2,'.. x , xn) be a dataset of size n with records taken from a universe X. For a given machine learning algorithm, let ((0;x) X' x Rdd + R be a loss function of parameter vector 0 C on the data point x, where C is closed convex set (can be Rdd).
generic formulation of the optimization problem to learn the model parameters, in the form of empirical risk minimization (ERM) with the following objective, where (D()) is the empirical loss

---

of the model, with parameter vector 8, on dataset D.
0
arg min (D(
where CD(0)= = Σ (()xx)
DEC
XED
Releasing this optimization output (i.e., 8*) can leak information about the dataset D, hence violating data privacy. To mitigate this risk, there exist randomized algorithms to ensure that the (a-Rényi) privacy loss of the ERM algorithm is upper-bounded by s, i.e., the algorithm satisfies (a, RDD..
Algorithm ANoisy GD: Noisy Gradient Descent
Input: Dataset D (x1. X2, Xp), loss function ((0;x), x), closed convex set C C IR learning rate 7). noise variance o², initial parameter vector 8--
1: for k 0. 1.... K- 11 do
2: g(x: D) = - =1 V[(0g; x;)
3: 0&t1 = Iee (0k- " + (2NN(0,
4: Output 0k
In this paper. our objective is to analyze privacy loss of Noisy Gradient Descent (Algorithm D. which a randomized ERM algorithm. Let OR. 0% be the parameter vectors at the k'th iteration of Auisy-GD on neighboring datasets D and D', respectively. We denote by On and 6 the corresponding random variables that model 02 and 0g.- We abuse notation to also denote their probability distributions by Oygk and O In this paper, our objective privacy of this algorithm. More precisely, we focus on the following.
model and analyze the dynamics of differential
1. Compute RDP bound (i.e., the worst Rényi divergence R., (Ox [0'x) between the output distributions of two neighboring datasets) for Algorithm | and analyze its tightness.
2. Compute the contribution of each iteration to the privacy loss. As we go from step k to K in Algorithm 1 we investigate how the algorithm's 's privacy loss changes as it runs the
k'th iteration (computed as Ra (Onz 0, - R. (Ontk-)
In the end, we aim to provide RDP bound that is tight, thus facilitating optimal utility 3 We emphasize that our goal is to construct theoretical framework for analyzing privacy loss of releasing the output 0g of the algorithm, assuming private internal states (i.e., 0,, .0K-1).
3.1 Tracing diffusion for Noisy GD
To analyze the privacy loss of Noisy GD, which is a discrete-time stochastic process, we first interpolate each discrete update from 0g 0x+1 with piece-wise continuously differentiable diffusion process. Let D and D' be a pair of arbitrarily chosen neighboring datasets. Given step-size n and initial parameter vector du 6y the respective & 4'th discrete updates in Algorithm I on neighboring datasets D and D' are
(0t+) IIe( (0k)) + Z2no 0%1t 11,(%' (0))) + + Zz), with ZB ~ ~20,0
These two discrete jumps can be interpolated with two stochastic processes θ and O2 over time ri S S 1y(k + 1) respectively. At the start of each step, = 1,k, the random variables O, and O₂ model the distribution of the 02 and 02 in the noisy GD processes respectively. During time mp < ny(k + 1). we model the respective gradient updates on D and D' with the following stochastic processes.
[ ( On 17 1- (kk)) (t-
(2(0) + 2 n
(5)
0 0 17 (0)) TK) (t-n)h) (t-nk))U,(0)), 2(t 202ttnnko222 72
where the vectors Un (0) (O) + VLn sent the average and difference between gradients neighboring datasets D and D' respectively.
and (0) (VL VL (B)) repre-

---

At the end of step, i.e. at - 17kk + 1), we project Or and O onto convex set C, and obtain
3.) θ +1 -lle (- lim 6% (-n((++))
+ m(++1) le
lim (--((k-1)
(6)
By plugging S into 6 we compute that the projected random variable 1k and O' n(++1) have
the same distributions the parameters 0k+1 and 0/41 at k + 1t step of noisy GD respectively. Repeating the construction for k = 0,... K 1, we define two piece-wise continuous diffusion processes 122 and (0/) whose distributions at time t n/ are consistent with 8g and 0% in the noisy GD processes (4) for any k E {o..... K 1}.
Definition 3.1 (Coupled tracing diffusions). Let Oo 0 be two identically distributed random variables. We refer to the stochastic processes {0r) and ) that evolve along diffusion processes (5) in npl: <1< np(k + 1) and undergo projection steps (6) at the end of step L 17(k: 1), as coupled tracing diffusions for noisy GD on neighboring datasets D, D'D'
The Rényi divergence Ra (a, ||6 n reflects the Rényi privacy loss of Algorithm with K steps. Conditioned observing 0g and ; the processes (0t)nk-cten((-=) and (0% (kctkk<ctc0(++>> in (5) are Langevin diffusions along vector fields -U2(0x) and U2(0%) respectively, for duration 1). Therefore, conditioned on observing 0% and 8%. the diffusion processes in (5) have the following stochastic differential equations (SDEs) respectively.
d = (Ox())) + dWW do; = (2(0g) V 2o
where dWW, v dO, T.a) describe the Wiener processes Rd. Therefore, the conditional proba- bility density functions Peink (010;) and (0 follow the following Fokker-Planck equation. For brevity, we use Ptinx: (010s) and p'e nı (010)) to represent the conditional probability density function p(O,- = O)0,,k nk 0x) and p(O) f nk 0%) respectively.
Opeink (010k) 8+
V (Pain (010))U((0))) 0² o² (Prion(((0s)) (010)) A (010%)
0p Opline (0102)
dt
By taking expectations over probability density function Pn, or ply (8%) on both sides of (8) obtain the partial differential equation that models the evolution of (unconditioned) probability density function p. (0) and (0) in the coupled tracing diffusions.
Lemma 1. For coupled tracing diffusion processes (5) in time 1/k < 17(k 1), the equivalent Fokker-Planch equations are
(p.(0) (0) V (00)
V (1(0))((0))+<ppci
dt
where (0) = (0) = E
[U2(0x)]0) are time-dependent vector fields on Rdd and @xreppkle
U2( [Ln LD
(L)((()) (0)) is the difference between gradients neighboring datasets.
By this density evolution equation, we model the noisy gradient descent updates with coupled tracing diffusions. The tracing diffusion process is similar to Langevin diffusion. Therefore, we first study the privacy dynamics in coupled tracing (Langevin) diffusions.
3.2 Privacy erosion in tracing (Langevin) diffusion
The Rényi divergence (privacy loss) R. (e, (0)) between coupled tracing diffusion processes in- creases over time, as the vector fields V,, Vi underlying two processes are different. We refer to this phenomenon as privacy erosion. This increase is determined by the amount of change in the probability density functions for coupled tracing diffusions, characterized by the Fokker-Plane Planck equations
g for diffusions under different vector fields.
Using equation 9 we compute bound on the rate (partial derivative) of R. (0+|(0)) over time in the following lemma, to model privacy erosion between two different diffusion processes. We refer to coupled diffusioos respective diffusion processes under different vector fields V2 and V

---

Lemma 2 (Rate of Rényi privacy loss), Let Vi and V be two vector fields on I corresponding to pair of arbitrarily chosen neighboring datasets D and D' with max - ()) S S, all
BER4
t 2 O. Then, for corresponding coupled diffussios {0t) and {0)) under vector fields V1 and
Vi and noise variance d², the Rényi privacy loss rate at any 2 0 is upper bounded by
aR. (0:110)) Öt
1 a
Ta (0:
-1-
(10)
? 4o²
Ea (o,
where 7 > O is a tuning parameter that we can fix arbitrarily according to our need.
Although this lemma bounds the Rényi privacy loss rate, the term Ia (O:]l0) depends on unknown distributions ,, O¹ and is intractable to compute. Even with explicit expressions for distributions O2 0, the calculation would involve integration in Fd which is computationally prohibitive for large d. Note that, however, the ratio La/ Ea is always positive by definition. Therefore, the Rényi divergence (privacy loss) rate in (T0) is bounded by its first component (a constant) given any fixed a. Theorem 1 (Linear Rényi divergence bound). Let Vi and V; be two vector fields on R", with max [V((0) - (2 S S. all 2 O. Then, the coupled diffusions under vector fields Ve and 0ERd
Vi with noise variance o² for time T has a-Rényi divergence bounded by E S
When the vector fields are V = Vn and Vi = Ln', the coupled diffusions follow Langevin diffusion. By definition 1.10 of total gradient sensitivity, max VLD VLD I S.. There- BER
fore, this naive privacy analysis gives linear RDP guarantee for Langevin diffusion, which resembles the moment accountant analysis M. However, tighter bound of Rényi privacy loss is possible with finer control of the ratio La (e, Ea (0,))0,). which by definition depends on the likelihood ratio between θ and 0,, thus is connected with Rényi privacy loss itself. When this ratio grows, the Rényi privacy loss rate decreases, thus slowing down privacy loss accumulation, and leading to tighter privacy bound.
Controlling Rényi privacy loss rate under isoperimetry We control the I./ Ea term in lemma 2 by making an isoperimetric assumption known as log-Sobole inequality (2), described as follows. Definition 3.2 (112 Log-Sobole Inequality (c-LSI)). Distribution of a random variable θ on Rd satisfies logarithmic Sobolev inequality with parameter e >> L.e. is e-LSI, for all functions f in the function set Fe [f Rd -> R f f is continuous, and ((f < )o), we have
< 2 E V (e)
E[f(0) log f(0) El
(11)
LSI was introduced by Gross [12 as a necessary and sufficient condition for rapid convergence of a diffusion processes. Recently, Vempala and Wibisono (22) showed that this isoperimetry condition is sufficient for rapid convergence of Langevin diffusion in Rényi divergence. Under LSI, they provide the following useful lower bound on Ia/ E, for an arbitrary pair of distributions.
Lemma (122) c-LSI in terms of Rényi Divergence). Suppose Or, G E Rd are random variables such that the density ratio between distributions of Or and O2 lies in Feg. Then for any a 2 1, RRa (Oill0))
I a Ia (0,)(0))
Ra (0,1(()) + a(a- 1)
(12)
da
2c Ea (0,110))
if and only if distribution 02 satisfies c-LSI.
(l,eo.))) Note that dc is always positive, as R., (O.](0)) monotonically increases with a > 1
This lemma shows that La (e, [[O)) (0, grows monotonically with the Rényi privacy loss Ra (Q,l @[). By Lemma 2 this implies a throttling privacy loss rate as privacy loss accumu- lates. Ciies.Combiiing Lemma and Lemma we therefore model the dynamics for Rényi privacy loss under c-LSI with the following PDE, which describes the relation between privacy loss, its changes over time, and its change over Rényi parameter a. For brevity, let R(a, 1) represent R. (O.
aR(a,1) ()
1 aS?
@R(a, R(a,1) 1) +(a 1) da
2(1 211-7)02c
(13)
Øt
7 4
The initial privacy loss R(a, 0) = 0, as O, 06- The solution for this PDE increases with time t > 0, and models the erosion of Rényi privacy loss in coupled tracing diffusions O and O).
5

---

3.3 Privacy guarantee for Noisy GD
We now use the privacy dynamics (13) of coupled tracing diffusions to analyze the privacy dynamics for noisy GD. We first bound the difference between the underlying vector fields Vi and V for coupled tracing diffusions for noisy GD on neighboring datasets D and D'.
Lemma 4, Let [(6; x) be a loss function on closed convex set C, with a finite total gradient sensitivity Sg. Let (Grrez and (0/ be the coupled tracing diffusions for noisy GD on neighboring datasets D' E X", under loss E(O; x) and noise variance a². Then the difference between underlying vector fields Vi and Vi for coupled tracing diffusions is bounded by
Sq n
max
[Vv(0) - (2(0))22 S BER4
(14)
where V2( and (0) are time-dependent vector fields on IR", defined in Lemmal
7
We then substitute S, in PDE (13) with Sg/n, n, and compute the following PDE modelling Rényi privacy loss dynamics of tracing diffusion njk < t 17 + 1), under c-LSI condition.
aR(a, t) Ōt S r 2n 2(1 2)
a5?
R(a, t) + (a- @R(a,t)) t)
(15)
a
da
We solve this PDE under y 1/2 for each time piece, and combine multiple pieces by seeing projection as crivacy-preserving poot-proesssing step, We derive the RDP guarantee for the Noisy GD algorithm. Theorem 2 (RDP for noisy GD under c-LSI). Let (Oirizo and {6)])20 be the tracing diffusion for AN on neighboring datasets D and D', under noise variance O² and loss function E(0; x). Let E(0; x) be a loss function on closed convex set C C Rd, with a finite total gradient sensitivity S.. If for any neighboring datasets D and D', the corresponding coupled tracing diffusions O2 and O satisfy c-LSI throughout O I t S nK, then ANoisy GD satisfies (a,, e) Rényi Differential Privacy for
0.5 20 9
(1 - -e-e---oo )o
(16)
This theorem offers a strong converging privacy guarantee, on the condition that c-LSI is satisfied throughout the Noisy GD process, We then analyze the LSI constant e for given Noisy GD process.
Isoperimetry constants for noisy GD When the loss function is strongly convex and smooth, prove that tracing diffusion of noisy GD satisfies LSI. This is because the gradient descent update is Lipschitz under smooth loss, and the Gaussian noise preserves LSI, discussed in Appendix [D.3] Lemma 5 (LSI for noisy GD). If loss function E(0; x) is >-strongly convex and 3-smooth over closed convex set C, the step-size is 1 < 3. and initial distribution is O, ~ INN 2o La)), then the coupled tracing diffusion processes {0rh2a and {0: for noisy GD on any neighboring datasets D and D' satisfy c-LSI for any t with -
Using the LSI constant proved by this lemma, we immediately prove the following RDP bound for noisy GD on Lipschitz smooth strongly convex loss, as a corollary of Theorem 2
Corollary 1 (Privacy Guarantee for noisy GD). Let E(O; x) be X-strongly convex, and 3-smooth loss function on closed convex set C, with a finite total gradient sensitivity Sg, then the noisy gradient descent algorithm (Algorithm)) 1) with start parameter Oo (o, Ta),, and step-size 11 < }o. satisfies (a, E) Rényi Differential Privacy with
0.52 Xa2n² (1 e -xnK/22)
This privacy bound has quadratic dependence on the total gradient sensitivity Sy, which is upper bounded by S, S 2L for L-Lipschitz loss functions. The smoothness condition / restricts the step-size and ensures Lipschitz gradient mapping, thus facilitating LSI by Lemma 5 Figure [] demonstrates how this RDP guarantee for noisy GD converges with the number of iterations K. Through y-axis, we show the & guaranteed for noisy GD under various Rényi divergence orders c and strong convexity constant X. The RDP order a linearly scales the asymptotic guarantee, but does not affect the convergence rate of RDP guarantee. However, the strong convexity parameter positively affects the asymptotic guarantee as well as the convergence rate; the larger the strong convexity parameter À is, the stronger the asymptotic RDP guarantee and the faster the convergence.

---

-10-2
in (0, ---ény Differential Privacy
Composition
Our bound
30,
4
20,
2
0 10, À
10, À = 2
10, À =
100 200
300
400
500
K
Figure Rényi privacy loss of noisy GD over K iterations, quantified using our DP Dynamics Analysis. We show & in the (a,,)-RDD guarantee derived by Corollary [ (bold lines), and the Baseline composition analysis (dashed lines). We evaluate under the following setting: RDP order {10, 20, 30}; X-strongly convex loss function with À E {1, 2, 4]; 3-smooth loss function with = 4; finite fz-sensitivity Sg for total gradient with S, = 4; size of the data set n = 5000; step-size 77 0.02; noise standard deviation 0.02. The expressions for computing the privacy loss are: our as²
analysis: X.
(1 (1-ea ei-m/2n and Baseline composition-baset analysis (derived by moment a5² 1n n
accountant with details in Appendix B 5
4 Tightness analysis: lower bound on privacy loss of noisy GD
Differential privacy guarantees reflect a bound on privacy loss on an algorithm; thus, it is very crucial also have analysis of their tightness (i.e., how close they are the exact privacy loss). We prove that our RDP guarantee in Theorem i tight. To this end, we construct an instance of the HRM optimization problem, for which we show that the Rényi privacy loss of the noisy GD algorithm grows at an order matching our guarantee in Theorem 2
It is very challenging lower bound the the exact Rényi privacy loss R. (0k, (KK,) in general. This might require having an explicit expression for the probability distribution over the last-iterate parameters dg. Computing close-form expression is, however, feasible when the loss gradients are linear. This is due to the fact that, after a sequence of linear transformations and Gaussian noise additions, the parameters follow Gaussian distribution. Therefore, we construct such ERM objective, compute the exact privacy loss, and prove the following lower bound.
Theorem (Lower bound on RDP of ANoisy There exist two neighboring datasets D, D' E x", start parameter O. and a smooth loss function {(0; x) on unconstrained convex set C Rdd with a finite total gradient sensitivity Sg. such that for any step-size r < 1, noise variance x² > 0, and iteration K E N, the privacy loss of ANo on D, D' is lower-bounded by
as²
Ra (0 (xxx) 2
402n² (1-e-nk).
g
(17)
We prove this lower bound using the Ez-squared norm loss ERM objective: min Diml |0- x.
We assume bounded data domain s.t. the gradient has finite sensitivity. With start parameter On 04 the 14th step parameter 6& is distributed as Gaussian with mean f4 = 7px Ei=0( (1 77) and variance k- -
of
2nd n
(1 - in each dimension, where ā Σ x; is the empirical dataset mean.
We explicitly compute the privacy loss at any step K, which is lower bounded by 1o (1 - *K).
as?
asS Meanwhile, Corollary gives our RDP upper bound e = σमाे (1 - e ==nn) for this same ERM
objective. This upper bound matches the lower bound every step K. up to a small constant of 4.
Moreover, Theorem facilitates smaller RDP upper bound than Corollary T by bounding the LSI constant throughout Noisy GD exactly. For squared-norm loss function, Theorem 2 gives the
7

---

following tighter RDP upper- upper-bound for Noisy GD, because all intermediate Gaussian distributions satisfy c-LSI with c= -
2-7, as proved in Appendix
Corollary 2 (RDP guarantee of ANoisy-GD on l2- fo-m squared loss), For any two neighboring
datasets D, D' E X", start parameter lg. step-size n, noise variance d², and K E N, if the loss function is tz-norm squared loss E(O; x) = 2 10 - x x||2 on unconstrained convex set C = R2, with
finite total gradient sensitivity Sg. the privacy loss of ANoisy-GD on D, D' upper-bounded by
a.S
Ra (0nk|16/ S (2 o (1 =
9
(18)
This RDP guarantee converges fast to O
d' which matches the lower bound at every step K, up to constant of 2- ~ 2. This immediately shows tightness of our converging RDP guarantee throughout the training process, for converging noisy GD algorithm. A different approach is to completely ignore the dynamics of differential privacy, and instead analyze privacy only al the convergence time (or when the algorithm is near convergence). Wang et al. [25), Minami al.
[6 show that sampling from the Gibbs posterior distribution v=0) x e-LD())/a for bounded Lp satisfies differential privacy. However, sampling exactly from the Gibbs distribution is difficult [4] Thus, Minami et al. [16], Ganesh and Talwar [[]] extend the DP guarantees of Gibbs posterior distribution to gradient-descent based samplers such as Unadjusted Langevin Algorithm (ULA) that can sample from distributions arbitrarily close to Gibbs distribution after a sufficient number of iterations K with extremely small step-size y). Minami et al. (16) compute the distance to convergence in total variation, and Ganesh and Talwar [1I] improve the prior bound by measuring the distance in Rényi divergence (building on the rapid convergence results of Vempala and Wibisono (22)). The latter results in a better gradient complexity M(nd), which however still grows with model dimension d. In comparison, practice can be much larger than the dataset size n.
DP guarantees are unaffected by parameter dimension d, which in
In contrast, composition-based privacy bound grows linearly as training proceeds, shown in Figure [ When the number of iterations K is small, however, composition-based bound grows at the same rate with the lower bound, as discussed in Appendix [ Therefore, to conclude whether our RDP guarantee superior to composition-ban based bound, we need to understand the number of iterations noisy GD needs, to achieve optimal utility. We discuss this in the following section.
5 Utility analysis for noisy gradient descent
The randomness, required for satisfying differential privacy, can adversely affect the utility of the trained model. The standard way to measure the utility of randomized ERM algorithm (for example, ANoky.GD GD) is to quantify its worst case excess empirical risk, which is defined as
(lCD(0)- Lop())) DEX
max
(19)
where 0 the output the randomized algorithm ANoisy-GD GD on D, 0" is the solution to the standard (no privacy) ERM (3, and the expectation is computed over the randomness of the algorithm.
We provide the optimal excess empirical risk (utility) of noisy GD algorithm under (a, R'D-RDP constraint. The notion of optimality for utility is defined as the smallest upper-bound for excess empirical risk that can be guaranteed under (a.E')-Rl RDDP constraint by tuning the algorithm's 's hyper- parameters (such as the noise variance o² and the number of iterations K). We focus here on smooth and strongly convex loss functions with a finite total gradient sensitivity.
Lemma 6 (Excess empirical risk for smooth and strongly convex loss). For L-Lippshitz. X-strongly convex and 3-smooth loss function E(O; x) over a closed convex set C C Rd, step-size 11 S > 2zz., and
start parameter Ou [o, 20² La)). the excess empirical risk of Algorithm is bounded by
2312
-Ynk 23dda2 X2 X2
B[Cn(Ok) - (D))
(20)
X
where 0* is the minimizer of (0) in the relative interior of corvex set C, and d the dimension of parameter.
8

---

Table 1: Utility comparison with the prior (e, 8)-DP ERM algorithms. We assume 1-Lipschitz. 8-smooth and X-strongly convex loss. Size of imput dataset is n, and dimension of parameter vector 0 is d. For objective perturbation, we assume & 2 3
2X and loss is twice differentiable. For our result, we We ignore numerical constants
assume (1)) The lower bound is f (min (1, 2
and multiplicative dependence on log(1/6).
Method
Utility Upper Bound
Gradient complexity
Bassily et al.
3
Noisy SGD
0
(1o) An
n²
Wang al.
23
DP-SVRG
( dlog(n) An=
O
(n log( An
Zhang et al. 26
Output Perturbation
0 x2n222)
Kifer et al.
Ohjective Perturbation
d 0
An=
NA
This Paper
Noisy GD
0 0d
( 22 fr log
n²
This lemma shows decreasing excess empirical risk for noisy GD algorithm under Lipschitz smooth strongly convex loss function the number of iterations K increases. The utility is determined by K and the noise variance o², which are constrained under (a,,'))RDP. Using our tight RDP guarantee in Corollary T we prove optimal utility for noisy GD.
Theorem 4 (Upper bound for (a, -DDP and (s, 8D-P Noisy GD), For Lipschitz smooth strongly convex loss function E(0; x) on bounded closed convex set C C R.d, and dataset D E x of size n, if the step-size B 2 and the initial parameter 0g IIc(N(O, 20 Ia)). then the noisy GD Algorithm iis (a, Rééééi differentially private, where a > 1 and E' > O, and satisfies
E EiCn(Ok-) LD( = 0 a,ddI.
(21)
E'X²n2
by setting noise variance o² Equivalently, for e S 2 log(1/8) 18) and 8 > O, Algorithm 7 (e, -.dd))irrrrelliillll private, and satisfies
4 A and number of updates K* = 2
log( add
n'te"
x
[[[n((k-) -()(0)))_-((0))))- =0( 3dl2 (11))))(111))
0( 2X2n2
(22)
by setting noise variance o² 4L'((+21og(118) and number of updates K*=
2 X² log(
?=
Tog(l/88a
Our algorithm achieves this utility guarantee with 0 O log
2n2
gradient computations of
VE(0; x). which is faster than noisy SGD algorithm (3 with a factor of n. However, we additionally assume smoothness for the loss function. Our gradient complexity also matches that of other efficient gradient perturbation and output perturbation methods [23 26), as shown in Table []
This utility matches the following theoretical lower bound in Bassily al. 3 for the best attainable utility of (e, diifferrennl private algorithms on Lipschitz smooth strongly convex loss functions.
Theorem (3 Lower bound for (s, DDD algorithms). Let n. d E N, e > 0, and ō = o( For every (e, -ifffeeeryyy private algorithm A (whose output is denoted by (erio), there is dataset D E X such that, with probability least 1/3 (over the algorithm random coins), we must have
2 1):
(D(Opriv) - LD(0') Ω min
(23)
where 0" minimizes constructed 1-Lipschitz, 1-strongly convex objective Co(() over convex set C.
Our utility matches this lower bound upto the constant factor log(1/8), when assuming e = 0(1).
This improves upon the previous gradient perturbation methods [3 24 by factor of log(n), and matches the utility of previously know optimal ERM algorithm for Lipschitz smooth strongly convex loss functions, such as objective perturbation 6 44 and output perturbation (26).

---

Utility gain from tight privacy guarantee As shown in Table 1 our utility guarantee for noisy GD is logarithiically better than that for noisy SGD Bassily et al. 3 although the two algorithms are extremely similar. This is because we use our tight RDP guarantee, while Bassily et al. [3] use composition-basee privacy bound. More specifically, noisy SGD needs n² iterations to achieve the optimal utility, as shown in Table This number of iterations is large enough for the composition- based privacy bound to grow above our RDP guarantee, thus leaving room for improving privacy utility trade-off, as we further discuss in Appendix F This concludes that our tight privacy guarantee enables providing a superior privacy-utility trade-off, for Lipschitz, strongly convex, and smooth loss functions.
Our algorithm also has significantly smaller gradient complexity than noisy SGD [3. for strongly convex loss functions, by a factor of n/log n. We use (moderately large) constant step-size, thus achieving fast convergence to optimal utility. However, noisy SGD uses a decreasing step-size, thus requiring more iterations to reach optimal utility.
6
Conclusions
We have developed a novel theoretical framework for analyzing the dynamics of privacy loss for noisy gradient descent algorithms. Our theoretical results show that by hiding the internal state of the training algorithm (over many iterations over the whole data), we can tightly analyze the rate of information leakage throughout training, and derive bound that is significantly tighter than that of composition-bann approaches.
Future Work. Our main result is tight privacy guarantee for Noisy GD smooth and strongly convex loss functions. The assumptions are very similar to that of the prior work on privacy amplification by iteration (8), and have obvious advantages in enabling the tightness and utility analysis. However, the remaining open challenge is to extend this analysis to non-smooth and non-convex loss functions, and stochastic gradient updates, which are used notably in deep learning.
Acknowledgements and Funding
The authors would like to thank Joe P. Chen, Hedong Zhang and anonymous reviewers for helpful discussions on the earlier versions of this paper.
This research is supported in part by Intel Faculty Award (within the www.private-ai.oog center), Huawei, Google Faculty Award, VMWare Early Career Faculty Award, and the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative (any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not reflect the views of National Research Foundation, Singapore).
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016
[2] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov difsassion operators, volume 348. Springer Science & Business Media, 2013.
[3] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Effi- cient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium Foundations of Computer Science, pages 464-473. IEEE, 2014.
[4] William M Bolstad. Understanding computational Bayesian statistics, volume 644. John Wiley
& Sons, 2009.
[5] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, al. Extracting training data from large language models. arXiv preprint arXivv2012.07805, 2020.
[6] Kamalika Chaudhuri, Claire Monteleoni, and Anand Sarwate. Differentially private empirical 2011.
risk minimization. Journal of Machine Learning Research,
10

---

[7] Cynthia Dwork. Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3-4):211-407) 2014.
[8] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 521-532. IEEE, 2018.
[9] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[10] Adriaan Daniël Fokker. Die mittlere energie rotierender elektrischer dipole im strahlungsfeld. Annalen der Physik, 348(5):810-820, 1914.
[1]] Arun Ganesh and Kunal Talwar. Faster differentially private samplers via Rényi divergence analysis of discretized Langevin MCMC. Advances Neural Information Processing Systems,
33, 2020.
[12] Leonard Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4): 1061-1083, 1975.
[13] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private private sgd? Advances Neural Information Processing Systems, 33, 2020.
[14] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
[15] Michel Ledoux. The concentration of measure phenomenon. Number 89, American Mathemati- cal Soc., 2001.
[16] Kentaro Minami, Hitomi Arai, Issei Sato, and Hiroshi Nakagawa. Differential privacy without sensitivity. In Advances in Neural Information Processing Systems, pages 956-964, 2016.
[17] Iya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[18] Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP), pages 739-753. IEEE, 2019.
[19] Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Ad- versary instantiation: Lower bounds for differentially private machine learning. arXiv preprint arXiv:2101.04535. 2021.
[20] Issei Sato and Hiroshi Nakagawa. Approximation analysis of stochastic gradient Langevin dynamics by using fokker-planck equation and ito process. In International Conference on Machine Learning, pages 982-990, 2014.
[21] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium Security and Privacy
(SP), pages 3-18. IEEF, 2017.
[22] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algo- rithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems, pages 8094-8106, 2019.
[23] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Newral Information Processing Systems, pages 2722- 2731, 2017.
[24] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. arXiv preprint arXiv: 1802.05211, 2018.
[25] Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pages 2493-2502, 2015.
[26] Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 3922-3928, 2017.
11


Reviews:
[{"review_id": "khFY-_Ey0-Y", "reviewer": "Reviewer_csAH", "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.  ", "questions": "", "limitations": "", "rating": 7, "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": "The paper is well-written, and to the best of my knowledge the results are new. However, I have the following concerns.\n\n(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. \n\n(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.\n\n(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. \n\n(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?\n\n(5) In the paragraph after Lemma 3, you used the terminology PDE, but in (12), you have an inequality instead of an equality.\n\n(6) In the sentence after (7), write \"(k+1)th step\" instead.\n\n(7) In section 6, it should be \"an exponential rate\".\n\n(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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "iDd2zxRfhy0", "reviewer": "Reviewer_vsV6", "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.\n", "questions": "", "limitations": "", "rating": 7, "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": "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. \n\nFor 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. \n\nThe assumption of strongly convex and smooth losses limits the practical applicability in deep learning and this has been acknowledged by the authors. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Addressed by the authors. I do not foresee any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 "}, "extra_text": {}}, {"review_id": "SNH-_9tafa", "reviewer": "Reviewer_wSUc", "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\n$\\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).$\n\nIn 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 \nof smooth and strongly convex loss functions.", "questions": "", "limitations": "", "rating": 7, "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": "Originality & Quality:\n\nThe 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.\nWhile I have written papers in (Noisy) Gradient-Descent Optimization, Langevin Dynamics and Statistical Differential Privacy, I have never\nbeen exposed in this corner of the literature. \n\n$[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).\n\nIn 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.\n\n\nClarity:\n\nHere there are my main objections with this submission. The paper is partially very well-written and partially disappointing.\nFor example until line 122 the flow guides the reader with good intuition behind the techniques used.\nHowever, already there are some annoying typos, which are repeatitively present in the appendix too.\n\n$[Q2]$ For example Eq (6). Did we lose a minus in front of $\\nabla L_D$ based on Eq (5)?\n\n$[Q3]$ Imagine the case of the mean reader who has not been exposed before in Wiener processes/Ito martingale processess.\n            How did we derive the Equation between (7) and (8) line 127? \n\nIn 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:\n\n$\\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].$\nNow how did we derive the Eq  between (7) and (8)? Also what is happening with the sign \"minus\" in front of the gradient again?\n\n$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\n\nIn contrast, Lemma 1 and its proof was well-stated and written correspondingly.\n\nFurthermore, 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.\n\n$[Q4]$ Does the Rate of Renyi privacy loss equation belong to the novel parts of this submission? \n             Is it the first time that we derive such a rate for the Langevin diffusion?\n\nEither 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. \n\n$[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?\n\n$[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?\n\nFinally another important question is the tightness of the result.\n\n$[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.\n\n\nIn 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.\n\n$[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\n\n$[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?\n\n$[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. \n\n$[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$\n like they provide a proof of extension lemma adapted to their setting.\n\n\nSignificance:\nIn 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\n\nSome extra questions that I would like to ask the authors?\n\n$[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)?\n\n$[Q8 ]$ Where in the proof was used crucially the smoothness and strong convexity of loss function?\n\n$[ 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "-fGX3vShKlc", "reviewer": "Reviewer_3Yfj", "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.", "questions": "", "limitations": "", "rating": 7, "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, 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. \n\nIn 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.\n\nIn 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)