Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)
Authors: Jiayuan Ye
Reza Shokri
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
noisy stochastic gradient descent
last-iterate analysis
privacy amplification

Abstract: Prior work on differential privacy analysis of randomized SGD algorithms relies on composition theorems, where the implicit (unrealistic) assumption is that the internal state of the iterative algorithm is revealed to the adversary. As a result, the R\'enyi DP bounds derived by such composition-based analyses linearly grow with the number of training epochs. When the internal state of the algorithm is hidden, we prove a converging privacy bound for noisy stochastic gradient descent (on strongly convex smooth loss functions). We show how to take advantage of privacy amplification by sub-sampling and randomized post-processing, and prove the dynamics of privacy bound for ``shuffle and partition'' and ``sample without replacement'' stochastic mini-batch gradient descent schemes. We prove that, in these settings, our privacy bound converges exponentially fast and is substantially smaller than the composition bounds, notably after a few number of training epochs. Thus, unless the DP algorithm converges fast, our privacy analysis shows that hidden state analysis can significantly amplify differential privacy. 

Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)
Jiayuan Ye, Reza Shokri
Department of Computer Science National University of Singapore {jiayuan, reza}&comp. nus edu sg
Abstract
Prior work differential privacy analysis of randomized SGD algorithms relies on composition theorems, where the implicit (unrealistic) assumption is that the internal state of the iterative algorithm is revealed to the adversary. As result, the Rényi DP bounds derived by such composition-bes with the number of training epochs. When the internal state of the algorithm is hidden, we prove converging privacy bound for noisy stochastic gradient descent (on strongly convex smooth loss functions). We show how take advantage of privacy amplification by sub-sampling and randomized post-processiig the dynamics of privacy bound for "shuffle and partition" and "sample without replacement" stochastic mini-batch gradient descent schemes. We prove that, in these settings, our privacy bound converges exponentially fast and is substantially smaller than the composition bounds, notably after few number of training epochs. Thus, unless the DP algorithm converges fast, our privacy analysis shows that hidden state analysis can significantly amplify differential privacy.
analyses linearly grow
and prove
Introduction
To protect user privacy, the widely-used differentially private training algorithm. DP-SGD adds carefully calibrated noise in each step of updating model parameters. This randomness guarantees that the models trained on any two neighboring datasets are indistinguishable probability distributions. To quantify this indistinguishability. the DP analysis bounds the (moment of) likelihood ratio between pair of models trained on any two neighboring datasets. Improving this privacy analysis crucial for obtaining higher (train and test) accuracy of the output model, under constrained privacy budget.
Machine learning models leak sensitive information about their training data 13 1
The main-stream analysis of privacy loss DP-SGD is based on composition theorems, which quantify the total privacy loss of the training process across all its iterations. Given that privacy- preserving learning via DP-SGD usually suffers from slow convergence empirical prediction accuracy [1O, the final bound could be significantly large (and loose). This analysis worsens the privacy-accuracy trade-off by overestimating the magnitude of required noise for DP training.
To alleviate this problem, one popular direction is to design new variants of the DP-SGD algorithm, that converge faster, i.e. require smaller number of iterations reach stable training accuracy. This includes works that derive privacy preserving variants of fast optimization algorithms, such as performing SP-SGD with momentum 25), adaptive gradient clipping
50 adaptive selection of
step-size and noise scale 4 and using pre-trained or hand-crafted features
34 All these approaches
aim for a faster training convergence for the DP learning algorithm, such that the composition analysis is applied to a smaller number of iterations and the total bound remains small.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Another line of work focuses on directly improving the privacy analysis of the DP-SGD algorithm. To this end. prior work T8 5 15I suggest that hiding the internal state of noisy (S)GD, therefore analyzing the privacy bound for releasing only the last iterate results in a more accurate estimation of privacy loss. By applying the last-iterate privacy analysis [T8] Feldman et al. [9] design new differentially private algorithms that achieve theoretically optimal excess risk with linear runtime for convex optimization, which is better than the prior privacy utility trade-off for the noisy SGD algorithm 77. However, the analysis applies only to one single epoch of training, thus it is unclear how such training performs in practical learning settings (which require multiple epochs of training). Chourasia et al. [15] derive strong privacy guarantee for hidden-state noisy GD over many training epochs, under strongly convex loss function. However, the analysis is limited to computationally e and extension of it to stochastic mini-batch training would fail to model the
expensive GD
privacy amplification by post-processing [1S 5 and mini-batch sub-sampling [2 27
(5)
Thus, under the hidden-state assumption over many epochs of training, the challenge is to compute a small privacy bound for differentially private stochastic gradient descent algorithms by taking advantage of privacy amplifications due to sub-sampling and randomized updates over mini-batches.
Contributions. In this paper, we tackle this chal- lenge, and bridge the gaps in the prior work on hidden-state (last-iterate) privacy analysis. We model the privacy dynamics of noisy SGD, and show the privacy amplification for private (hidden state) ma- chine learning due to stochastic mini-batch selec- tion. (i) As we also show in this figure, for multi- epoch noisy stochastic mini-batch gradient descent under "shuffle and partition" " and iterative "sam- pling without replacement". we prove new converg- ing privacy bounds (for strongly convex smooth loss function) that significantly improves over the prior bounds [5]
in = R-ne)- Differential Privacy
DP SGD M SGM 2Y
(conspasition)
0.15
Our Privacy Bound (fixed-order last mini-batch)
0.10
0.05
Our Privacy Bound (shuffle and partition)
29 13]. Our proof relies on our new bounds for the privacy amplification by post- processing (Lemmal (32) and sub-sampling (Theorems 4.2 and 4.3) (ii) For the special case of full gradient descent, our new approach (via proving better bounds for the privacy amplification by randomized post-processing) results in a strictly tighter bound than the prior work (15) with a different proof (Appendix D.7. The key insight of our new proof is that we can break down one noisy GD update into two consecutive steps: a noisy GD update with smaller noise scale, followed by pure additive Gaussian noise (randomized post-processing).
10
20
30
40
Training Epochs
Our results show that, to obtain a tighter privacy bound, it crucial to apply our hidden-state privacy dynamics analysis for learning tasks with slow to moderate convergence. Alternatively, it is not so costly to use composition- based privacy analysis when the training process converges very quickly.
2 An overview of the problem and our approach
We analyze differential privacy loss of the noisy (stochastic) mini-batch gradient descent algorithm, when only the last iterate parameters 0% are visible (see Algorithm 1 I We consider two mini-batci
generation variants: (1) "shuffle and partition" (widely implemented in privacy libraries
40 24
);
(2) "sample without replacement" (analyzed extensively in prior results [12] 27 37 despite its computational cost). Our ultimate goal is to prove worst-case upper bound of the Rényi divergence between distributions of last-iterate parameters 8% and @ trained any two neighboring datasets.
The prior work Chourasia et al. [5] has shown a tight converging hidden-state privacy dynamics analysis for full-batch noisy gradient descent. However, the sub-sampling steps that are unique to the stochastic mini-batch gradient descent, and their privacy benefits, are not modeled nor quantified in such bounds and the follow-up up work. Would a naive extension of the prior GD analysis to the stochastic mini-batch setting result in a tight bound? To this end, we can view the updates that involve the (sensitive) differing data record (between neighboring datasets) gradient descent smaller, iteratively changing dataset of size b (i.e., the size of a mini-batch). This extension results in the following naive privacy baseline.
'See Appendix B for the preliminaries about differential privacy and necessary tools for our analysis.
2

---

Algorithm 1 ANoisy-mRGDD Noisy (Stochastic) mini-batch Gradient Descent
1: Input: Dataset D (X1, X2,
... , Xx.). X2,... Parameter space E Rº Loss function {(0; x). Stepsize v,. Noise
standard deviation a. mini- size 6. Initial parameters 0g sampled from an arbitrary distribution pa (0).
2: Batch Generation: obtain mini-batches B3 of size b, for j = 0,-.. , ,n/bb11: 1; for epochs & 0,.... K
3: If "Shufile and partition": randomly partition data indices into B", ...... Bn/b-1 let B3 = B'
4: b If Sample without replacement: resample b different indices from (L, (L,.., ,n] to obtain every By-
5: for epoch k = 0, 1,... K 1 do
6: for iteration j 0, 1, .n/b- 1 do
7: 05-1 == 0g n 9 (0%: B)) v 2no² N (O, where 9 (0):B.) Ei v((0fix))
8: 0k+1 6%
9:
Output: 8%
Theorem 2.1 (Naive Extension of Chourasia al. [5] bound to SGD). the loss function E(0;
is X-strongly convex and 8-smooth, and its gradient has ez-sensitivity Sg then Algorithm) 0 Munder
"shuffle and partition" " and step-size n < X+3 sattisfies (aég)-Rényi DP with S x0=22 (1-e- (1-e-Ank/2) /2)
2
asa
However, as we also show in Figure T this naive privacy dynamies baseline slowly converges to a huge constant, which is significantly worse than the bounds derived by composition py This is because this naive baseline fails to capture the privacy amplification due to the stochasticity of mini-batch sub-sampling, and the iterative noisy updates which amplify the privacy of preceding mini-batches (referred to as amplification by post-processing). In this paper, we show how to compute much tighter differential privacy bound for noisy SGD, under the hidden-state assumption, while taking advantage of these privacy amplifications. Our methodology is novel and quantifies the hidden- state privacy amplification due iterative data (re)sampling throughout the training process (over multiple epochs of training). This solves the limitation of the prior work on privacy amplification (by iteration) which focuses on single epoch, and uses composition theorems across epochs (thus, not modeling the privacy of hidden-state iterative resampling). Finally, our methodology is generic and applies the special case of full-batch noisy gradient descent, which enables strictly tighter privacy bound than the prior work 1 under the same assumptions (Appendix D.7. p.
Our approach is as follows. We decompose the distribution of last iterate parameters 0% in Algo- rithm as a mixture of conditional distributions p(0k)) = EB P(B) p(0 B)), given any possible mini-bate Mini-batch sequence B. We first analyze the Rényí privacy loss for a fixed mini-batch sequence while modeling privacy amplification by randomized post- post-processing (i.e., how much the randomized gradient update improve the privacy due to updates on preceding mini-batches). We then quantify the privacy amplification by subsampling under stochastic mini-batches.
Privacy amplification by randomized post-processing. To start, we consider Algorithm D without the effect of stochasticity in the mini-batch sampling process. That is, we first assume that the mini- batch sequence used in the algorithm is fixed (by an arbitrary order). When a mini- batch contains only the indices of shared data records between two neighboring datasets, then the deterministic mini- batch gradient descent mapping does not cause any additional privacy loss. Addition of the Gaussian noise that follows this deterministic update, however, serves as a randomized post- prot-processing which decreases the Rényi divergence between the two processes (associated to neighboring datasets). To compute this privacy amplification, we precisely model the change of parameter distributions with the Fokker-Plande equation (for diffusion process with zero drift).
Hidden-state privacy amplification by sub-sampling. Although privacy amplification by a single 29
20, 21], to the best of our knowledge, no prior bounds are applicable to multiple epochs of hidden-sttan state iterative resampling. This is because
sub-sampling operation is well-studied [12 27
7
5
37
2 A recent concurrent work (2) also follows this approach to extend the GD analysis 15 to SGLD setting. and proves a similar bound to our naive privacy dynamics baseline Theorem 2.1 However, there is a slight difference between (3)) Corollary 3.3] and our Theorem 2.T due to the flawed assumption in [2) Lemma 3,4] that the LSI constant proved in Chourasia al. [IS] (that only holds for GD process) also holds for SGLD process (that takes the form a more complicated mixture distribution). See more details Appendix For simplicity of presentation, we assume b divides n. If n//b is not an integer, and if the algorithm ignores the last [n/b] b data points, then our privacy dynamics bound holds by replacing n//b with [n/b].
3

