Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
Authors: Jason Altschuler
Kunal Talwar
Venue: NeurIPS 2022 Accept (2022)
Keywords: private optimization
convex optimization
noisy-SGD
DP-SGD
stochastic gradient Langevin dynamics
privacy losss

Abstract: A central issue in machine learning is how to train models on sensitive user data. Industry has widely adopted a simple algorithm: Stochastic Gradient Descent with noise (a.k.a. Stochastic Gradient Langevin Dynamics). However, foundational theoretical questions about this algorithm's privacy loss remain open---even in the seemingly simple setting of smooth convex losses over a bounded domain. Our main result resolves these questions: for a large range of parameters, we characterize the differential privacy up to a constant. This result reveals that all previous analyses for this setting have the wrong qualitative behavior. Specifically, while previous privacy analyses increase ad infinitum in the number of iterations, we show that after a small burn-in period, running SGD longer leaks no further privacy. Our analysis departs from previous approaches based on fast mixing, instead using techniques based on optimal transport (namely, Privacy Amplification by Iteration) and the Sampled Gaussian Mechanism (namely, Privacy Amplification by Sampling). Our techniques readily extend to other settings.

Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
Jason M. Altschuler
Kunal Talwar Apple ktalvar@apple..om
MIT jasonalt@mit. edu
Abstract
A central issue in machine learning is how train models on sensitive user data. Industry has widely adopted simple algorithm: Stochastic Gradient Descent with noise (a.k.a. Stochastic Gradient Langevin Dynamics). However, foundational theoretical questions about this algorithm's privacy loss remain open- even in the seemingly simple setting of smooth convex losses over bounded domain. Our main result resolves these questions: for large range of parameters, we characterize the differential privacy up to a constant. This result reveals that all previous analyses for this setting have the wrong gualitative behavior. Specifically, while previous privacy analyses increase ad infinitum in the number of iterations, show that after a small burn-in period, running SGD longer leaks further privacy. Our analysis departs from previous approaches based on fast mixing, instead using techniques based on optimal transport (namely, Privacy Amplification by Iteration) and the Sampled Gaussian Mechanism (namely, Privacy Amplification by Sampling). Our techniques readily extend to other settings
1 Introduction
Convex optimization is a fundamental task machine learning. When models are learnt on sensitive data, privacy becomes a major concern motivating large body of work on differentially private convex optimization [3, 4 g [3 19 21 30). In practice, the most common approach for training private models NOISY-SGD. i.e., Stochastic Gradient Descent with noise added each iteration. This
algorithm is simple and natural, has optimal utility bounds 3 4 and is implemented mainstream machine learning platforms such Tensorflow (TF Privacy) 1 Py Torchh (Opacus) (35] and JAX (6).
Yet, despite the simplicity and ubiquity of this NOISY-SGD algorithm, we do not understand basic questions about its privacy loss -i.., how sensitive the output of NOISY-SGD is with respect the training data. Specifically:
Question 1.1. What the privacy loss of NOISY- SGD as a function of the number of iterations?
Even in the seemingly simple setting of smooth convex losses over bounded domain, this funda- mental question has remained wide open. In fact, even more basic questions are open:
Question 1.2. Does the privacy loss of NOISY- SGD increase ad infinitum in the number of iterations?
The purpose of this paper is to understand these fundamental thcoretical questions. Specifically, resolve Questions [.I and 1.2 by characterizing the privacy loss of NoISY-SGD up to a constant factor in this (and other) settings for large range of parameters. Below, we first provide context by describing previous analyses SI.I and then describe our result in 1.2 and techniques in $
The Supplementary Material contains full version of this paper with proofs and more discussion.
Throughout, we follow the literature by writing "privacy loss" to refer to the differential privacy parameters.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Previous approaches and limitations
Although there is a large body of research devoted to understanding the privacy loss of NOISY-SGD, all existing analyses have (at least) one of the following two drawbacks.
Privacy bounds that increase ad infinitum. One type of analysis approach yields upper bounds on the DP (resp.. Rényi DP) that scale as vT (resp., T). This includes the original analyses of NOISY-SGD, which were based on the techniques of Privacy Amplification by Sampling and Advanced Composition 2 3], as well as alternative analyses based on the technique of Privacy Amplification by Iteration [12]. A key issue with these analyses is that they increase unboundedly in the number of iterations T. This limits the number of iterations that NOISY-SGD can be run given a reasonable privacy budget, typically leading to suboptimal optimization error in practice. Is this a failure of existing analysis techniques or an inherent fact about the privacy loss of NOISY-SGD?
Privacy bounds that apply for large 7 and require strong additional assumptions. The second type of analysis approach yields convergent upper bounds on the privacy loss, but requires strong additional assumptions. This approach is based on connections to sampling. The high-level intuition is that NOISY-SGD is a discretization of a continuous-time algorithm with bounded privacy loss. Specifically, NoISY-SGD can be interpreted as the Stochastic Gradient Langevin Dynamics (SGLD) algorithm 33, which is discretization of continuous-time Markov process whose stationary distribution is equivalent to the exponential mechanism (23 and thus is differentially private under certain assumptions.
However, making this connection precise requires strong additional assumptions and/or the resolution of longstanding open questions about the mixing time of SGLD (see $T1.4 for details). Only recently did a large effort in this direction culminate in the breakthrough work by Chourasia et al. [ which proves that full batcl Langevin dynamics (a.k.a., NOISY-GD rather than NOISY-SGD) has a privacy loss that converges as T + oo in this setting where the smooth losses are additionally assumed to be strongly convex.
Unfortunately, the assumption of strong convexity seems unavoidable with current techniques. Indeed, in the absence of strong convexity, it is not even known if NoISY-SGD converges to private stationary distribution, let alone this convergence occurs in a reasonable amount of time. (The tour-de-force work 7 shows mixing in (large) polynomial time, but only in total variation distance which does not have implications for privacy.) There are fundamental challenges for proving such a result. In short, SGD is only weakly contractive process without strong convexity, which means that its instability increases with the number of iterations [18)or in other words, it is plausible that NOISY-SGD could run for long time while memorizing training data, which would of course mean it is not privacy-presers optimization, is unclear if the privacy loss of NOISY-SGD should even remain bounded; i.e., is unclear what answer one should even expect for Question 1.2
algorithm. As such, given state-of-the-art analyses in both sampling and
let alone Question I.1
1.2 Contributions
The purpose of this paper is to resolve Questions 1.1 and 1.2
To state our result requires first recalling the parameters of the problem. Throughout, we prefer to state our results in terms of Rényi Differential Privacy (RDP); these RDP bounds are easily translated to DP bounds, as mentioned below in Remark 1.4 See the preliminaries section $2 for definitions and background on privacy.
We consider the basic NOISY-SGD algorithm run on dataset X FI where each x; defines a convex, L-Lipschitz, and M M-mmooth loss function f.(-) on a convex set KC of diameter D. For any step size 17 & 2/M, batch size b, and initialization wn é K. we iterate T' times the update
Wh+1 Nx[w (G Z.)],
where G, denotes the average gradient vector a random batch of size b, Z, N(0,02Ia is an isotropic Gaussian, and II denotes the Euclidean projection onto IC.
Recentlyy Ye and Shokri 3 and Ryffel et al. 27 in works concurrent to the present paper, extended the result of ( SGLD by removing the full batch assumption; we also obtain the same result by direct extension of our (completely different) techniques, see the Supplementary Materials. Note that both papers [27 34] still require strongly convex losses, and in fact state in their conclusions that removing this assumption is an open problem that "would pave the way for wide adoption by data scientists." " Our main result resolves this question.

---

Rényi Differential Privacy of Noisy-SGD SGD
Legend
existing results (privacy leaks infinitum)
result
leakage after T
1
Iterations T
Dn
Figure 1: Even the basic setting of smooth convex optimization over a bounded domain, exist- ing implementations and theoretical analyses of NoISY-SGD the standard algorithm for private optimization- leak privacy ad infinitum as the number of iterations T increases. Our main result establishes that after small burn-in period of (nn) iterations, there is further privacy loss. For simplicity, this plot sets L= 1 (wlog by rescaling), a = O(1) (the regime in practice), and omits logarithmic factors; the main text for precise (and optimal) dependence all parameters.
Known privacy analyses of No1sY-SGD give an (a,E)-RDP upper bound of
8 aL?
T
(1.I)
2202
which increases ad infinitum as the number of iterations T characterization the privacy loss, answering Question T.I] This result also answers Question 1.2 and shows that previous analyses have the wrong qualitative behavior: after small burn-in period of
2
3 12
Our main result is a tight
( DD) Tn iterations, NOISY-SGD leaks no further privacy. See Figure
Theorem 1.3 (Informal statement of main result: tight characterization of the privacy of NOISY-SGD).
For large range of parameters, NOISY-SGD satisfies (ox,))-Rl E-RDP for
aL? min T,
Dn
(1.2)
n²o²
Im
and moreover this bound is tight up to constant factor.
Observe that the privacy bound in Theorem 1.3 is identical to the previous bound [.11 when the number of iterations T is small, but stops increasing when T> T. Intuitively, T can be interpreted as the smallest number of iterations required for two NOISY-SGD processes run on adjacent datasets to, with reasonable probability, reach opposite ends of the constraint set In other words, T effectively the smallest number of iterations before the final iterates could be maximally distinguishable.
To prove Theorem we show a matching upper bound (in $3) and lower bound (in $4) These two bounds are formally stated Theorems 3.1 and 4.1 respectively. See $1.3 for an overview of our techniques and how they depart from previous approaches.
We conclude this section with several remarks about Theorem
Remark 1.4 (Tight DP characterization). While Theorem 1.3 characterizes the privacy loss of NOISY-SGD in terms of RDP, our results can be restated in terms of standard DP bounds. Specifically, by standard conversion from RDP to DP (25) Proposition 1]. if å is not smaller than exponentially small -bo/nn and if the resulting bound is $ 1, it follows that NoISY-SGD is (c, 8DDP DD for
L no
Dn
8
log 1/8.
(1.3)
Lm
A matching DP lower bound is proved along the way when we establish our RDP lower bound in
'Details: NOISY-SGD updates on adjacent datasets differ by at most nL/b if the different datapoint is in the current batch (i.e.. with probability b/n), and otherwise are identical. Thus, in expectation and with high probability, it takes T'x (Dn)/(nL) iterations for the two ROISY-SGD processes differ by distance D.

---

Discussion of assumptions in Theorem 1.3
Boundedness, All previous privacy analyses are oblivious to any sort of diameter bound and therefore unavoidably increase ad infinitum c.f. our lower bound in Theorem 1.3 Our analysis is the first to exploit boundedness: whereas previous analyses can only argue that having smaller constraint set does not worsen the privacy loss, we show that this strictly improves the privacy loss, in fact making it convergent as T co. See the techniques section 1.3 We emphasize that this diameter bound is a mild constraint. Indeed, every utility/otimmzzationn guarantee for (non-strongly) convex losses inevitably has similar dependence, simply due to the difference between initialization and optimum. We also mention that one can solve an unconstrained problem by solving constrained problems with norm bounds, paying only a small logarithmic overhead on the number of solves and a constant overhead in the privacy loss using known techniques [22]. Moreover, in many optimization problems, the solution set is naturally constrained either from the problem formulation or application.
Smoothness. The smoothness assumption on the losses can be relaxed by running NoISY-SGD on smoothed version of the objective. This can be done using standard techniques, e.g., Gaussian convolution smoothing [12 $5.5), or Moreau-Yousida smoothing by replacing gradient steps with proximal steps 4 $4].
Convexity, Convexity appears to be essential for privacy bounds that do not increase ad infinitum in T. Our analysis uses convexity in an essential way to ensure that NoISY-SGD is a contractive process. However, convexity is too restrictive when training deep networks, and it is an interesting open question if the assumption of convexity be relaxed. Any such result appears to require entirely new techniques-if even true. The key technical challenge is that for any iterative process whose set of reachable fixed points is non-convex, there will be non-contractivity at the boundary between basins of attraction- and this precludes arguments based on Privacy Amplification by Iteration.
Lipschitzness. This assumption can be safely removed since smoothness and boundedness imply Lipschitzness for I. = M. We write our result in this way in order to clearly isolate where this dependence comes from, and also because the Lipschitz parameter L may be much better than M.
Mild assumptions on parameters. The lower bound makes the mild assumption that the diameter D of the decision set is neither asymptotically smaller than the movement size from one gradient step, nor asymptotically smaller than the standard deviation from T random increments of Gaussian noise N(O, vy"o" so that the noise does not overwhelm the learning. The upper bound uses the technique of Privacy Amplification by Sampling, and thus inherits an upper bound assumption on a from the analysis of the Sampled Gaussian mechanism, as well as mild bounds on the batch size that only affect the complete range {1,...,r) n up to a constant factor assuming that the noise a is not so small that it is asymptotically overwhelmed by one gradient step. These restrictions neither affect numerical bounds which can be computed for any a and b (see 2.33.. nor do they affect the asymptotic (e, 6DD bounds in most parameter regimes of interest.
Extensions. Our analysis techniques extend to related settings, as will be investigated in an extended journal version of this paper. We mention here that if the convexity assumption the losses is replaced by strong convexity, then NOISY-SGD enjoys better privacy. Specifically, Theorem 1.3 extends identically except that the threshold T for further privacy loss improves from linear to logarithmic in n. namely Ö(k) where x denotes the condition number of the losses. This matches the
independent results of (27 34 (see Footnote 2 and uses completely different techniques from them.
1.3 Techniques
Upper bound on privacy. Our analysis technique departs from recent approaches based on fast mixing. This allows us to bypass the many longstanding technical challenges discussed in $I.1
Instead, our analysis combines the techniques of Privacy Amplification by Iteration and Privacy Amplification by Sampling. As discussed in IT.I previous analyses based on these techniques yield loose privacy bounds that increase ad infinitum in T. Indeed, bounds based on Privacy Amplification by Sampling inevitably diverge since they "pay" for releasing the entire sequence of T iterates, each of which leaks more information about the private data [2] 3. Privacy Amplification by Iteration avoids releasing the entire sequence by directly arguing about the final iterate; however, previous
*For strongly convex losses, boundedness is unnecessary for convergent privacy; the Supplement.

---

arguments based on this technique are unable to exploit a diameter bound on the constraint set, and therefore inevitably lead to privacy bounds which grow unboundedly in T
Our analysis is based on the observation that when the iterates are constrained to a bounded domain, we can combine the techniques of Privacy Amplification by Iteration and Privacy Amplification by Sampling in order to only pay for the privacy loss from the final T = =(Dn))) (Ln) iterations. Specifically, we partition the execution of NOISY-SGD into the initial T 'T' iterations and the final T iterations. Recall that to show privacy, we must show that NOISY-SGD produces a similar output run on given dataset or another dataset that is changed slightly. On one hand, if the partially learned model wr-T were fixed, then the privacy loss from the last T iterations could be bounded by the standard analysis of NOISY-SGD based on Privacy Amplification by Sampling and Advanced Composition. On the other hand, irrespective of the input dataset, wr-F lies in a set of diameter D. If the remaining iterations were now run on the same dataset, the Privacy Amplification by Iteration Argument can be used to show that the algorithm "forgets" this initial displacement by up to D. (This formalized in Proposition 3.2, which is the first Privacy Amplification by Iteration argument that is not vacuous as T + oo). In other words, we can control the privacy loss if we change the dataset either in the first T T iterations or in the final T iterations. At a high-level, our analysis proceeds by carefully running these arguments in parallel.
Lower bound on privacy. We construct two adjacent datasets on which the NOISY-SGI iterates are generated by random walks one symmetric, one biased const--ind within an interval of length D. In this way, we reduce the question of how large is the privacy loss of NoISY-SGD, the question of how distinguishable is a constrained symmetric random walk from a constrained biased random walk. The core technical challenge is that the distributions of the iterates of these random walks are intractable to reason about explicitly- due to the highly non-linear interactions between the projections and random increments. Briefly, our key technique here is a way to modify these processes so that one hand, their distinguishability is essentially the same, and the other hand, no projections occur with high mobability-alloowe us to explicitly compute their distributions and thus also their distinguishabiliityy Details in $4
1.4 Other related work
Private sampling. The mixing time of (stochastic) Langevin Dynamics has been extensively studied in recent years starting with I. and other more recent works have analyzed mixing in other notions of distance. From the point of view of privacy, more stringent notions of mixing are needed, and mixing in Renyi divergence was studied by Vempala and Wibisono [32] and Ganesh and Talwar [13]. In addition to the aforementioned works, several recent works have studied algorithms for sampling from the distribution exp(= Σ, f((w) or its regularized versions from a privacy viewpoint. 24 proposed mechanism of this kind that works when may be unbounded and showed that it satisfies (s, d)-P. Recently, 17 gave better privacy bounds for such a regularized exponential mechanism, and designed an efficient sampler based only function evaluation. (16) showed number of results about the continuous Langevin Diffusion, showing that it gives optimal utility bounds for different variants of private optimization problems with different parameters.
As alluded to in ST.II there are several core issues with trying to prove DP bounds for NOISY-SGD by directly combining "fast mixing" bounds with "private once mixed" bounds. First, mixing results typically do not apply, e.g., since DP requires mixing in stringent divergences like Rényi, or because realistic settings with constraints, stochasticity, and lack of strong convexity are difficult to analyze- indeed, understanding the mixing time for such settings is a challenging open problem. Second, even when fast mixing bounds do apply, directly combining them with "private once mixed" bounds unavoidably leads to DP bounds that are loose to the point of being essentially useless (e.g., the inevitable dimension dependence in mixing bounds to the stationary distribution of the continuous- time Langevin Diffusion would lead to dimension dependence in DP bounds, which should not occur-as we show). Third, even if Markov chain were private after mixing, one cannot conclude from this that it is private beforchand-indeed there are simple Markov chains which are private after mixing, yet are exponentially non-private beforehand [4].
Utility bounds. In the field of private optimization, one separately analyzes two properties of algorithms: (i) the privacy loss as a function of the number of iterations, and (ii) the utility (a. optimization error) as function of the number of iterations. These two properties can then be
5

---

combined to obtain privacy-utility tradeoffs. The purpose of this paper is to completely resolve (i); this result can then be combined with any bound on (ii).
Utility bounds for SGD are well understood 28 and these analyses have enabled understanding
utility bounds for NoISY-SGD in empirical S and population 4 settings. However, there is big difference between the minimax-optimat utility bounds in theory versus what is desired in practice. Indeed, while in theory single pass of NOISY-SGD achieves the minimax-optimal population risk 13. in practice NOISY-SGD benefits from running longer to get more accurate training. In fact, this divergence is even true and well well-documented for non- non-private SGD as well, where one epoch is minimax-opiin -ottimal in theory, but in practice more epochs help. Said simply, this is because typical problems are not worst-case problems (i.e., minimax-optimat theoretical bounds are typically not representative of practice). For these practical settings, in order to run NOISY- longer, it is essential to have privacy bounds which do not increase ad infinitum. Our paper resolves this.
Preliminaries
In this section, we recall relevant preliminaries about convex optimization ($2.1) differential privacy (2.2), and two by-now-standare techniques for analyzing the privacy of optimization algorithms-
namely, Privacy Amplification by Sampling (..3) and Privacy Amplification by Iteration ($2.4).
Notation. We write Px to denote the law of a random variable X, and IP Px to denote the law of X given the event Y y. We write Zs:r as shorthand for the vector concatenating ....... ZT. We write s denote the pushforward of distribution j under (possibly random) function f. i.e. the law of f(X) where X ~ J.. We write d (1 A) to denote the mixture distribution that is with probability and with probability 1 1- x. We write A(X) to denote the output of an algorithm A run on input X;; this is a probability distribution if A is randomized algorithm.
2.1 Convex optimization
Throughout, the loss function corresponding to data point v; or x is denoted by fc or f/-. respectively, While the dependence on the data point is arbitrary, the loss functions are assumed to be convex in the argument w E K. (a.k.a., the machine learning model we seek to train). Throughout, the set K. of possible models is a convex subset of Rd. In order to establish both optimization and privacy guarantees, two additional assumptions are required on the loss functions. Recall that a differentiable function g K Ed is: L-Lipschitz if [g(w) g(w') Ll[w - w'll for all w, w/ K.; and M M-smooth if (V) Vg(w")) < MM || --- w'll for all w, w' e K.
2.2 Differential privacy and Rényi differential privacy
In order to prove DP guarantees, we work with the related notion of Rényi Differential Privacy (RDP) introduced by 255. since RDP more amenable to our analysis techniques and is readily converted to DP guarantees (25 Proposition 1]. RDP measures how distinguishable the output of an algorithm when run on two "adjacent" datasets-i.n two datasets which differ on most one datapoint- in Rényi divergence. We therefore first recall the definition of Rényi divergence.
Definition 2.1 (Rényi divergence). The Rényí divergence between probability measures p. and of order a e (1, 00) is D., (14 || v)) a-1 log ʃ (m(z)/v(z)) (())d, if < v, and co otherwise. Here 0/0= 0 and z/0 = oo for x > 0. The Rényi divergences of order a E oo) are defined by continuity. Definition 2.2 (Rényi Differential Privacy). A randomized algorithm A satisfies (a,E)-RDPP if D. (A(x) A(X')) & e for any two adjacent datasets X,X'
Following, we recall two basic propertics of RDP that we use in our analysis. Proofs can be found, e.g., in [31 Theorem 9] and [25] Proposition 3], respectively.
Lemma 2.3 Prost-groessiing property of Rényi divergence). For any Rényi parameter a 1, any (possibly random) function h. and any probability distributions p.v.
Da (h hyv) < Da (H v).

---

Lemma 2.4 (Strong composition for RDP). For any Rényi parameter & 1, and any two sequences of random variables X1, XI.....X .x and I..... Yb.
Da (Pxua PY sup Do (PxpXin-- PyMMa)))ma)))
212-1
2.3 Privacy Amplification by Sampling
A core technique in the DP literature is Privacy Amplification by Sampling (20]. which quantifies the idea that private algorithm run on small random sample of the imput become more private. We recall convenient statement of this from [26, Theorem 11] in terms of the RDP of the "Sampled Gaussian Mechanism" (which is a composition of subsampling and additive Gaussian noise).
Definition 2.5 (Rényi Divergence of the Sampled Gaussian Mechanism). For Rényi parameter a 1. mixing probability E (0, 1), and noise parameter a 0, define
Sa (a = Da (N(O, (1- (1-9))((,0))) (N(
Lemma 2.6 (Bound on Rényi Divergence of the Sampled Gaussian Mechanism). Consider Rényi parameter 1, mixing probability q (0, 1/5). and noise level R 4. If a a² (q. then
S. (, o) 20u2/o²
This bound restricts to Rényi parameter at most a' (), which is defined to be the largest satisfying a & M /2 log(o* and a (M2 /2 log [o /)M log(gax) + 1/(20²)), where M == log(1 (/(1((1111))11// 1)). While we use Lemma 2.6 prove the asymptotic bounds in Theorem 1.3 we emphasize that i) our bounds can computed numerically for any a 1, and ii) this upper bound does not preclude a from the typical parameter regime of interest, see the discussion in $..
2.4 Privacy Amplification by Iteration
The Privacy Amplification by Iteration technique of [12] bounds the privacy loss of an iterative algorithm without "releasing" the entire sequence of iterates- iterates-unlike unlike arguments based on Privacy Amplification by Sampling, c.f., $1.3 This technique applies to processes generated by Contractive Noisy Iteration (CNT). We begin by recalling this definition, albeit in a slightly more general form that allows for two differences. The first difference is allowing the contractions to be random; albeit simple, this generalization is critical for analyzing NOISY-SGD because a stochastic gradient update random. The second difference is that we project each iterate; this generalization is solely for convenience as it simplifies the exposition F)
Definition 2.7 (Contractive Noisy Iteration). Consider a (random) initial state Xo Rdd a sequence of (random) contractions de : Rd IRd, sequence of noise distributions & and a convex set K. The Projected Contractive Noisy Iteration CNI(Xo, { [E),, KC) is the final iterate XT of the process
X drot (X+) Ze.1;
where Ze,1 is drawn independently from E1.1-
Proposition 2.8 (Origina PABI bound), Let XT and X/- denote the outputs of CNI(Xo. (0r), (5)) K)) and CNI(Xo, (Øt), (E)) K)) where & N(0, Let Let 1| &illo and consider any sequence a1...., aT such that 2 == Et (s: a.) is non-negative for all t and satisfies 2T Then
Da (Px Px²
t=1 o?
'Since projections are contractive, these processes could be dubbed Contractive Noisy Contractive Processes (CNCI); however, use Definition[2.7] 2.7Jas it more closely mirrors previous usages of CNL. Alternatively, since the composition of contractions is contraction. the projection
be combined with di obtain bona fide CNI: however, this requires defining auxiliary shifted processes which leads more complicated analysis.
"Strictly speaking, Proposition 2.8 is a generalization of (12) Theorem 22] since it allows for randomized contractions and projections in the CNI. See the Supplementary Materials for proof.
7

---

3 Upper bound on privacy
In this section, we prove the upper bound in Theorem 1.3
The formal statement of this result is as follows; see $1.2 for a discussion of the mild assumptions on the parameters.
Theorem 3.1 (Privacy upper bound for NOISY-SGID. Let TRd be convex set of diameter D, and consider optimizing convex losses over K. that are I.-Lipschitz and M-smooti Consider any number of iterations T, dataset size n N, batch size b & n, stepsize ri < M/M, noise parameter a > and initialization Wa E I such that < n/5 and bo > 8/2L. Then NOISY- SGG satisfies (a, ba and if a a 2VEL
aT? min
Dn Ln
E x
T,
n²
3.1 Privacy Amplification by Ittration bounds that are not vacuous as T oo
Recall from the preliminaries section $2.4 that PABI arguments, while tight for small number of iterations T, provide vacuous bounds as T + oo (c.f., Proposition 2.8 The following proposition overcomes this by establishing privacy bounds which are independent of the number of iterations T. This result only requires additionally making the mild assumption that the CNI iterates bounded.
Proposition 3.2 (New PABI bound that is not vacuous as T + co). Let XT, X'y, and be as in Proposition 2.8 Consider any {O....,T'
T 13 and sequence 07+1y..., ar such that 2x == + Eier+1 (8: ai) is non-negative for all and satisfies zr 0. If KC has diameter D, then:
Da (Pxr F
< a Σ 2 t=T+1 of
of
Proof idea. We first recall the basic idea of the proof of the original PABI bound (Proposition) 2.8). Briefly, that proof uses as a potential certain shifted Rényi divergence, which allows for uncertainty in one of the two distributions as measured in optimal transport distance (making it geometrically aware). The original argument bounds the shifted divergence at iteration T (which is precisely the RDP in question), by the shifted divergence at iteration T 1, and so to the shifted divergence at iteration (which vanishes since NOISY-SGD always has the same initialization). In this way, by keeping track of the privacy loss each iteration, PABI bounds the RDP. The main idea behind Proposition 3.2 is to change this argument by simply stopping the induction earlier. Specifically, unroll to iteration 7, and then boundedness of the iterates to control the shifted divergence that intermediate time r. For brevity, the proof is deferred to the Supplementary Materials.
We remark that this new version of PABI uses the shift in the shifted Rényi divergence for a different purpose than previous work: rather than just using the shift to bound the bias incurred from updating on two different losses, here we also use the shift to exploit the boundedness of the constraint set.
3.2 Proof sketch of Theorem 3.1 (full details in the Supplementary Materials)
Step 1: Coupling the iterates. Suppose = {z1, ... Tx and X' (a'..... ........,,,, ,41 are adjacent datasets; that is, they agree x; x on all indices i E [r]] > {E*} except for at most one index E [n]. Denote the corresponding loss functions by f. and f/ where f, f except possibly fer f... Consider running NoISY-SGD on either X' or X" for T iterations call the resulting iterates {Wa) and (W;) respectively-wiieee where we start from the same point é K. and couple T-1 and the random noise in each iteration. That is,
the sequence of random batches {B.)
W 1lx[W, y Σ vf((W,) Y, 2.]
ieB
W = [xx[W/ y Σ V)((W))) + Y, z
for all T where we have split the noise into terms Y ~ N( Z. ~(..000'0)) 2 ~
(W/) (WW)] L for any 01,02 satisfying of = (we set 01 = =2 =======//// a/V2 later for asymptotics). words, this noise-splitting lets us use the noise for both the Privacy Amplification by Sampling and Privacy Amplification by Iteration arguments below.
8

---

Importantly, notice that in the definition of W the gradient is taken w.r.t. loss functions corre- sponding to data set X' rather than X'; this is corrected via the bias in the noise term Z/. Notice also
that this bias term is only realized (i.e., 7: is possibly non-centered) with probability 1 - b/n because the probability that i* is in a random size-b subset of [n] is byn.
Step 2: Interpretation as conditional CNI sequences. Observe that conditional on the event that Ze Zi are equal (call their value 2t), then
W+1 = ITy (W)) + Y]]
W = (T. Yr] ieB,
where
(r(w) w Σ Vf((w) 2
(3.1)
This gives us CNI since Φe contractive. (This contractivity follows from the fact that stochastic gradient update on a smooth convex function is contractive; details in the Supplementary Materials.)
Step 3: Bounding the privacy loss. Recall that seek upper bound Da (Pw, || Pw;.). Let
(0............... (O..... T 1} be threshold parameter be chosen shortly. Then
D, (Pwr Pw;y) ) D. (Fwr.zrz (w......r
< Da (F P2ioo-) + Dup Z
Pwyizzg Za,z )-=)
(3.2)
Above, the first step is by the post-processing inequality for the Rényi divergence (Lemma 2.3 ). and the second step is by the strong composition rule for the Rényi divergence (Lemma 2.4
Step 3a: Bounding the first term in (.2), using Privacy Amplification by Sampling. In words,
this the privacy loss from releasing T noisy gradients. This can be bounded by Privacy Amplification by Sampling (Lemma 2.6) and Advanced Composition (Lemma 2.4 via a standard argument
2 This yields the bound (T - 7 S,, ( boz)
2L ): full details in the Supplementary Materials.
Step 3b: Bounding the second term in (.2). using Privacy Amplification by Iteration. From step 2. we know that conditional on the event that Z, Z; for all t r, then (We and {W7) projected CNI (c.f., Definition 2.7} with respect to the same update functions. Thus we may apply the new Privacy Amplification by Iteration bound (Proposition 3.2) with 8 0 and a D/(T- to obtain the bound aD /(2))² (T
Step 4: Putting the bounds together. By plugging into that NOISY-SGD is (a, (DDP for
3.2 the bounds in Steps 3a-3b, we conclude
(T- Sa
boz
E E min TE(
(3.3)
2L
2n 2T -
By bounding Sa
bo
2L using Lemma 2.6. setting = 02 : setting 7 T
and otherwise using the simple bound which scales linearly in T, and simplifying. obtain the desired privacy bound on e, proving Theorem 3.1 full details in the Supplementary Materials.
4 Lower bound on privacy
In this section, we prove the lower bound in Theorem 1.3 This is stated formally below and holds even for linear loss functions in one dimension, in fact even when all but one of the loss functions are zero. See 1.. for a discussion of the mild assumptions on the diameter. Below let T := 0.75 Dn. Lxj
Theorem 4.1 (Privacy lower bound for NOISY-SGD). There exist universal constants CD. Ca. Co. and a family of L-Lipschitz linear functions over the interval = [-D/2, D/2] such that the following holds. Consider running NOISY-SGD from arbitrary initialization Wy with any parameters satisfying D > CDnL and o² < c2 TT) Then NOISY-SGI not (ā,e)-RDP for
aL? min (T. T.T...
E Ca. n²0²
(4.1)

---

Construction. Consider datasets X' (.i.....,.a 2n 2n) and X' = __ 2n-1 2nd which differ only on z'y, and corresponding functions which are all zero f.(.) =... fn(() [,(()) T(D- w.). Clearly these functions are linear and T-LLipschitz. The intuition behind this construction is that running NoISY-SGD on X' or X' generates a random walk that is clamped to stay within the interval Kut with the key difference that running NoIsY- on dataset X' generates a symmetric random walk (wz), whereas running NOISY-SGD on dataset X' generates a biased random walk { that biases right with probability b/n each step. That is,
except for
We+1 = Ik[ + Ze]
and
w/11 II W Vi Zi]
[
where the processes are initialized at wo = w/ = O, each random increment Ze ~ [O. 1j²a") is an independent Gaussian, and each bias Y, nL/b with probability b/n and otherwise
Key obstacle for analysis: intractability of reasoning about the iterates' distributions. The high-level intuition behind this construction is simple state: the bias of the random walk {w{} makes it distinguishable (to the minimax optimal extent, as we show) from the symmetric random walk {wr]. However, making this intution precise is challenging because the distributions of the iterates Wr. w/ are intractable to reason about explicitly- due to the highly non-linear interactions between the projections and the random increments. Thus we must establish the distinguishabiliyy of wr, w in way that avoids reasoning explicitly about their distributions. We show how to do this in the Supplementary Materials and give a full proof of Theorem 4.1 there.
5 Discussion
The results of this paper suggest several natural directions for future work:
Clipped gradients? NOISY-SGD implementations sometimes clip gradients to ensure small norms 2
For generalized linear models, the clipped gradients are gradients of an auxiliary convex loss [29). so results can be applied directly. However, in general, clipped gradients do not correspond to gradients of a convex loss, in which case our results (as well as all other works in the literature that aim at proving convergent privacy bounds) do not apply. Can this be remedied?
Average iterate? Can similar privacy guarantees be established for the average iterate rather than the last iterate? There are fundamental difficulties with trying to proving this: indeed, the average iterate is provably not as private for NorSY-CSGD 4
Adaptive stepsizes? Can similar privacy guarantees be established for optimization algorithms with adaptive stepsizes? The main technical obstacle is how control the privacy loss from how past iterates affect the adaptivity in later iterates. This appears to preclude using our analysis techniques, at least in their current form.
Beyond convexity? Convergent privacy bounds break down without convexity. This precludes appli- cability to deep neural networks. Is there any hope of establishing similar results under some sort of mild non-convexity? Due to simple non-convex counterexamples where the privacy of NoISY-SGD diverges, any such extension would have to make additional structural assumptions on the non- convexity (and also possibly change the NoISY-SGD algorithm), although it is unclear how this would even look. Moreover, this appears to require significant new machinery as our techniques are the only known way to solve the convex problem. and they break down in the non-convex setting (see also the discussion in (T.2).
General techniques? Can the analysis techniques developed in this paper be used in other settings? Our techniques readily generalize to any iterative algorithm which interleaves contractive steps and noise convolutions. Such algorithms are common in differentially private optimization, and it would be interesting to apply them to other variants of NOISY-SGD.
Acknowledgments and Disclosure of Funding
We are grateful to Hristo Paskov for many insightful conversations. This work was done in part while JA was an intern at Apple during Summer 2021. JA was also supported in part by NSF Graduate Research Fellowship 1122374, TwoSigma PhD Fellowship, and an NYU Faculty Fellowship.
10

---

References
[1] Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving. Michael Isard, et al. TensorFlow: system for large-scale machine learning. In Symposium on Operating Systems Design and Implementation, pages 265-283, 2016.
[2] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Conference on Computer and Communications Security, pages 308 308-318,74 2016.
[3] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Symposium on Foundations of Computer Science, pages 464-473.
IEFE, 2014.
[4] Racf Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex opti- mization with optimal rates. In Advances Neural Information Processing Systems, volume 32, pages 1122--1129, 2019.
[5] Raef Bassily, Cristohal Guzman, and Anupama Nandi. Non-Fuclidean differentially private stochastic convex optimization. arXiv:2 0/278, 2021.
[6] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: compos- able transformations of Python+NumPy programs, 2018. URL //tpttt:://gttbbbbb
http://tttuuuuuooooogggggo/// com joogle/jxx
[7] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from log-concave distribution with Projected Langevin Monte Carlo. Discrete & Computational Geometry,599 59(4)7757-783 2018.
[8] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12:1069-1109 2011.
[9] Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of Langevin diffusion and noisy gradient descent. In Advances in Neural Information Processing Systems, volume 34, pages 14771-14781, 2021.
[10] Amak Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society: Series (Statistical Methodology), 79, 6 2017.
[11] Alain Durmus and Eric Moulines. High-dimensional Bayesian inference via the unadjusted Langevin algorithm. Bernoulli, 25:2854-2882. 11 2019.
[12] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In Symposium on Foundations of Computer Science, pages 521-532. IEEE, 2018.
[13] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Symposium on the Theory of Computing, pages 439-449, 2020.
[14] Arun Ganesh and Kunal Talwar. In Personal communication.
[15] Arun Ganesh and Kunal Talwar. Faster differentially private samplers via Rényi divergence analysis of discretized Langevin MCMC. In Advances in Neural Information Processing Systems, volume 33, pages 7222-7233, 2020.
[16] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Langevin diffusion: An almost universal algorithm for private Fuclidean (convex) optimization. arXiv:2204.01 58552, 2022.
[17] Sivakanth Gopi, Yin Tat Loc, and Daogao Liu, Private convex optimization via exponential mechanism. arXiv:2203.0m .002663v,, 2022.
[18] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability stochastic gradient descent. International Conference on Machine Learning, pages 1225-1234, 2016.
[19] Prateek Jain and Abhradeep Guha Thakurta. (Near) dimension independent risk bounds for differentially private learning. In International Conference on Machine Learning, pages 476-484. PMLR, 2014.
[20] Shiva Prasad Kasiviswanathan, Homin K Lec, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we leam privately? SIAM Journal on Computing, 40(3):793 826,, 2011.
[21] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Computational Learning Theory, pages 25-1, 2012.
[22] Jingeheng Liu and Kunal Talwar. Private selection from private candidates. In Symposium on Theory of Computing, pages 298-309, 2019.
[23] Frank McSherry and Kunal Talwar. Mcchanism design via differential privacy. In Symposium on Foundations of Computer Science, pages 94-103 2007.
[24] Kentaro Minami, Hitomi Arai, Issei Sato, and Hiroshi Nakagawa. Differential privacy without sensitivity. In Advances in Neural Information Processing Systems, volume 29, 2016.
11

---

[25] Ilya Mironov. Rényi differential privacy. In Computer Security Foundations Symposium, pages 263-275. IEEE, 2017.
[26] Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the Sampled Gaussian Mcchanism. arXiv preprint arXiv: 10530, 2019.
[27] Theo Ryffel, Francis Bach, and David Pointcheval. Differential privacy guarantees for stochastic gradient Langevin dynamics. arXiv:2201. 1980, 2022.
[28] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In Conference on Computational Learning Theory, 2009.
[29] Shuang Song, Thomas Steinke, Om Thakkar, Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private GLMs. In International Conference on Artificial Intelligence and Statistics, pages 2638 2646. PMLR, 2021.
[30] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly optimal private Lasso. Advances Neural Information Processing Systems, volume 28, pages 3025-3033, 2015.
[31] Tim Van Erven Peter Harremos. Rényi divergence
Kullback-Leibles divergence. IEEE Transactions
on Information Theory, 60(7):3797-3820, 2014.
[32] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In Advances Neural Information Processing Systems 32, pages 8092-8104, 2019.
[33] Max Welling and Yee Whye Tch. Bayesian learning via stochastic gradient Langevin dynamies. In International Conference on Machine Learning, page 181-688, Madison, WI, USA, 2011.
[34] Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). arXiv:2203.05366 2022.
[35] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. Opacus: User-friendly differential privacy library in PyTorch, arXiv preprint arXiv:2109.1222 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] On the contrary, the main results of this paper have positive socictal impacts: show that machine learning models can trained for longer while still protecting the privacy of sensitive user data.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (cither in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A].
(d) Did you include total amount of compute and the type resources used (e.g.. type GPUs, internal cluster, or cloud provider)? [N/A].
If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 'r us- ing/eurating? [N/A]
12

---

(e) Did discuss whether the data you are using/curating contains personally identifiable informa- tion offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable?
[N/A]
(b) Did you descrihe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "hdUjnppFgtk", "reviewer": "Reviewer_iTwN", "summary": "This work proposes an asymptotic privacy bound analysis when $T$ is large in Noisy SGD (SGLD) for convex functions. The results show when the number of iterations $T$ increases at the start, the privacy decreases at a linear rate. After a burn-in period, the privacy is bounded by a constant, and running SGD longer leaks no further privacy.  Some techniques based on PABI are also proposed in the analysis. The work also shows the tightness with a lower bound construction based on the trace analysis of random walk, which makes the proposed magnitude more convincing.", "questions": "Some questions:\n1. Can the proposed framework be extended to the bounded non-convex function with a regularizer, like [Li et al, 2019] for SGLD (Also mentioned in [Chourasia et al. 2021]).\n2. How can the proposed bounds be used/ help the cost minimization and privacy mechanism design?\n3. How a $D$ determined for the real cases? Is $D$ related to the dimension and the convergence of the convex problem? Will the convergence influence the privacy level?\n\n\nSome suggestions:\n1. Some simple examples/numerical studies can be provided to show the effectiveness of the proposed framework more intuitively.\n", "limitations": "The assumptions have been discussed in detail, showing the limitations of the work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The paper discusses the core problem in the Noisy-SGD analysis and provides a new asymptotic viewpoint for the privacy bound. Some new techniques are also proposed for the problem \n2. The paper is well-organized and some important points and proof sketches are shown in the main context with the detailed proof in the Supplement.\n3. Good and detailed sketches for the existing Noisy-SGD analysis.\n\nCons:\n1. The paper only discusses the function for convex cases, which simplifies the difficulties for analysis. More works might focus on the analysis in non-convex cases (like deep networks).\n2. The paper lacks some numerical studies to give more insights and verify the performance of the proposed framework.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "hGBYIi9ctD", "reviewer": "Reviewer_gSaZ", "summary": "The authors show that Noisy SGD achieves a privacy loss that does not grow indefinitely in the setting of convex optimization with smooth Lipchitz functions over a bounded set. The proof technique relies on privacy amplification by sampling and on amplification by iteration. Additionally, the authors also show a lower bound showing that the upper bound is tight up to a constant.", "questions": "No questions", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts: Paper is well written, easy to read, provides enough background on the problem and a good literature review. The result is also pretty cool since it shows that previous upper bounds for the privacy loss, where privacy scales indefinitely, exhibit the wrong qualitative behavior.\nIt looks like the only similar results (a bounded privacy loss) only hold in the case of smooth and strongly convex setting, so being able to relax strong convexity is significant. \nWeaknesses: I don’t have much to say here, I think it is a good paper.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dlaSSxgZNoS", "reviewer": "Reviewer_qRoi", "summary": "In this paper, authors show that running DP-SGD for a convex function on a bounded domain converges to a bounded privacy cost opposed to the classical composition results that grow to infinity as the number of iterations grow. Similar to Chourasia et al. 2021, authors assume that the internal state (i.e. the intermediate parameter values) are kept private and only the final iterate is released. Authors build a novel analysis, where they split the the parameter trace in two halves and analyse the privacy cost of these halves separately. This involves finding a new improved privacy amplification by iteration (PABI) result. Authors also present a lower bound result for the privacy guarantee.", "questions": "I don't have much to ask, since I found the proofs quite easy to follow. Couple of very minor things that caught my eye:\n- Lines 303-304: \"Notice also that this bias term is only realized with probability 1 − b/n because the probability that i∗ is in a random size-b subset of [n] is b/n.\", maybe I miss something, but I thought the noise is realized w.p. b/n\n- The bound in beginning of page 14 of supplement: I do understand that if you set $R=\\tilde{T}$, the summands inside the $\\min$ get equivalent and with larger $R > \\tilde{T}$ the latter term gets smaller and and former grows. However, I'm not quite sure, how do you form the last inequality. It almost seems like you only have the second term of the summand in the final expression, and the first has vanished somewhere.\n- I'm curious, could one use some adaptive step-size schemes like Adam with this final iterate release analysis? Or would the Adam cause some sort of side-channel privacy leak through the last gradients it uses in adapting the step-size?", "limitations": "There is not much discussion of the limitations, probably due to lack of space. I guess the authors could further discuss the limitations that the assumptions make. For example the assumption of bounded domain. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main result of the paper (the upper bound) is a significant finding. Although, Chourasia et al. 2021 already showed this type of behaviour of the privacy cost for an iterative algorithm, this paper presents following significant updates to the result of Chourasia el al; extending the result for subsampled GD (preferable for computational reasons), and replacing the strong convexity assumption with just convexity. \n\nAuthors have done significant amount of original work to solve the question at hand. The proof of main theorem (Thm. 3.1) comprises of many novel techniques and results, such as the new PABI result. I think the main limitation of the result is the assumption of limited search domain. However it is not a too strong of an assumption, and I think there are several real world problems that do have a priori known limited optimization domain.\n\nTo me, the most apparent weakness of the work is the presentation. The supplement included in the submission seemed like a (almost) perfectly good journal version (~19 pages) of the article, and was really pleasant to read. However, the cut down version is way too crowded currently. I do appreciate authors efforts to have the most crucial bits in the main paper, but I think the paper needs even more polishing and moving less important stuff to the appendix to make it to the NeurIPS format. And I'm afraid that it is going to be really difficult given the amount of material this paper contains.This lack of space also gives the paper a really abrupt ending with no discussion or conclusions. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-RT0GxhvVyw", "reviewer": "Reviewer_v3zG", "summary": "This paper studies the privacy loss of noisy projected stochastic gradient descent. More specifically, the authors show that after some iterations, noisy projected stochastic gradient will not cause further privacy leakage if we only release the last iterate of the algorithm. This result looks very interesting and promising for private convex optimization.", "questions": "I think the result of the current paper is very interesting, and my main concerns are as follows:\n1. How to make use of the new analysis to better understand the utility of noisy SGD.\n2. The new analysis seems to be limited to noisy projected SGD. However, in practice, people often clip the stochastic gradient and then add noisy, and how can this analysis help us to understand the privacy loss of the widely used clipped based method? In other words, whether practitioners can benefit from your analysis in practice to apply noisy project SGD?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The authors provide a new privacy analysis for noisy projected stochastic gradient descent when optimizing a convex, Lipschitz, and smooth objective with a bounded parameter space.\n2. The new privacy loss upper bound shows that noisy projected stochastic gradient descent will not cause further privacy loss after a certain number of iterations.\n\nWeaknesses:\n1. It is unclear how this result can be used to study the utility guarantee of noisy SGD. According to Bassily et al, 2019, the original private analysis can achieve the optimal utility guarantee for noisy SGD, and thus it is unclear how we can make use of the new privacy analysis.\n2. One drawback of the current analysis is that we can only release the last iterate.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept