summaries: 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.   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. 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. 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. 
abstractText: 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 to 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 a provably tight bound on the Rényi 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.
authors.name: Rishav Chourasia
authors.name: Jiayuan Ye
authors.name: Reza Shokri
references.authors: Martin Abadi Andy Chu Ian Goodfellow H Brendan McMahan Ilya Mironov Kunal Talwar Li Zhang
references.title: Deep learning with differential privacy
references.venue: In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,
references.authors: Dominique Bakry Ivan Gentil Michel Ledoux
references.title: Analysis and geometry of Markov diffusion operators, volume 348
references.venue: Springer Science & Business Media,
references.authors: Raef Bassily Adam Smith Abhradeep Thakurta
references.title: Private empirical risk minimization: Efficient algorithms and tight error bounds
references.venue: In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science,
references.authors: William M Bolstad
references.title: Understanding computational Bayesian statistics, volume 644
references.authors: Nicholas Carlini Florian Tramer Eric Wallace Matthew Jagielski Ariel Herbert-Voss Katherine Lee Adam Roberts Tom Brown Dawn Song Ulfar Erlingsson
references.title: Extracting training data from large language models
references.authors: Kamalika Chaudhuri Claire Monteleoni Anand D Sarwate
references.title: Differentially private empirical risk minimization
references.venue: Journal of Machine Learning Research,
references.authors: Cynthia Dwork Aaron Roth
references.title: The algorithmic foundations of differential privacy
references.venue: Foundations and Trends® in Theoretical Computer Science,
references.authors: Vitaly Feldman Ilya Mironov Kunal Talwar Abhradeep Thakurta
references.title: Privacy amplification by iteration
references.venue: IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS),
references.authors: Vitaly Feldman Tomer Koren Kunal Talwar
references.title: Private stochastic convex optimization: optimal rates in linear time
references.venue: In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,
references.authors: Adriaan Daniël Fokker
references.title: Die mittlere energie rotierender elektrischer dipole im strahlungsfeld
references.venue: Annalen der Physik,
references.authors: Arun Ganesh Kunal Talwar
references.title: Faster differentially private samplers via Rényi divergence analysis of discretized Langevin MCMC
references.venue: Advances in Neural Information Processing Systems,
references.authors: Leonard Gross
references.title: Logarithmic sobolev inequalities
references.venue: American Journal of Mathematics,
references.authors: Matthew Jagielski Jonathan Ullman Alina Oprea
references.title: Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information
references.venue: Processing Systems,
references.authors: Daniel Kifer Adam Smith Abhradeep Thakurta
references.title: Private convex empirical risk minimization and high-dimensional regression
references.venue: In Conference on Learning Theory,
references.authors: Michel Ledoux
references.title: The concentration of measure phenomenon
references.venue: Number 89. American Mathematical Soc.,
references.authors: Kentaro Minami HItomi Arai Issei Sato Hiroshi Nakagawa
references.title: Differential privacy without sensitivity
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ilya Mironov
references.title: Rényi differential privacy
references.venue: IEEE 30th Computer Security Foundations Symposium (CSF),
references.authors: Milad Nasr Reza Shokri Amir Houmansadr
references.title: Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning
references.venue: IEEE symposium on security and privacy (SP),
references.authors: Milad Nasr Shuang Song Abhradeep Thakurta Nicolas Papernot Nicholas Carlini
references.title: Adversary instantiation: Lower bounds for differentially private machine learning
references.venue: arXiv preprint arXiv:2101.04535,
references.authors: Issei Sato Hiroshi Nakagawa
references.title: Approximation analysis of stochastic gradient Langevin dynamics by using fokker-planck equation and ito process
references.venue: In International Conference on Machine Learning,
references.authors: Reza Shokri Marco Stronati Congzheng Song Vitaly Shmatikov
references.title: Membership inference attacks against machine learning models
references.venue: IEEE Symposium on Security and Privacy (SP),
references.authors: Santosh Vempala Andre Wibisono
references.title: Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Di Wang Minwei Ye Jinhui Xu
references.title: Differentially private empirical risk minimization revisited: Faster and more general
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Di Wang Minwei Ye Jinhui Xu
references.title: Differentially private empirical risk minimization revisited: Faster and more general
references.venue: arXiv preprint arXiv:1802.05251,
references.authors: Yu-Xiang Wang Stephen Fienberg Alex Smola
references.title: Privacy for free: Posterior sampling and stochastic gradient monte carlo
references.venue: In International Conference on Machine Learning,
references.authors: Jiaqi Zhang Kai Zheng Wenlong Mou Liwei Wang
references.title: Efficient private erm for smooth objectives
references.venue: In Proceedings of the 26th International Joint Conference on Artificial Intelligence,
sections.heading: 1 Introduction
sections.text: Machine learning models leak a significant amount of information about their training data, through their parameters and predictions [21, 18, 5]. Iterative randomized training algorithms can limit this information leakage and bound the differential privacy loss of the learning process [3, 1, 8, 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 to 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 [13, 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, 9] 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 a guarantee is quantitatively similar to composition bounds of 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 a pair of continuous-time Langevin diffusion [20] 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.
  *Equal contribution. Alphabetical Order.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  We then prove an exponentially-fast converging privacy bound for noisy GD: (simplified theorem) Under 1-strongly convex and β-smooth loss function `(θ;x) with total gradient sensitivity 1, the noisy GD Algorithm 1, with initial parameter vector θ0 ∼ ΠC(N (0, 2σ2Id)) and step size η < 1β ,
  satisfies (α, ε)-Rényi DP with ε = O (
  α σ2n2 (1− e
  −ηK2 ) ) , 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 algorithms. 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 tightness of the bound, the utility of the randomized algorithm under the computed differential 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( dn2ε2 ), with a small gradient complexity of order O(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 a 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.
sections.heading: 2 Preliminaries on differential privacy
sections.text: Let X be the data universe, and a dataset D contain n records from it: D = (x1,x2, · · · ,xn) ∈ Xn. 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 to another measure ν′ on same space (denoted as ν ν′) if for all measurable set S, ν(S) = 0 whenever ν′(S) = 0.
  Definition 2.1 ([17] Rényi differential privacy). Let α > 1. A randomized algorithm A : Xn → Rd satisfies (α, ε)-Rényi Differential Privacy (RDP), if for any two neighboring datasets D,D′ ∈ Xn, the α Rényi divergence Rα (A(D)‖A(D′)) ≤ ε. For a pair of measures ν, ν′ over the same space with ν ν′, Rα (ν‖ν′) is defined as
  Rα (ν‖ν′) = 1
  α− 1 logEα (ν‖ν′) , where Eα (ν‖ν′) =
  ∫ ( dν
  dν′
  )α dν′. (1)
  We refer to Rα (A(D)‖A(D′)) also as the Rényi privacy loss of algorithm A on datasets D,D′. An RDP guarantee can be converted to (ε, δ)-DP guarantee [17, Proposition 5].
  Definition 2.2 ([22] Rényi information). Let α > 1. For any two measures ν, ν′ over Rd with µ ν′ and corresponding probability density functions p, p′, if p(θ)p′(θ) is differentiable, the α-Rényi Information of ν with respect to ν′ is
  Iα (ν‖ν′) = 4
  α2 E θ∼p′ [∥∥∥∥∇ p(θ)α2p′(θ)α2 ∥∥∥∥2
  2
  ] = E θ∼p′ [ p(θ)α−2 p′(θ)α−2 ∥∥∥∥∇ p(θ)p′(θ) ∥∥∥∥2
  2
  ] . (2)
  See the Appendix B for a comprehensive presentation of preliminaries.
sections.heading: 3 Privacy analysis of noisy gradient descent
sections.text: Let D = (x1,x2, · · · ,xn) be a dataset of size n with records taken from a universe X . For a given machine learning algorithm, let `(θ;x) : X × Rd → R be a loss function of a parameter vector θ ∈ C on the data point x, where C is a closed convex set (can be Rd). A generic formulation of the optimization problem to learn the model parameters, is in the form of empirical risk minimization (ERM) with the following objective, where LD(θ) is the empirical loss
  of the model, with parameter vector θ, on a dataset D.
  θ∗ = arg min θ∈C
  LD(θ), where LD(θ) = 1
  n ∑ x∈D `(θ;x). (3)
  Releasing this optimization output (i.e., θ∗) can leak information about the dataset D, hence violating data privacy. To mitigate this risk, there exist randomized algorithms to ensure that the (α-Rényi) privacy loss of the ERM algorithm is upper-bounded by ε, i.e., the algorithm satisfies (α, ε)-RDP.
  Algorithm 1 ANoisy-GD: Noisy Gradient Descent
  Input: Dataset D = (x1,x2, · · · ,xn), loss function `(θ;x), closed convex set C ⊆ Rd, learning rate η, noise variance σ2, initial parameter vector θ0.
  1: for k = 0, 1, · · · ,K − 1 do 2: g(θk;D) = ∑n i=1∇`(θk;xi)
  3: θk+1 = ΠC(θk − ηng(θk;D) + √
  2ηN (0, σ2Id)) 4: Output θK
  In this paper, our objective is to analyze privacy loss of Noisy Gradient Descent (Algorithm 1), which is a randomized ERM algorithm. Let θk, θ′k be the parameter vectors at the k’th iteration of ANoisy-GD on neighboring datasets D and D′, respectively. We denote by Θηk and Θ′ηk the corresponding random variables that model θk and θ′k. We abuse notation to also denote their probability distributions by Θηk and Θ′ηk. In this paper, our objective is to model and analyze the dynamics of differential privacy of this algorithm. More precisely, we focus on the following.
  1. Compute an RDP bound (i.e., the worst case Rényi divergence Rα (ΘK‖Θ′K) between the output distributions of two neighboring datasets) for Algorithm 1, and analyze its tightness.
  2. Compute the contribution of each iteration to the privacy loss. As we go from step k = 1 to K in Algorithm 1, we investigate how the algorithm’s privacy loss changes as it runs the k’th iteration (computed as Rα ( Θηk ∥∥∥Θ′ηk)−Rα (Θη(k−1)∥∥∥Θ′η(k−1))). In the end, we aim to provide a RDP bound that is tight, thus facilitating optimal utility [3]. We emphasize that our goal is to construct a theoretical framework for analyzing privacy loss of releasing the output θK of the algorithm, assuming private internal states (i.e., θ1, · · · , θK−1).
sections.heading: 3.1 Tracing diffusion for Noisy GD
sections.text: To analyze the privacy loss of Noisy GD, which is a discrete-time stochastic process, we first interpolate each discrete update from θk to θk+1 with a piece-wise continuously differentiable diffusion process. Let D and D′ be a pair of arbitrarily chosen neighboring datasets. Given step-size η and initial parameter vector θ0 = θ′0, the respective k’th discrete updates in Algorithm 1 on neighboring datasets D and D′ are{
  θk+1 = ΠC(θk − η∇LD(θk) + √ 2ησ2Zk), θ′k+1 = ΠC(θ ′ k − η∇LD(θ′k) + √ 2ησ2Zk), with Zk ∼ N (0, Id). (4)
  These two discrete jumps can be interpolated with two stochastic processes Θt and Θ′t over time ηk ≤ t ≤ η(k + 1) respectively. At the start of each step, t = ηk, the random variables Θηk and Θ′ηk model the distribution of the θk and θ ′ k in the noisy GD processes respectively. During time ηk < t < η(k + 1), we model the respective gradient updates on D and D′ with the following stochastic processes.{
  Θt = Θηk − η · U1(Θηk)− (t− ηk) · U2(Θηk) + √
  2(t− ηk)σ2Zk Θ′t = Θ ′ ηk − η · U1(Θ′ηk) + (t− ηk) · U2(Θ′ηk) + √ 2(t− ηk)σ2Zk
  (5)
  where the vectors U1(θ) = 12 (∇LD(θ) +∇LD′(θ)) and U2(θ) = 1 2 (∇LD(θ)−∇LD′(θ)) represent the average and difference between gradients on neighboring datasets D and D′ respectively.
  At the end of step, i.e. at t→ η(k + 1), we project Θt and Θ′t onto convex set C, and obtain
  Θη(k+1) = ΠC
  ( lim
  t→η(k+1)− Θt
  ) ,Θ′η(k+1) = ΠC ( lim
  t→η(k+1)− Θ′t
  ) . (6)
  By plugging (5) into (6), we compute that the projected random variable Θη(k+1) and Θ′η(k+1) have the same distributions as the parameters θk+1 and θ′k+1 at k + 1
  th step of noisy GD respectively. Repeating the construction for k = 0, · · · ,K − 1, we define two piece-wise continuous diffusion processes {Θt}t≥0 and {Θ′t}t≥0 whose distributions at time t = ηk are consistent with θk and θ′k in the noisy GD processes (4) for any k ∈ {0, · · · ,K − 1}. Definition 3.1 (Coupled tracing diffusions). Let Θ0 = Θ′0 be two identically distributed random variables. We refer to the stochastic processes {Θt}t≥0 and {Θ′t}t≥0 that evolve along diffusion processes (5) in ηk < t < η(k + 1) and undergo projection steps (6) at the end of step t = η(k + 1), as coupled tracing diffusions for noisy GD on neighboring datasets D,D′.
  The Rényi divergence Rα(ΘηK‖Θ′ηK) reflects the Rényi privacy loss of Algorithm 1 with K steps. Conditioned on observing θk and θ′k, the processes {Θt}ηk<t<η(k+1) and {Θ′t}ηk<t<η(k+1) in (5) are Langevin diffusions along vector fields −U2(θk) and U2(θ′k) respectively, for duration η. Therefore, conditioned on observing θk and θ′k, the diffusion processes in (5) have the following stochastic differential equations (SDEs) respectively.
  dΘt = −U2(θk)dt+ √ 2σ2dWt, dΘ ′ t = U2(θ ′ k)dt+ √ 2σ2dWt, (7)
  where dWt ∼ √ dtN (0, Id) describe the Wiener processes on Rd. Therefore, the conditional probability density functions pt|ηk(θ|θk) and p′t|ηk(θ|θ ′ k) follow the following Fokker-Planck equation. For brevity, we use pt|ηk(θ|θk) and p′t|ηk(θ|θ ′ k) to represent the conditional probability density function p(Θt = θ|Θηk = θk) and p(Θ′t = θ|Θ′ηk = θ′k) respectively. ∂pt|ηk(θ|θk) ∂t = ∇ · ( pt|ηk(θ|θk)U2(θk) ) + σ2∆pt|ηk(θ|θk) ∂p′t|ηk(θ|θ ′ k) ∂t = −∇ · ( p′t|ηk(θ|θ ′ k)U2(θ ′ k) ) + σ2∆pt|ηk(θ|θ′k) (8)
  By taking expectations over probability density function pηk(θk) or p′ηk(θ ′ k) on both sides of (8), we obtain the partial differential equation that models the evolution of (unconditioned) probability density function pt(θ) and p′t(θ) in the coupled tracing diffusions. Lemma 1. For coupled tracing diffusion processes (5) in time ηk < t < η(k + 1), the equivalent Fokker-Planck equations are{
  ∂pt(θ) ∂t = ∇ · (pt(θ)Vt(θ)) + σ 2∆pt(θ) ∂p′t(θ) ∂t = ∇ · (p ′ t(θ)V ′ t (θ)) + σ 2∆p′t(θ), (9)
  where Vt(θ) = −V ′t (θ) = E θk∼pηk|t [U2(θk)|θ] are time-dependent vector fields on Rd, and U2(θ) = 1 2 [∇LD(θ)−∇LD′(θ)] is the difference between gradients on 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.
sections.heading: 3.2 Privacy erosion in tracing (Langevin) diffusion
sections.text: The Rényi divergence (privacy loss) Rα (Θt‖Θ′t) between coupled tracing diffusion processes increases over time, as the vector fields Vt, V ′t 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-Planck equations (9) for diffusions under different vector fields.
  Using equation (9), we compute a bound on the rate (partial derivative) of Rα (Θt‖Θ′t) over time in the following lemma, to model privacy erosion between two different diffusion processes. We refer to coupled diffusions as respective diffusion processes under different vector fields Vt and V ′t .
  Lemma 2 (Rate of Rényi privacy loss). Let Vt and V ′t be two vector fields on Rd corresponding to a pair of arbitrarily chosen neighboring datasets D and D′ with max
  θ∈Rd ‖Vt(θ)− V ′t (θ)‖2 ≤ Sv for all
  t ≥ 0. Then, for corresponding coupled diffusions {Θt}t≥0 and {Θ′t}t≥0 under vector fields Vt and V ′t and noise variance σ
  2, the Rényi privacy loss rate at any t ≥ 0 is upper bounded by ∂Rα (Θt‖Θ′t)
  ∂t ≤ 1 γ αS2v 4σ2 − (1− γ)σ2α Iα (Θt‖Θ ′ t) Eα (Θt‖Θ′t) . (10)
  where γ > 0 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 Iα (Θt‖Θ′t) depends on unknown distributions Θt,Θ′t, and is intractable to compute. Even with explicit expressions for distributions Θt,Θ ′ t, the calculation would involve integration in Rd which is computationally prohibitive for large d. Note that, however, the ratio Iα/Eα is always positive by definition. Therefore, the Rényi divergence (privacy loss) rate in (10) is bounded by its first component (a constant) given any fixed α. Theorem 1 (Linear Rényi divergence bound). Let Vt and V ′t be two vector fields on Rd, with max θ∈Rd ‖Vt(θ)− V ′t (θ)‖2 ≤ Sv for all t ≥ 0. Then, the coupled diffusions under vector fields Vt and V ′t with noise variance σ 2 for time T has α-Rényi divergence bounded by ε = αS 2 vT 4σ2 .
  When the vector fields are Vt = −∇LD and V ′t = −∇LD′ , the coupled diffusions follow Langevin diffusion. By definition B.10 of total gradient sensitivity, max
  θ∈Rd ‖∇LD(θ)−∇LD′(θ)‖2 ≤ Sg n . There-
  fore, this naïve privacy analysis gives linear RDP guarantee for Langevin diffusion, which resembles the moment accountant analysis [1]. However, a tighter bound of Rényi privacy loss is possible with finer control of the ratio Iα (Θt‖Θ′t)/Eα (Θt‖Θ′t), which by definition depends on the likelihood ratio between Θt and Θ′t, 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α/Eα term in lemma 2 by making an isoperimetric assumption known as log-Sobolev inequality [2], described as follows. Definition 3.2 ([12] Log-Sobolev Inequality (c-LSI)). Distribution of a random variable Θ on Rd satisfies logarithmic Sobolev inequality with parameter c > 0, i.e. it is c-LSI, if for all functions f in the function set FΘ = {f : Rd → R|∇f is continuous, and E(f(Θ)2) <∞}, we have
  E[f(Θ)2 log f(Θ)2]− E[f(Θ)2] logE[f(Θ)2] ≤ 2 c E[‖∇f(Θ)‖22]. (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 Iα/Eα for an arbitrary pair of distributions. Lemma 3 ([22] c-LSI in terms of Rényi Divergence). Suppose Θt,Θ′t ∈ Rd are random variables such that the density ratio between distributions of Θt and Θ′t lies in FΘ′t . Then for any α ≥ 1,
  Rα (Θt‖Θ′t) + α(α− 1) ∂Rα (Θt‖Θ′t) ∂α ≤ α 2 2c Iα (Θt‖Θ′t) Eα (Θt‖Θ′t) , (12)
  if and only if distribution of Θ′t satisfies c-LSI.
  Note that ∂Rα(Θt‖Θ′t)
  ∂α is always positive, as Rα (Θt‖Θ ′ t) monotonically increases with α > 1 [17].
  This lemma shows that Iα (Θt‖Θ′t)/Eα (Θt‖Θ′t) grows monotonically with the Rényi privacy loss Rα (Θt‖Θ′t). By Lemma 2, this implies a throttling privacy loss rate as privacy loss accumulates.Combining Lemma 2 and Lemma 3, 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 α. For brevity, let R(α, t) represent Rα (Θt‖Θ′t).
  ∂R(α, t) ∂t ≤ 1 γ αS2v 4σ2
  − 2(1− γ)σ2c [ R(α, t)
  α + (α− 1)∂R(α, t) ∂α
  ] (13)
  The initial privacy loss R(α, 0) = 0, as Θ0 = Θ′0. The solution for this PDE increases with time t ≥ 0, and models the erosion of Rényi privacy loss in coupled tracing diffusions Θt and Θ′t.
sections.heading: 3.3 Privacy guarantee for Noisy GD
sections.text: 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 Vt and V ′t for coupled tracing diffusions for noisy GD on neighboring datasets D and D′. Lemma 4. Let `(θ;x) be a loss function on closed convex set C, with a finite total gradient sensitivity Sg . Let {Θt}t≥0 and {Θ′t}t≥0 be the coupled tracing diffusions for noisy GD on neighboring datasets D,D′ ∈ Xn, under loss `(θ;x) and noise variance σ2. Then the difference between underlying vector fields Vt and V ′t for coupled tracing diffusions is bounded by
  max θ∈Rd ‖Vt(θ)− V ′t (θ)‖2 ≤ Sg n , (14)
  where Vt(θ) and V ′t (θ) are time-dependent vector fields on Rd, defined in Lemma 1.
  We then substitute Sv in PDE (13) with Sg/n, and compute the following PDE modelling Rényi privacy loss dynamics of tracing diffusion at ηk < t < η(k + 1), under c-LSI condition.
  ∂R(α, t) ∂t ≤ 1 γ αS2g 4σ2n2
  − 2(1− γ)σ2c [ R(α, t)
  α + (α− 1)∂R(α, t) ∂α
  ] (15)
  We solve this PDE under γ = 12 for each time piece, and combine multiple pieces by seeing projection as privacy-preserving post-processing step. We derive the RDP guarantee for the Noisy GD algorithm. Theorem 2 (RDP for noisy GD under c-LSI). Let {Θt}t≥0 and {Θ′t}t≥0 be the tracing diffusion for ANoisy-GD on neighboring datasets D and D′, under noise variance σ2 and loss function `(θ;x). Let `(θ;x) be a loss function on closed convex set C ⊆ Rd, with a finite total gradient sensitivity Sg. If for any neighboring datasets D and D′, the corresponding coupled tracing diffusions Θt and Θ′t satisfy c-LSI throughout 0 ≤ t ≤ ηK, then ANoisy-GD satisfies (α, ε) Rényi Differential Privacy for
  ε = αS2g
  2cσ4n2 (1− e−σ 2cηK). (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 c for given Noisy GD process.
  Isoperimetry constants for noisy GD When the loss function is strongly convex and smooth, we 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, as discussed in Appendix D.3. Lemma 5 (LSI for noisy GD). If loss function `(θ;x) is λ-strongly convex and β-smooth over a closed convex set C, the step-size is η < 1β , and initial distribution is Θ0 ∼ ΠC(N (0, 2σ2
  λ Id)), then the coupled tracing diffusion processes {Θt}t≥0 and {Θ′t}t≥0 for noisy GD on any neighboring datasets D and D′ satisfy c-LSI for any t ≥ 0 with c = λ2σ2 .
  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 `(θ;x) be a λ-strongly convex, and β-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 θ0 ∼ ΠC(N (0, 2σ 2 λ Id)), and step-size η < 1 β , satisfies (α, ε) Rényi Differential Privacy with
  ε = αS2g λσ2n2 (1− e−ληK/2).
  This privacy bound has quadratic dependence on the total gradient sensitivity Sg, which is upper bounded by Sg ≤ 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 1 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 λ. The RDP order α 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.
  analysis: ε = αS2g λσ2n2 ·
  (
  1− e−ληK/2
  )
  ; and Baseline composition-based analysis (derived by moment accountant [1] with details in Appendix E): ε = αS2g
  4n2σ2 · ηK.
sections.heading: 4 Tightness analysis: a lower bound on privacy loss of noisy GD
sections.text: Differential privacy guarantees reflect a bound on privacy loss on an algorithm; thus, it is very crucial to also have an analysis of their tightness (i.e., how close they are to the exact privacy loss). We prove that our RDP guarantee in Theorem 2 is tight. To this end, we construct an instance of the ERM 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 to lower bound the the exact Rényi privacy loss Rα ( ΘKη ∥∥Θ′Kη) in general. This might require having an explicit expression for the probability distribution over the last-iterate parameters θk. Computing a 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 a Gaussian distribution. Therefore, we construct such an ERM objective, compute the exact privacy loss, and prove the following lower bound. Theorem 3 (Lower bound on RDP of ANoisy-GD). There exist two neighboring datasets D,D′ ∈ Xn, a start parameter θ0, and a smooth loss function `(θ;x) on unconstrained convex set C = Rd, with a finite total gradient sensitivity Sg, such that for any step-size η < 1, noise variance σ2 > 0, and iteration K ∈ N, the privacy loss of ANoisy-GD on D,D′ is lower-bounded by
  Rα ( ΘηK ∥∥Θ′ηK) ≥ αS2g4σ2n2 (1− e−ηK) . (17) We prove this lower bound using the `2-squared norm loss as ERM objective: minθ∈Rd ∑n i=1 ‖θ−xi‖22 n . We assume bounded data domain s.t. the gradient has finite sensitivity. With start parameter θ0 = 0d, the kth step parameter θk is distributed as Gaussian with mean µk = ηx̄ ∑k−1 i=0 (1− η)i and variance σ2k = 2ησ2 n2 ∑k−1 i=0 (1− η)2i in each dimension, where x̄ = ∑n i=1 xi/n is the empirical dataset mean. We explicitly compute the privacy loss at any step K, which is lower bounded by αS2g
  4σ2n2 (1− e −ηK).
  Meanwhile, Corollary 1 gives our RDP upper bound = αS2g σ2n2
  ( 1− e−ηK ) for this same ERM
  objective. This upper bound matches the lower bound at every step K, up to a small constant of 4.
  Moreover, Theorem 2 facilitates a smaller RDP upper bound than Corollary 1 by bounding the LSI constant throughout Noisy GD exactly. For squared-norm loss function, Theorem 2 gives the
  following tighter RDP upper-bound for Noisy GD, because all intermediate Gaussian distributions satisfy c-LSI with c = 2−η2σ2 , as proved in Appendix E. Corollary 2 (RDP guarantee of ANoisy-GD on `2-norm squared loss). For any two neighboring datasets D,D′ ∈ Xn, start parameter θ0, step-size η, noise variance σ2, and K ∈ N, if the loss function is `2-norm squared loss `(θ;x) = 12 ‖θ − x‖ 2 2 on unconstrained convex set C = Rd, with a finite total gradient sensitivity Sg , the privacy loss of ANoisy-GD on D,D′ is upper-bounded by
  Rα ( ΘηK ∥∥Θ′ηK) ≤ αS2g(2− η)σ2n2 (1− e− 2−η2 ηK). (18) This RDP guarantee converges fast to O(
  αS2g σ2n2 ), which matches the lower bound at every step K,
  up to a constant of 42−η ≈ 2. This immediately shows tightness of our converging RDP guarantee throughout the training process, for a converging noisy GD algorithm. A different approach is to completely ignore the dynamics of differential privacy, and instead analyze privacy only at the convergence time (or when the algorithm is near convergence). Wang et al. [25], Minami et al. [16] show that sampling from the Gibbs posterior distribution ν(θ) ∝ e−LD(θ)/σ2 for bounded LD satisfies differential privacy. However, sampling exactly from the Gibbs distribution is difficult [4]. Thus, Minami et al. [16], Ganesh and Talwar [11] 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 iterationsK with extremely small step-size η. Minami et al. [16] compute the distance to convergence in total variation, and Ganesh and Talwar [11] 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 Ω(nd), which however still grows with model dimension d. In comparison, our DP guarantees are unaffected by parameter dimension d, which in practice can be much larger than the dataset size n.
  In contrast, composition-based privacy bound grows linearly as training proceeds, as shown in Figure 1. 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 E. Therefore, to conclude whether our RDP guarantee is superior to composition-based bound, we need to understand the number of iterations noisy GD needs, to achieve optimal utility. We discuss this in the following section.