---

under the hidden-state assumption, the number of mixing components in the last-iterate parameter distribution grows exponentially with the number of epochs K, i.e., [number of possible values for one mini-batch] which makes the mixture distribution very difficult analyze. In this paper, to study the exponentially many mixture components, we derive recursions for the divergence between mixture distributions after one epoch. We use the joint convexity of exponentiated Rényi divergence to bound how much smaller the Rényi divergence between mixture distributions (for model parameters at one epoch) is compare to the worst case Rényi divergence across any pair of their mixture components (representing the preceding epoch). This recursion quantifies the sttte privacy amplification by sub-sampling. and enables a significantly smaller Rényi DP bound for noisy stochastic mini-batch gradient descent, than the composition of sub-sampled mechanisms over multiple epochs (Figure
3 Privacy dynamics for fixed-ordering noisy mini-batch gradient descent
In this section, we quantify the privacy amplification by randomized post-processing in Algorithm I during iterations that do not access the sensitive differing data between neighboring datasets. We then combine it with RDP composition for the remaining iterations and prove a converging privacy bound.
3.1 Privacy amplification by randomized post-processing (additive Gaussian noise)
We first explain the key lemma that proves exponentially decaying Rényi privacy loss under additive Gaussian noise post- post-processing, when the parameter distributions satisfy the log-Sobolev inequality. This is new bound for the well-known "privacy amplification by iteration" " phenomenon [I 5
Lemma 3.1. Let u.v be two distributions on Rd. Let R. - Ba be a measurable mapping on Rd. We denote (0, 2ta² Ia) to be the standard Gaussian distribution on R. with covariance matrix 2lg...a. We denote (0) and pl
(0) to be the probability density functions for the distributions
I+ (v) denote the push forward distributions of μ. under mapping f- Then if μ and satisfy log-Sobolev inequality with constans e, and if the mapping I is L-Liipscitz, then for any order a > 1,
I (1) * (,, and (v) *N (0, 2to² respectively, where (1)), I+
① Ra (p(())l)p((0)) S - 200.. -2.-202 Ōt
RRa (Ra()((0)lp) (Ra
② + +(a 1) da (a(0((00)))))))) (1)
a
where c; c (- + +1o2) is the log-Sobolev inequality constant for distributions (0) and (0).
Proof Sketch. The proof starts by modelling Gaussian noise as a diffusion process with zero drift. We then bound the rate of Rényi divergence with the LSI constant for the process (following prior works 35 13). However, instead of assuming a fixed LSI constant c for all intermediate distributions, we prove more precise LSI constant e that changes with t. Complete proof is in Appendix D.I
The partial differential inequality in Lemma 3.I quantifies the amplification of Rényi privacy loss under additive Gaussian noise. By solving Equation ① on / E [0, we prove the following lemma that models recursive privacy dynamics during one step of noisy mini-batch gradient descent.
Lemma 3.2. Let D, D' be arbitrary pair of neighboring datasets that differ in the ig-th data point (iee Fig # x''g). Let By be a fixed mini-batch used (in iteration j of epoch k) in Algorithm ! which contains indices sampled from {1, ,1, We denote 0% and 0% as the intermediate parameters in Algorithm [ on input datasets D and D', respectively. If the distributions of 0% and 0², satisfy log-Sobolev inequality with constant e, and if the mini-batch GD mapping f(0) =
nn.-
0 17 6. Ei x(0:x.) L-Liipschiz for parameters 0, then the following recursive bound for Rényi divergence holds.
(a, -11000
(1+
==200" ssa
if B% if By
with a' a-1 2:2n02 (2)
+
α
Ro 1021100 (045)
1 1,2
Proof Sketch. When in é Bi we apply Lemma 3.1 on the deterministic mini-batch gradient descent update f. and solve Equation ( to obtain recursive Rényi privacy bound. This proof is similar to

---

0.15
0.15
iin (a. e Differential Privacy
Naive Privacy Dynamics Baseline 15
Naive Privacy Dynamics Baseline 1k]
Privacy Dynamics (first mini baich) Balli et al. Composition (first mini-batch)
Privacy Dynamics butch) Balle et al.
3 Composition (last mini-bateh)
0.10
0.10
15
10
0.05
0.05
15
25
5
K
(a) data points the first mini mini-batch
(b) data points the mini-bacch
Figure I: Rényi privacy loss of fixed-orden fxxe-ordering noisy mini-batch gradient descent over K epochs, which repeatedly goes over fixed sequence of mini-batch partition in each epoch. We show the privacy loss for data points in the first mini-batch B" and the last mini-batch /n/6-1 of each pass. We show the E in the (g. eR-DP guarantee derived by our privacy dynamics analysis (bold lines), the naive privacy dynamics baseline (thin lines), and the privacy amplification mixing and diffusion analysis ( combined with composition (dashed line). We evaluate
under the following setting: RDP order a f10, 15): X-strongly convex loss function with 1: 3-smooth loss function with 4; gradient sensitivity Sg = 4; size of the data set n = 50; step-size 7 0.02; noise variance o² = 4, mini-batch size b = 2. We use Theorem 3.3 for our privacy dynamics; Theorem 2.1 for naive Composition (details are in Appendix D.6
privacy dynamics baseline; and 5 Theorem 5] for Balle et al. 5
that of [15 Theorem 2]. however, dealing with the new LSI constant that changes with / introduces an additional technical difficulty. When in E Bi use composition theorem to prove the additive
recursion the second row of Equation 2 The complete proof in Appendix D.2
Comparison with prior amplification by post-processing bound. Prior to this work, for convex and smooth loss functions, Feldman al. [8] derive tight bound for the amplification by post- processing in noisy stochastic gradient descent. In Appendix D.4, we show that our new recursive amplification bound could recover this known tight bound for convex smooth loss functions, while using different proof. For (a more restrictive setting of) one epoch of noisy SGD on strongly convex loss function, Balle al. [5] further improve the bound in Feldman et [8] via a careful coupling-basse based approach. However, to multiple epochs except by using Rényi DP composition (which would give a linearly worsening Rényi DP bound with the number of epochs). By contrast, our recursive amplification bound easily applies to multiple epochs (under hidden state assumption, and without requiring composition over the epochs), and enables converging privacy dynamics for Algorithm I on strongly convex smooth loss functions (as discussed in Section 3.2
do not see easy way extend the bound in Balle et al. [5]
3.2 Improved privacy dynamics for fixed-ordering noisy mini-batch gradient descent
By using the recursive privacy bound Lemma 3.2 and the non-overlapping property of mini-batch partitions of the dataset, we prove position-depennent Rényi DP bounds for Algorithm I as follows.
Theorem 3.3 (Privacy dynamics under strongly convex smooth loss). Conditioned on a fixed sequence of partitioned mini-batches B" ...... BB//b-i in Line 3 if the loss function is X-strongly convex, 8-smooth and its gradient has Ez-sensitivity S. then running Algorithm for K 2 1 epochs with step-size 1) < X+3.
2
satisfies (a., RRéény DP for data points in the batch B30, with
(1 (K)
1n (a)
+ 5 (0/b-5((a)
S 6
(3)
(1 - 1/t 2 2m/bb 1ED
where cd((a)
an 20-12
(1 n71) 2(1-1)
- for any j = 1,... (we assume
1 2).
Proof Sketch. We first prove that the distribution of parameters 0 satisfies LSI with a constant of that depends on j. Then we plug the LSI constants into Lemma 3.2 and prove recursive privacy bound
5

---

for data points in each batch B Finally, by carefully choosing which recursion to use and solve, we obtain the privacy bound in the theorem statement. The complete proof is in Appendix [.5] m
The above new privacy bound Theorem 3.3 quantifies the privacy amplification during iterations that only access the shared data points between neighboring datasets, and it is significantly smaller than the naive privacy dynamics baseline derived from Chourasia et al. [S (that does not capture this additional privacy amplification). Figure 1 we observe that for data points in the first batch Bd, our new privacy dynamics bound is smaller by a multiplicative factor of approximately n/b (where b/n the batch sampling ratio), and the improvement for data points in the last-batch is also significant.
Bound improvement compared with Balle et al. (5]. In the first epoch (when K = 1), our privacy dynamics bound (based on recursive scheme) in Theorem 3.3 is of same order the privacy amplification bound Balle et al. [ Theorem 5], as shown in Figure I However, for training with multiple epochs, Balle et al. [ use coupling-based approach, and
do not see easy way to extend their analysis except by using Rényí DP composition 23 over the epochs, which gives a linearly accumulating Rényi DP bound for multiple epochs (as K increases). On the contrary, as shown in Figure D our improved privacy dynamics bound converges to a constant, thus significantly improves over the Rényi DP composition of Balle al. 5 Theorem 5].
4 Privacy dynamics for noisy stochastic mini-batch gradient descent
In this section, we further improve over the by incorporating the effect of amplification of privacy loss due to the stochastic mini-batch sampling. We first prove the following lemma by the convexity of f-divergence with f(z) = x².
privacy dynamics analysis in Section 3
Lemma 4.1 (Joint convexity of scaled exponentiation of Rényi divergence). Let p1. Hmm and V1," 3mm be distributions over R. Then for any RDP order a 2 1, and any coefficients
Pl, .. Pm 2 0 that satisfy Pt +... + Pm = 1, the following inequality holds.
(a-1)- EE
Pj (a-1))
(4)
We provide a detailed proof for Lemma in Appendix This Lemma is our main tool for quantifying the additional privacy amplification under stochastic mini-batcher in the rest of the section.
4.1 Privacy dynamics under shuffle and partition
The "shuffle and partition" batch generation scheme is commonly used for practical DP-SGD implementations in privacy libraries [24] 40 By using Theorem 3.3 and new bounds for the privacy amplification by shuffling in Algorithm ! we prove the following Rényi DP guarantee.
Theorem 4.2 (Privacy dynamics under "shuffle and partition").. If the loss function f(0;z) is X-strongly convex, 8-smooth, and if its gradient has finite ez-sensitivity Sy, then for & 2 2, run- ning Algorithm 7 for K 2 1 epochs with step-size v x+3. generation scheme, satisfies (a. Réény DP with
2_ under "shuffle and partition" batch
1 1- -)2))-2(K (m)
E
#1 (a). 5D
1 1- 1- (1-11))) (1-n))= 21 (n/00
a a-1
.log
Aug (aa-1)) (SSoen//
(5)
where sg((a)
ans? 2
(1 2))2
11 for any j = 1,..........................1. (we assume
2). N
The above Rényi DP bound Theorem 122 is always smaller than the Rényi DP bound in Theorem 3.3 for the worst-case fixed mini-batch sequence (i.e., when the differing data point is in the last binc- of each pass). Therefore, Theorem 4.2 quantifies the privacy amplification due to shuffling, when compared to the worst-case Rényi DP bound among all possible mini-batch sequences. In Figure (a), we illustrate this amplification in more details.
*When a and e/ //b-J0 (a) are large, the second term in Equation might overflow. In the experiments,
we compute this log-sum-cue cum term with the shifted approximation o log Aug (cr 13 m/6-/0 to (2) <dco))

---

Our Privacy Dynamics (shuflle and partition)
Privacy Dynamics (samp. replacement)
Our Privacy Dynamics (fixed-ordrr last mini-batch)
DP-SGD
SGM
A
(compocition)
DPSSG
(composition)
in (o.,))-kknyi Difieventia Phivacy
0.15
0.15
10
0.05
0.05
0
0
10
20
30
40
10
20
30
40
K
(a) shuffle and partition
(b) (re)sample without replacement
Figure 2: Rényi privacy loss of noisy (stochastic) mini-batch gradient descent K epochs. We show in the (q, ()PP) guarantee derived by our privacy dynamics bound under "shuffle and partition" " (bold lines, left plot), our privacy dynamics bound under sampling without replacement (bold lines, right plot), our privacy dynamics bound for data points in the last batch /=/b-1 (thin dashed lines), and the baseline composition-based bound 22 (thin lines). We evaluate under the following setting: RDP order E [10, 15): X-strongly
for DP-SGD [
convex loss function with À = 1; 3-smooth loss function with 3 = 4; finite total gradient sensitivity Sy = 4;
size of the data set n = 50; step-size 7) = 0.02; noise variance o² 4, batch size = 2. The expressions for computing the privacy bounds are: Privacy Dynamics (shuftle and partition): Theorem 4.2 Privacy Dynamies
(samp. w.o. replacement): Theorem Privacy Dynamics (last batch): Theorem under jo n2/b
Composition: derived from Section 3.3. of Mironov al.
29 that approximately equals
26
K.
Comparison with prior amplification by sub-sampling bounds 22 20
We now investigate
how our Rényi DP bound Theorem 2 compares with prior bounds for privacy amplification by sub-sampled mechanisms, in terms noisy mini-batch GD on sub-sampled mini-batch with size b, and RDP bound for full-batch noisy GD on a small dataset with size b). Observe that only the first term of the Rényi DP bound Equation
amplification rate (i.e. the ratio between RDP bound for
increases with the number of epochs K, and its growth rate strictly smaller than E 1 ans? Here, the term 4 is exactly the Rényi DP bound for a full-batthh noisy GD update on dataset with small size b. Therefore, Theorem 4.2 achieves amplification rate of ( ) for epoch of noisy mini-bated gradient descent under "shuffle and partition". This ( amplification rate
ams
m 4m262
for epoch matches the ( (())) amplification rate in prior bounds for one epoch of sub-sampled mechanisms PD 20 P because one epoch consists of iterations.
However, prior bounds for privacy amplification by sub-sampling (such as for sub- sub-sampled Gaussian
mechanism [29] and for noisy SGD under "shuffle and partition" 20 (1) only study a single update or single epoch, and then rely composition theorem for computing amplified privacy bounds for multiple epochs. Consequently, the Rényi DP bounds derived by such analyses linearly grow with the number of epochs K. On the contrary, our Rényi DP bound in Theorem 4.2 applies to multiple
epochs with hidden intermediate state, and thus enables converging Rényi DP bound that never exceeds maximum value. Hence, Rényi DP bound in Theorem composition- based privacy bound for DP-SGD 20
is strictly smaller than 1 + & epochs. This is because the first after Xv
term in Equation 5 is strictly smaller than the composition- based privacy bound after Xy epochs, and the second term in Equation (5) is strictly smaller than the composition-based privacy bound after n/b epochs (as we explain with more details in Appendix E.
4.2 Privacy dynamics under (re)sampling mini-batch of fixed size without replacement
We now similarly analyze privacy dynamics for another variant of noisy mini-batch gradient descent (Algorithm D. where in each iteration of each epoch, we freshly (re)sample b indices without replacement from -1. -. n2 to obtain fixed-size mini-batch. That is, the mini-batches used in
7

---

different iterations (of one epoch) may overlap. This "sampling a mini batch of fixed size without replacement" scheme widely studied in the amplification by sub- samp-ing literature [5] 37 an attractive alternative that ensures fixed mini-bate size (when compared to Poisson sub sub-sampling).
26 as
Theorem 4.3 (Recursive amplification by sampling without replacement, If the loss function E {0;;a)
is A-strongly convex, B-smooth, and if its gradient has finite Ez-sensitivity Sg. then Algorithm D Jander sampling without replacement and stepsize < X+B
2 satisfies (ar, R)-Rny DP guarantee with
1
E a 1 log (5%(())
(6)
where the terms (a for k- = 0, .....
K --12 1 and = 0, ... ,n/b - 11 are recursively computed by (a) + (1- h) h))
(a())) L; S/ 2.
(0-1)088 so
(a(a and (2+1(a)= = Sn/b (a).
(0-1)9522
Observe that in the above recursion, the term Sy (a) is strictly smaller than e 4o
5% (i.e..
the Rényi DP bound for one step of noisy gradient descent on dataset with size b), thus quantifying the privacy amplification by sampling a mini-batch of fixed size without replacement. We illustrate
(b). However, our privacy bound under "sample without replacement" in Figure 2 (b) is larger than our privacy bound under "shuffle and partition" in Figure (a), which suggests room for future improvement of the amplification rate bound. Indeed, for the
this privacy amplification in Figure -
special case of a single update, prior privacy amplification by subsampling bounds 33 26 achieve
better amplification rates of O(5)
However, prior bounds for privacy amplification by sampling generally only apply to a single sub- sampled update. Therefore, for analyzing multiple iterations of updates, prior works still rely on composition theorems, which results in linear growth of Rényi DP bound with regard to number of epochs. On the contrary, our privacy amplification bound Theorem appllis to multiple iteration of hidden-state (re)sampling without replacement steps, which enables a converging Rényi DP bound even for training an infinite number of epochs. In Figure 2 (b). we compare our Rényi DP bound Theorem 4.3 with the baseline composition-based observe that for a range of RDP orders a 10, 15, 20, our privacy dynamics bound significantly improves over the baseline composition-bans -ased bound (after 50 epochs).
privacy bound for DP-SGD I1 28] We
5 Example: privacy dynamics for DP-SGD on regularized logistic regression
In this section, we explain a practical setting that our improved privacy dynamics analysis is applicable: training regularized logistic regression with the DP-SGD algorithm [ (under "shuffle and partition" " mini-batch sampling scheme). Note that DP-SGD algorithm under "shuffle and partition" is equivalent to our analyzed gagorithmmaafter change of notations, as discussed in Appendix [F.]] For completeness, in Algorithm 2 also provide the pseudocode for an equivalent of DP-SGD algorithm under notations in our paper.
5.1 How to ensure strong convexity, smoothness and finite sensitivity
Suppose that we want to train models for image classification tasks. The training dataset that we take as input is D = (Z). ....... zn), where each data record z; = (x,, consists of the d-dimentional data input feature vector x; E IRd, and the label vector y: E {0, 1] (in one-hot encoding). To satisfy the necessary conditions for our privacy dynamics bound, we use regularized logistic regression to ensure strong convexity, use feature clipping to ensure smoothness, and use gradient clipping to enforce finite gradient sensitivity, as follows.
Regularzied Logistic regression (for strong convexity). The loss function for regularized logistic regression in the multi-class setting (with per-class bias) is as follows.
X
(0: = Lu (0 + 1012
where (n(0x, x) is the following logistic regression loss function.
x 0,
T +
Eo(0; y) = -y² log 0 + + e 2"0
log e
(8)
+
ex
8

---

where X (x, 1) E Rd+1 denotes the concatenation of the data feature vector x and 1, and = (y) :... .y) is the label vector. The parameter vector is 0 = (0).-.. Oe) E ((++1)c that represents the weight and the per-class bias of the linear model. The logistic regression loss function is convex, and therefore the regularized logistic regression loss function is X-strongly convex.
Feature Clipping (for bounding the smoothness constant). To ensure that the condition of loss function smoothness with regard to parameters 0 is satisfied, we follow Feldman et al. [8] and normalize the data feature vector in & norm, such that ||x||2 S L. Under this data feature clipping. prove that the logistic regression loss function ( is ( (1221) }-smooth in the following Proposition 5.1 Proposition 5.1. If the data feature vector has bounded l2 norm, such that ||x||2 S T., then the unregularized logistic regression loss function Eo(O; x. Equation 3-smooth with regard parameters for
is convex, L-Lipschitz and
L 22 +1)
(9)
B L +1
(10)
By Proposition 5.1
the regularized logistic regression loss function Equation 7 is (3 + -m-smooth.
The above feature clipping technique is different from the DP-SGD algorithm W that only requires per-example gradient clipping. The major reason that we use data feature clipping (besides per- example gradient clipping), is for ensuring smoothness of the logistic regression loss function (by Proposition 5. which a necessary condition for applying our privacy bound Theorem 3.3
Per-example Clipping Unregularized Gradient (for reducing gradient sensitivity without harm- ing smoothness or strong convexity). Although feature clipping already bounds the gradient sen- sitivity by 2 2222(2² + 1) (by Proposition 5.1p. this bound grows with the feature clipping norm L. This in turn restricts the signal to noise ratio, and tends to give suboptimal privacy-utility trade-off in practical experiments. Therefore, we additionally perform per-example ly-clipping on the unregular- ized gradient (detailed pseudocode in Appendix F.I.. Under per- eer-example clipping unregularized gradient, we prove in the following Proposition 5.2, that each gradient update in regularized logistic regression has finite gradient sensitivity, and preserves strong convexity and smoothness.
Proposition 5.2. Let (o(0; y) be the logistic regression loss function defined in Equation Let Vio(Oxx.y) min Vlo(O; x. y) $4 be the clipped gradient of (unregularized) (0; y) [Vo0(xx.y))l
loss function x)), under l2 clipping norm Sa If gf;; y) go x. y) X0, and if the data vector x has bounded &g norm, such that |x||| 2 L. then g(0; x, y) has finite Eg ex-sensitivity Sg. is continuous, and is almost everywhere differentiable with
A Id I Vog(O: x. y) 1 (8 +8+A), A) I(44)o
(11)
for any 0, 0' E g(d+1) and B 12+1
We provide complete proof for this proposition in Appendix F44
This construction of clipped unregularized gradient enables us to enjoy the benefits of gradient clipping (such as for speeding up convergence 44 [4] while satsifying the necessary smoothness and strong convexity conditions for applying our privacy dynamics bound.
5.2 Composition-baset privacy bound and privacy dynamics analysis for DP-SGD
Baseline composition-based privacy analysis. To the best of our knowledge, the moments accoun- tant [ combined with the privacy amplification bound for Subsampled Gaussian Mechanism 29 gives the strongest baseline composition-based privacy bound for DP-SGD. The original DP-SGD bound only holds for mini-batch sampling from a Poisson distribution. However, currently many pri- vacy libraries
still apply the DP-SGD analysis while implementing the "shuffle and partition" sampling scheme. Recent works 20 21 further prove that the Rényi DP bound for DP-SGD under "shuffle and partition" matches that for SGD under Poisson sampling in order. Therefore, consider the moments accountant bound for subsampled Gaussian mechanisms (29] as a reasonable comparison baseline for our privacy bound of DP-SGD Algorithm under "shufffe and partition".
24 40
Improved privacy dynamics analysis. We now compute our privacy dynamics bound Theorem 4.2 for the modified DP-SGD algorithm Algorithm 2 under "shuffle and partition". By plugging the

---

notation transformation in Appendix F.I into Theorem we prove the following privacy dynamics theorem for noisy mini-batch gradient descent on regularized logistic regression.
Corollary 5.3 (Privacy dynamies for noisy mini-batch gradient descent on regularized logistic regression). For the regularized logistic regression loss Equation 7 with regularization coefficient X, if the data feature vector clipped in ly-norm by L, and the unregularized gradient is clipped in
Sa, l2 norm by 2. then for K 2 and t 2 2, Algorithm 2 with stepsize 1 < (12+1)/2+2X and noise
multiplier mut satisfies (a, normm + E) Réényi Differential Privacy with
16 s 55 (a). (a)
1 1- -
- 7))2.(K ()/()))nn//)))/ DD
1
Aug (a-1)= (12) OSto<n/b
log
(1 - n/) 11)2-11/6-12
a
where the terms (a) is upper-bounded for any j = -,,... .. n//b as follows
cg(a)) S
2a
Ex-1 (1-
.. (1--1))) 111))111111
(13)
o² mui
n/)22
Proof Sketch. The proof is by applying Theorem 4.2 with gradient sensitivity S., smoothness constant
1'+1
X, strong convexity constant (derived by Proposition 5.2)) and noise standard deviation
2
V2
T
2 mmul S (explained in Appendix R1
6 Conclusions and Discussion
We prove a novel converging last-iterate privacy bound for noisy stochastic mini-batch gradient descent on strongly convex smooth loss functions. Our bound substantially improves the prior privacy dynamics bound for noisy GD [55, by proving novel bounds for the additional privacy amplification (by randomized post-processing and sub-sampling) during training with stochastic mini-batches. Our results show that to obtain tighter privacy bound (thus achieving better privacy accuracy trade-off), differentially private learning algorithms needs be evaluated by a last-iterate privacy bound, unless it has a very fast convergence (under which, due to the small number of epochs, the cost of composition bound is not significant).
Future Work and Other Related Work. For iteratively resampling a mini- of fixed size without replacement, there is room for improving our hidden-state privacy amplification bound Theorem under smaller batch size b, because under one sampling without replacement step, the best known
37 This suggests possibility for a better hidden-state privacy amplification bound (without using composition) for multiple steps of sub-sampling.
amplification rate is as small as O 6? ,
5
In our current analysis, strong convexity and smoothness of the loss functions are necessary conditions for obtaining a converging hidden-state Rényi DP bound. More specifically, strong convexity and smoothness ensure that log-Sobolev inequality with constant (which is a condition required by Lemma B.2p holds throughout the training process (i.e. after any number of epochs le and iterations j). A recent work Altschuler and Talwar [ consider constrained optimization problem where A optimized over a bounded set with finite & diameter (rather than the unconstrained parameter space Rd considered in this paper). Under such setting, they prove that convexity (instead of strong convexity) and smoothness the loss functions suffice to enable a time-independent Rényi DP bound for noisy SGD. However, it remains an important open problem to further relax the convexity and smoothness conditions for proving converging Rényi DP bound.
One of the most important motivation for studying hidden-state Rényi DP bound in this paper, is that most State-of-the-an privacy accuracy trade-off for differentially private learning are achieved via the last-iterate model (instead of average of iterates). However, in terms of theoretical privacy utility prove that the average of iterates achieves optimal privacy-utility trade-off in certain regimes. For convex stochastic optimization, by exploiting the privacy amplification of last-iterate, recent works
trade-off, prior works [ g
15 22 prove that last-iterate also achieves asymptotically optimal privacy-utility trade-off (for appropriate choice of step sizes or continuous-time algorithm). Therefore, remains an interesting open problem as to whether last-iterate or average of iterate enables better (non-assymptotic) privacy accuracy trade-off.
[19
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Yaodong Yu, Chuan Guo, Maziar Sanjabi and anonymous reviewers for helpful discussions on drafts of this paper. This research is supported by Google PDPO faculty research award, Intel within the www.private-ai.co Early Career Research Award (NUS ECRA award number NUS ECRA FY19 P16), 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 author(s) and do not reflect the views of National Research Foundation, Singapore.
center, Meta faculty research award, the NUS
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Jason M Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 2022.
[3] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34, 2021.
[4] Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. International Conference on Machine Learning. pages 383-392. PMLR, 2021.
[5] Borja Balle, Gilles Barthe, Marco Gaboardi, and Joseph Geumlek. Privacy amplification by mixing and diffusion mechanisms. Advances neural information processing systems, 32, 2019.
[6] Jean-Baptiste Bardet, Nathaël Gozlan, Florent Malrieu, and Pierre-André Zitt. Functional inequalities for gaussian convolutions of compactly supported measures: Explicit bounds and dimension dependence. Bernoulli, 24(1):333-352) 2018.
[7] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Effi- cient algorithms and tight error bounds. In 2014 JEEE 55th Annual Symposium on Foundations of Computer Science, pages 464 473. IEEE, 2014.
[8] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
[9] Dankmar Böhning. Multinomial logistic regression algorithm. Annals of the institute of Statistical Mathematics, 44(1):197-200, 1992.
[10] Zhiqi Bu, Hua Wang, and Qi Long. On the convergence and calibration of deep learning with differential privacy. arXiv preprint 07X1v:2106.07830, 2021.
[11] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voor Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. 30th USENIX Security Symposium (USENIX Security 21), pages 2633-2650, 2021.
[12] Kamalika Chaudhuri and Nina Mishra. When random sampling preserves privacy. In Annual International Cryptology Conference, pages 198- 2-3...1.55 Springer, 2006.
[13] Hong-Bin Bin Chen, Sinho Chewi, and Jonathan Niles-Weed. Dimension-free soboley inequali- ties for mixture distributions. Journal of Functional Analysis, 281 (1 10:233,,, 2021.
[14] Xiangyi Chen, Steven Z, Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: geometric perspective. Advances Neural Information Processing Systems, 13:13773-13782. 2020.
11

---

[15] Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34: 14771-14781, 2021.
[16] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[17] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-07, 2014.
[18] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 521-532. IEEE, 2018.
[19] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[20] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 202/ IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 954-964 IEEE, 2022.
[21] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for r\ enyi and approximate differential privacy. arXiv preprint arXiv:2208. 2022.
[22] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Langevin diffusion: An almost univer- sal algorithm for private euclidean (convex) optimization. arXiv preprint arXiv:2204001885, 2022.
[23] Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein. Stochastic training is not necessary for generalization. In International Conference on Learning Represen- lations, 2021.
[24] Google et al. Tensorflow privacy, 2021.
[25] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shufflin. In International Conference on Machine Learning, pages 5213-5225. PMLR, 2021.
[26] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference Artificial Intelligence and Statistics, pages 2560-2569. PMLR, 2020.
[27] Ninghui Li, Wahbeh Qardaji, and Dong Su. On sampling, anonymization, and differential pri- vacy or, k-anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 32-33, 2012.
[28] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263 263-275. IEEE, 2017.
[29] Ilya Mironov, Kunal Talwar, and Li Zhang. R) enyy differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 10530, 2019.
[30] Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X Yu, Sashank J Reddi, and Sanjiv Kumar. Adaclip: Adaptive clipping for private sgd. arXiv preprint 2tti::/90.00000 2019.
[31] Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume Contributions the Theory of Statistics, volume 4, pages 547-562. University of California Press, 1961.
[32] Théo Ryffel, Francis Bach, and David Pointcheval. Differential privacy guarantees for stochastic gradient langevin dynamics. arXiv preprint arXiv:2201. 1980, 2022. URL. httpp::tt////..... //aaxivv org abs/ 2201. 11980v2
12

---

[33] Inder Jeet Taneja and Pranesh Kumar. Relative information of type esiszár's 's f-divergence, and information iequalitiess Information Sciences, 166(1-4):05-125,, 2004.
[34] Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference on Learning Representations, 2020.
[35] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[36] Feng-Yo Yu Wang and Jian Wang. Functional inequalities for convolution probability measures. In Annales de I' I'Institut Henri Poincaré, Probabilités Statistiques, volume 52, pages 898-914. Institut Henri Poincaré, 2016.
[37] Yu- fu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR, 2019.
[38] Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pages 3-19, 2018.
[39] Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, Vincent Bindschaedler, and Reza Shokri. Enhanced membership inference attacks against machine learning models. In ACM Conference on Computer and Communications Security (CCS), 2021.
[40] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, al. Opacus: User-friendly differential privacy library in pytorch. arXiv preprint (txXi:2109.122990 2021.
[41] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019.
[42] David Zimmermann. Logarithmic sobolev inequalities for mollified compactly supported measures. Journal of Functional Analysis, 266(6) 2013.
[43] David Zimmermann. Elementary proof of logarithmic sobolev inequalities for gaussian convo- lutions IR. In Annales Mathématiques Blaise Pascal, volume 23, pages 129-140, 2016.
13


Reviews:
[{"review_id": "PLj7mp0brzW", "reviewer": "Reviewer_duNW", "summary": "This paper extends the last-iterate analysis to DP-SGD on strongly convex and smooth loss functions. The main contribution, compared the similar analysis GD, is to take two kinds of amplification into account: 1) post-processing by adding Gaussian noise; (2) sub-sampling. The empirical results show that the proposed methods outperforms composition-based algorithms.", "questions": "1. Seems the only reason to assume strong convexity is for the Lipchitzness and utility result? Can we just assume Lipchitzness for the privacy guarantee? Please correct me if I miss anything.\n2. How does the results in the paper compare to a parallel work \"Langevin Diffusion: An Almost Universal Algorithm for Private Euclidean (Convex) Optimization\"?", "limitations": "1. The writing is not good enough.\n2. Many details of the evaluation is missing.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper makes a solid step towards last-iterate analysis for DP-SGD. Although there is some space for improvement, I believe the paper surely passes the bar for acceptance.\n\nStrength:\n1. Last-iterate analysis is a very important direction to further improve privacy-utility trade-off for DP-SGD. The authors manage to augment the previous analysis for GD with amplification by post-processing and sub-sampling, which is a solid contribution.\n\nWeakness:\n1. The paper is not well written enough. There is huge space for improvement on the organization of the sections, the section names and the way to present the contributions. For example, even with some background knowledge, the titles for section 4 and 5 are somewhat confusing at the first glance for me. I suggest merging 4 and 5 into one section because they are actually two steps in one proof. There are also some sentences that do not read well (e.g. Line 109). Uppercase and lowercase letters are not used in a universal way in section titles. Some citations are outdated. For example, Tramer and Boneh 2022 are accepted to ICLR 2022 but the cited one is still the arXiv version.\n2. Table 2 does not report what kind of clipping is used? Also the number of iterations used in the experiments are not reported.\n3. Although hyperparameter tuning is typically not taken into consideration when counting privacy budget, the authors should still expose the details of their hyper-parameter tuning process.\n", "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": "H6kZ88xUt4", "reviewer": "Reviewer_Wz9m", "summary": "In this paper, authors extend recent work in convergent privacy cost of convex optimization to subsampled gradient descent (GD) setting. Authors show, that for strongly convex Lipschitz loss functions, the privacy cost of releasing last iterate of DP-SGD does not grow to infinity as the number of epochs grows, but that there is a finite upper bound for this loss. Authors present a novel privacy analysis that builds on top of recent work by Chourasia et al. 2021, and is able to capture the privacy amplification by subsampling. Finally, authors demonstrate empirically how the reduced privacy cost improves the prediction accuracy of logistic regression model learned under DP.", "questions": "Typos:\n- Lines 108-109: sentence inside parenthesis seems bit odd. Also, missing capital letter after period as in \". then\"\n- Thm 5.2: I guess K>=1 being mentioned twice is a typo.\n\nSome questions:\n\n- When you say \"fixed sequence of minibatches\", does this mean that the minibatches are the same across the epochs? As in $B^j_k = B^j_l \\, \\forall k,l \\in [K]$? I just want to make sure that I understand the difference in the contributions of Sections 4 and 5. So Sec. 4 builds the theoretical background under the assumption that the sequence is fixed and Sec. 5 then extends this to actual subsampling scheme?\n\n- In beginning of Sec. 4, it sounds like you say that you focus on the case where the adjacent index is not accessed by Alg. 1. This seems weird given the theoretical contributions of this Section, e.g. Thms 4.2 and 4.3. Maybe it is a typo? Or did I just misunderstand your point.\n\n- Out of curiosity, could you use some learning rate adaptation like Adam under the last iterate release scheme? I wonder would it cause some side-channel privacy leak through the gradient history it uses to update the learning rate.\n\n- Maybe I missed something, but after Thm 5.2 you mention that the bound is tighter than composition based after $4 \\cdot \\frac{1}{\\lambda  \\eta} + 4 \\cdot \\frac{n}{b}$ epochs. You justify this by saying, that the parts leading to this bound are smaller than the composition based one after $4 \\cdot \\frac{1}{\\lambda  \\eta}$ epochs and $4 \\cdot \\frac{n}{b}$ epochs. Now, I wonder, why cannot you just pick the max of these and say that the both parts are majored with the composition based after these many epochs. Of course the sum of the terms also works, but I was just curious if there is a reason not to use $\\max(4 \\cdot \\frac{1}{\\lambda  \\eta}, 4 \\cdot \\frac{n}{b}) \\leq 4 \\cdot \\frac{1}{\\lambda  \\eta} + 4 \\cdot \\frac{n}{b}$?", "limitations": "I think the limited use cases due to assumptions on the loss function could be further discussed. Negative societal impact is not discussed in the paper, but I believe the paper is purely theoretical and does not have direct negative impacts.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In many applications, the intermediate steps of DP-SGD are not needed, but are released which causes the privacy cost of these types of release schemes to grow as the number of iterations grows. In this paper, authors continue the research in direction of releasing only the last iterate and quantifying the privacy amplification due to keeping the internal states secret. More specifically, this paper extends the work by Chourasia et al. 2021, who proposed a bound for the privacy cost for DP gradient descent algorithm. As the GD algorithm is often computationally expensive, authors take the natural next step and quantify the privacy cost of stochastic GD. Authors show several novel theoretical results (mainly Thms 4.2, 4.3, 5.2 and 5.3), that are based on novel privacy analysis, capturing the privacy amplifying effect of subsampling. The new privacy bound is significantly tighter than the privacy bound of Chourasia et al. that does not capture the subsampling amplification.\n\nI also think that the paper is generally well written, and after couple of reads the story and the contributions become very clear. There are some parts that I think could be further clarified, and I will add those to the questions section. \n\nThe most significant limitation of this work must be the assumptions on the loss function. The strong convexity and the Lipschitzity rule out quite a few applications of DP-SGD. However, I still believe that the paper makes significant contributions that will be beneficial in the future works on convergent bounds of DP-SGD.", "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": "9lhIHLO5TcD", "reviewer": "Reviewer_q4dU", "summary": "The paper focuses on improving the privacy analysis of DP-SGD. The paper studies the privacy guarantees when only the last iterate is released. The paper's main contribution in this particular setting is to provide tighter privacy bound for strongly convex loss functions. Finally, the paper provides an example of a classification task where a tighter privacy analysis leads to improved accuracy compared to when composition-based privacy analysis is used.\n\nOverall, I think this is an extremely important result and strongly recommend the paper be accepted.", "questions": "1) Could authors comment on the privacy-utility tradeoff when the average of iterates is used instead of the final iterate as the output of the SGD algorithm?\n", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) The main result has significant practical implications on differentially private machine learning training.\n2) There are many similarities with [14]. Perhaps a minor weakness of the paper is that it isn't entirely clear what are the technical challenges the authors had to overcome to complete the analysis, which were not already addressed in [14].", "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": "2w2n98-XjRy", "reviewer": "Reviewer_tVnr", "summary": "This work improves the analysis of the last-iterate privacy bound which assumes the internal state of the algorithm is not revealed. The new analysis derives a privacy loss that grows slower than the one derived from the composition theorem if the network converges slowly or is trained for multiple epochs.", "questions": "Q1: Although the idea of sparing privacy by hiding internal states looks interesting, many assumptions have been made for the analysis, which could be broken in practice and thus breach privacy, on the other hand, the evaluation does not show the proposed method obviously outperforms the composition theorem (as described in Weakness), thus one may lack the motivation for using the proposed method and taking a risk.\n\nQ2: I don't know how the hyperparameters are tuned, but since the privacy loss of the last-iterate analysis becomes flat after multiple epochs of training, perhaps longer training will make the results of the proposed method better.", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have a basic understanding of the theoretical part of this work but didn't go deeper into the proofs, for me the strength and weakness of this work are:\n\nStrength:\n\nSo far DP learning still suffers from dramatic performance loss compared with non-private learning, tailored and tight privacy bound can help reduce the required noise under certain privacy budgets and improve the performance.\n\nWeaknesses:\n\n1. This work extends the study of last-iterate privacy bound by considering mini-batch gradient and privacy amplification by subsampling, etc.. To apply the new analysis in practice, many assumptions have been made, which may not be satisfied when training a real network, so I expect the resulting network obviously outperforms others, so far it's not, perhaps a tighter bound is needed.\n\n2. I am a little confused about the evaluation of the proposed privacy analysis. I see the baseline performance given in this work is lower than in its original work. For example in the experiment on CIFAR10, ScatterNet can actually obtain an accuracy of 69.3\\%, ResNeXt-29 can achieve 80.0\\%, SIMCLR can achieve 92.7\\%, all are on par with using the method proposed in this work.", "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