sections.heading: 5 Utility analysis for noisy gradient descent
sections.text: The randomness, required for satisfying differential privacy, can adversely affect the utility of the trained model. The standard way to measure the utility of a randomized ERM algorithm (for example, ANoisy-GD) is to quantify its worst case excess empirical risk, which is defined as
  max D∈Xn
  E[LD(θ)− LD(θ∗)], (19)
  where θ is the output of the randomized algorithm ANoisy-GD on D, θ∗ 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 (α, ε′)-RDP constraint. The notion of optimality for utility is defined as the smallest upper-bound for excess empirical risk that can be guaranteed under (α, ε′)-RDP constraint by tuning the algorithm’s hyperparameters (such as the noise variance σ2 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-Lipschitz, λ-strongly convex and β-smooth loss function `(θ;x) over a closed convex set C ⊆ Rd, step-size η ≤ λ2β2 , and start parameter θ0 ∼ ΠC(N (0, 2σ 2 λ Id)), the excess empirical risk of Algorithm 1 is bounded by
  E[LD(θK)− LD(θ∗)] ≤ 2βL2
  λ2 e−ληK +
  2βdσ2
  λ , (20)
  where θ∗ is the minimizer of LD(θ) in the relative interior of convex set C, and d is the dimension of parameter.
  This lemma shows decreasing excess empirical risk for noisy GD algorithm under Lipschitz smooth strongly convex loss function as the number of iterations K increases. The utility is determined by K and the noise variance σ2, which are constrained under (α, ε′)-RDP. Using our tight RDP guarantee in Corollary 1, we prove optimal utility for noisy GD.
  Theorem 4 (Upper bound for (α, ε′)-RDP and (ε, δ)-DP Noisy GD). For Lipschitz smooth strongly convex loss function `(θ;x) on a bounded closed convex set C ⊆ Rd, and dataset D ∈ Xn of size n, if the step-size η = λ2β2 and the initial parameter θ0 ∼ ΠC(N (0, 2σ2
  λ Id)), then the noisy GD Algorithm 1 is (α, ε′)-Rényi differentially private, where α > 1 and ε′ > 0, and satisfies
  E[LD(θK∗)− LD(θ∗)] = O( αβdL2
  ε′λ2n2 ), (21)
  by setting noise variance σ2 = 4αL 2 λε′n2 , and number of updates K ∗ = 2β
  2 λ2 log( n2ε′ αd ).
  Equivalently, for ε ≤ 2 log(1/δ) and δ > 0, Algorithm 1 is (ε, δ)-differentially private, and satisfies
  E[LD(θK∗)− LD(θ∗)] = O( βdL2 log(1/δ)
  2λ2n2 ), (22)
  by setting noise variance σ2 = 8L 2(ε+2 log(1/δ)) λε2n2 , and number of updates K ∗ = 2β 2 λ2 log( n2ε2 4 log(1/δ)d ).
  Our algorithm achieves this utility guarantee with O(β 2 λ2n log ( ε2n2 d ) ) gradient computations of ∇`(θ;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 1.
  This utility matches the following theoretical lower bound in Bassily et al. [3] for the best attainable utility of ( , δ)-differentially private algorithms on Lipschitz smooth strongly convex loss functions.
  Theorem 5 ([3] Lower bound for (ε, δ)-DP algorithms). Let n, d ∈ N, ε > 0, and δ = o( 1n ). For every (ε, δ)-differentially private algorithm A (whose output is denoted by θpriv), there is a dataset D ∈ Xn such that, with probability at least 1/3 (over the algorithm random coins), we must have
  LD(θpriv)− LD(θ∗) = Ω ( min { 1, d
  ε2n2
  }) , (23)
  where θ∗ minimizes a constructed 1-Lipschitz, 1-strongly convex objective LD(θ) over convex set C.
  Our utility matches this lower bound upto the constant factor log(1/δ), when assuming βλ2 = O(1). This improves upon the previous gradient perturbation methods [3, 24] by a 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, 14] and output perturbation [26].
  Utility gain from tight privacy guarantee As shown in Table 1, our utility guarantee for noisy GD is logarithmically better than that for noisy SGD in 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 a composition-based privacy bound. More specifically, noisy SGD needs n2 iterations to achieve the optimal utility, as shown in Table 1. This number of iterations is large enough for the compositionbased 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 a (moderately large) constant step-size, thus achieving fast convergence to optimal utility. However, noisy SGD [3] uses a decreasing step-size, thus requiring more iterations to reach optimal utility.
sections.heading: 6 Conclusions
sections.text: 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 a bound that is significantly tighter than that of composition-based approaches.
  Future Work. Our main result is a tight privacy guarantee for Noisy GD on 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.org 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).
title: Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent