Unified Enhancement of Privacy Bounds for Mixture Mechanisms via $f$-Differential Privacy
Authors: Chendi Wang
Buxin Su
Jiayuan Ye
Reza Shokri
Weijie J Su
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy
$f$-DP
mixture mechanisms
shuffling
differentially private gradient descent
TL;DR: We improve the privacy bounds for mixture mechanisms, including shuffling and differentially private gradient descent, using $f$-DP.

Abstract: Differentially private (DP) machine learning algorithms incur many sources of randomness, such as random initialization, random batch subsampling, and shuffling. However, such randomness is difficult to take into account when proving differential privacy bounds because it induces mixture distributions for the algorithm's output that are difficult to analyze. 
This paper focuses on improving privacy bounds for shuffling models and one-iteration  differentially private gradient descent (DP-GD) with random initializations using $f$-DP. 
We derive a closed-form expression of the trade-off function for shuffling models that outperforms the most up-to-date results based on $(\epsilon,\delta)$-DP.
Moreover, we investigate the effects of random initialization on the privacy of one-iteration DP-GD. 
Our numerical computations of the trade-off function indicate that random initialization can enhance the privacy of DP-GD.
Our analysis of $f$-DP guarantees for these mixture mechanisms relies on an inequality for trade-off functions introduced in this paper. This inequality implies the joint convexity of $F$-divergences. 
Finally, we study an $f$-DP analog of the advanced joint convexity of the hockey-stick divergence related to $(\epsilon,\delta)$-DP  and apply it to analyze the privacy of mixture mechanisms.

Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacy
Chendi Wang"
Buxin Su" Department of Mathematics University of Pennsylvania Philadelphia, PA, USA, 19104 subuxindsas upenn. edu
University of Pennsylvania Philadelphia, PA, USA, 19104 & Shenzhen Research Institute of Big data Shenzhen, Guangdong, China, 518000
Seaendd@wartoo... www.n. edu
Jiayuan Ye
Reza Shokri
Department of Computer Science National University of Singapore
Department of Computer Science
National University of Singapore Singapore reza@comp.oo www..uus..uu.... edw.
Singapore j jiayuan&comp.. edu sg
Weijie J. Su Wharton Statistics and Data Science Department University of Pennsylvania Philadelphia, PA, USA, 19104 suw@wharton, upenn. edu
Abstract
Differentially private (DP) machine learning algorithms incur many sources of ran- domness, such as random initialization, random batch subsampling, and shuffling. However, such randomness' is difficult take into account when proving differential privacy bounds because it induces mixture distributions for the algorithm's 's output that are difficult to analyze. This paper focuses on improving privacy bounds for shuffling models and one-iteration differentially private gradient descent (DP-GD) with random initializations using fDP We derive closed-form expression of the trade-off function for shuffling models that outperforms the most up-to-date results based on (c, -DP Moreover, we investigate the effects random initialization on the privacy of one-iteration DP-GD. Our numerical computations of the trade-off function indicate that random initialization can enhance the privacy of DP-GD. Our analysis of f-DP guarantees for these mixture mechanisms relies for trade-off functions introduced in this paper. This inequality implies the joint convexity of F-divergences. Finally, study f-DP analog of the advanced joint convexity the hockey-stick divergence related to (e, 8)DDP and apply to analyze the privacy of mixture mechanisms.
inequality
Introduction
Differential privacy (DP. 16
rigorous mathematical framework for ensuring data privacy and has become cornerstone of -revcc-presrrvingg data analysis over the past two decades. DP has found widespread applications various data science fields, such as machine learning 212
17)
"quul contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

query answering 18 15 and synthetic data generation 37 48
29 28 A randomized mechanism
considered differentially private if the outputs of two neighboring datasets that differ in at most one element are indistinguishable from each other. The closeness of these outputs can be measured in various ways, resulting in the deñnition of (c, 5)-
[16 and its various relaxations.
The distinguishabiliy between the outputs can be measured by statistical divergences. For example, (e, 6)- associated with the so-called hockey-stick divergence 35 Another divergence relevant to differential privacy is the Rényi divergence 120 [8) which leads to Rényi DP
EEC [[] and concentrated
DP In addition to divergence based DP, hypothesis testing perspective on differential privacy was proposed in [ More recently, [4] established f-DP for differential privacy where the privacy measured by the trade-off function of type and type II errors.
In real-world applications of differential privacy, including differentially private machine learning, it is common to analyze the privacy budget of mechanisms that involve mixture distributions, where the mixture is introduced by stochastic components in the algorithm. Examples of such mechanisms
include sub-sampled mechanisms 4 (52 HO. BT, shuffled mechanisms [13
22
23 and variants of
the differentially private stochastic gradient descent (DP-SGD) algorithm 1 26 3 15 that involves
random initialization and multiple rounds of mini-batch sampling. Recently, privacy amplification by
iteration [24] has drawn much attention as it can be used to analyze the privacy bounds for DP-SGD
45
which leads tighter privacy bounds compared classical analysis based on the composition
theorem
33
39 50
While mixture mechanisms are essential in differentially private machine learning, the absence of an f-DP guarantee for their analysis remains a significant challenge. Moreover, existing divergence- not tight. This is primarily because the complex
based DP bounds for most of these mechanisms distribution resulting from the mixture makes it challenging to accurately quantify privacy guarantees. In order to illustrate this perspective, we consider the examples of shuffling models and DP gradient descent (DP-GD) with random initialization, as follows.
In shuffling models, each user's 's data record is locally privatized using local DP algorithm [1I. Subsequently, a curator shuffles the dataset containing all users' data. The shuffling procedure introduces additional mixtures of binomial noise [22]. thereby potentially am- plifying the privacy provided by the local randomizer. Shuffling is commonly employed in machine learning algorithms for batch generation [5 47 To deal with this mixture, Hoeffding's s inequality was used in previous literature information. Using f-DP in this paper, we derive an exact analytical trade-off function for the mixture of binomial distributions which is sharp.
(2 23 that leads to the loss of
In deep learning, random initialization is usually adopted in the stochastic gradient de- scent to enhance the performance of deep neural networks [36]. Intuitively, the inherent randomness introduced by initialization should contribute to the privacy amplification of DP-GD. However, Rényi differential privacy (DP) falls short in quantitatively measuring this randomness, even when applied to the simplest linear model. In this paper, we demonstrate how f-DP can effectively evaluate and quantify this inherent randomness from initialization.
Our contributions. This paper makes two-fold contribution. Firstly, we propose a unified theory to analyze the privacy of mixture mechanisms within the framework of f-DP. Precisely, we derive an f-DP inequality for mixture distributions which implies the joint convexity of F F-divergences for any convex F. We name this result the "joint concavity of trade-off functions". as it is a lower bound for trade-off functions. The tightness of the joint concavity is also investigated. Moreover, the "advanced joint concavity of trade-off functions" which is an f-DP analog of the advanced joint convexity of the hockey-stick divergence and results in sharper bounds in certain cases.
propose
Building on our inequality, we have refined the privacy analysis of both shuffling models and DP-GD with random initialization using f-DP. Specifically, for shuffling models, we obtain trade-off functions dosed-form representation, leading to tighter bounds compared to existing state-of-the-ee results based on (e, DD... As for DP-GD, given the challenges in the trajectory analysis of multi-step iterations, we have chosen to explore more straightforward one-iteration DP-GD. We demonstrate that using random initialization significantly enhances the privacy of the output from a single iteration.
2

---

2 Preliminaries on differential privacy
Let D f2 C 2 be a fixed dataset of size n. Consider randomized algorithm A: 2" + S that maps a dataset to A(D) in some probability space S. Differential privacy requires that the change of one element in dataset has restricted impact on the output of A. Mathematically, we say A satisfies (e, 0DD for some 2 0 and 0 S 6 v 1
P[A(Da) E S) S E'P(((D)) E
for any event S E S and any neighboring datasets Do and Dj. When å = 0, we simply call (e, O)-DP that for small values of e and 8, it is challenging to distinguish
as c-DP. Based on the definition, between Do and Dj based on the outputs of A(o)) and A(D1), as the distribution of A(Do) closely resembles that of A(D1).
The definition of (CPP) corresponds to the hockey-stick divergence. Let P and Q be two distributions with probability density functions (pdfs) p and q, respectively. The hockey-stick divergence between P and Q is defined by (PIQ)) = I (p(æ) 7q(x)) dr for y 2 with ()+ ma. With little bit abuse of notations, in this paper, we define the divergence (or the trade-off function) between two random variables as the divergence (or the trade-off function) between their distributions. Then, a mechanism A is (e, 6)- if and only Hos ([ s 8 for any neighboring datasets Do and Dj which also implies He
S 5.
The Rényi-DP (RDP) is defined based-on the Rényi divergence. The Rényi divergence of order ä > 1 between /' and Q is given by
p((r) (xx)
& (x)dxx
Ra (PIIQ) ā log
For ā = or +00, Ri Rox is the limit of Rş ā tends to 1 or +oc A mechanism A is said to satisfy (ā, c)-RDP if Ra (A(())))
S c for any neighboring Do and D2.
The distinguishability between A(Du) and A(D;) ) aligns with the concept of f-DP. Consider hypothesis testing problem Ho Pvs.. H, Q and
can be quantified using hypothesis testing, which
rejection rule & [0, 1]. We define the type I error as Ep(Ø). which is the probability that we reject the null hypothesis Ho by mistake. The type error 3g
Ee (65 is the probability that we
accept the alternative H1 wrongly.
The trade-off function T(P, Q) the minimal type II error at level a of the type error, that is,
T(P, ()()) = inf as S aa.
We say a mechanism satisfies f-DP if ((D)) A(D,)) f for any neighboring datasets Dg and Dj. In particular, A is said to satisfy μ-GDP if GDP. where (z) (1-)) =t), for Iu 2 O, is the Gaussian trade-off function with being the cumulative distribution function (cdf) of N(O,, 1). A considered to be more private if the corresponding trade-off function takes larger values. When A achieves perfect privacy and A(D,) and A(D1) become completely indistinguishable, the trade-off function is Id(z) 1 Consequently, for any trade-off function f. we have f < Id.
We say trade-off function is symmetric if T(P. Q) T(Q, P). Note that a trade-off function may not necessarily be symmetric. But one can symmetrize it as shown in [14]. The symmetrization of trade-off function will be used when we analyze the shuffled mechanisms.
3 Joint concavity of trade-off functions
Let (P.) and {m be two sequences of probability distributions. Denote the probability density functions (pdfs) of P; and Q: as Pt and qt. respectivelly Consider the mixture distributions Pw
and Qw with pdfs Pw = mm i=1 WtP: and [w = Σ w.Ys, where the weight w = (wi.... wm)
such that w; 2 0 and Ei=10 w; = 1. The following lemma is bound the trade-off function
T(Pw. ). Upon finalizing this paper, we noted that Lemma 3.1 and Proposition 3.2 appeared independently in another paper 4p Theorem 8]. where they served different applications.
3

---

Lemma 3.1 (Joint concavity of trade-off functions). For two mixture distributions Pw and Qw. it holds
m/
T(Pw:Qw Qw)(((t,)))) 2
w (PP
is the type I error for testing Ps v.S. Q; using the likelihood ratio test and (rl1,c) c) = Ei=1 u0;0s, c).
where
(x) +eP xm=; 92 (X) = |
The main idea of the proof is make the mixture distributions more distinguishable by releasing the indices. Precisely, for X ~ Pw and Y ~ Qw, let X be random variable such that X = ~ P. with / being the indices, i.e., P[Z i] = w, Let (x|,, 1) be a random variable where we observe both X and the indices 1. Then, the right hand side of Lemma 3.1 is the trade-off function T((X)T, 7), TY) [)) between two joint distributions. This is lower bound for the trade-off function between mixture distributions because (X + X is data-independent post- post-processing procedure that only removes the observation of indices I, and DP immune post- post-processing
14
Under the setting of f-DP, usually require that the trade-off function is symmetric. The symmetry of the trade-off function in Lemma 5.1 is guaranteed by the following proposition.
Proposition 3.2. Suppose that for each i, T(P,, Qi) is a symmetric trade-off function. Then the trade-off function T [(X II) is symmetric.
The joint convexity of F-divergences plays an important role in the analysis of divergence-based DP for mixture mechanisms 4 22
We now show that Lemma is extension of the joint convexity of F-divergences, including the scaled exponentiation of the Rényi divergence and the hockey-stick divergence, trade-off functions. A trade-off function is always convex and thus differentiable almost everywhere. Thus, without loss of generality, we consider f; that is differentiable, symmetric, with (0) 1.
Proposition 3.3 (An application of Lemma 3.1 to the F-divergences). Let (r(Pl)Q) J F((())//(())))(( (())) be an F-divergence between any two distributions P and Q with some convex F. Then, for ft T(P:, Qi), we have
Dp S L{
J/ F (1PLOO) [f((z)) dr Σ w. (P.II..)....
Conversion from a trade-off function to F-divergences is straightforward using Section B in [4] However, conversion from F F-ddivereence to trade-off function is highly non-trivial. In fact, F-divergence an integral of functional of the trade-off function over the whole space while Lemma holds holds pointwisely, which is local property. This explains why the divergence-based DP not as informative as f-P since some information is lost due to the integration.
Privacy analysis of the shuffled mechanisms
In this section, explore the f-DP analysis of shuffled mechanisms. Drawing upon 2 23 the shuffling procedure incorporates a mixture of binomial noise. This noise can be tightly bounded using our f-DP inequality for mixture distributions.
4.1 Theoretical privacy guarantee
In shuffling models, the record of each user is privatized by some local randomizer (such as a randomized response mechanism (11) and all records then shuffled by curator. Mathematically, consider a dataset D = { C Z of size n and each data point 2; is privatized by an local randomizer Ao Z : Z that satisfies DD. Then, the mechanism A n 2n that maps D to D (Ao(z)) is co-DP. A shuffler Ashufte takes the privatized dataset D as input and applies uniformly random permutation D, which introduces the mixture of binomial noise A and results in privacy amplification.

---

As noted in [23,, the shuffling procedure introduces mixtures of binomial distributions. More specifically, the outputs generated by the shuffled mechanism for two neighboring datasets result from post-processing random variables X ~ P and Y Q with P = (1 w) Po + uQo and Q = (1 w)Qo + w wPo. where the weight w = -' and the distributions Po and Qo are defined as (A+ 1,C - A) ~ Po. and (A,C - A 1) ~ Qu with A ~ Sinom((,11 1/2) and C~ Bn - 1,2/ + 1)). is easy to see that Po is the mixture of {[A, + +,, ),)); with weights wT : IP[C = i] and Qo is the mixture of {(A,, - A. + +))) 1-1 with the same weights. In this context, Binom(k: p) is binomial distribution with parameters & E N and E [0, 1] and each A; is distributed as Binom(i. (i. 1/2). Advancing our analysis, we adopt the joint concavity, as outlined in Lemma 3.1 to establish a lossless bound for the trade-off function T T(Po, Qu).
Proposition 4.1. Let F; be the distribution function of Binom(i, 1/2) and let w P(C for C' ~ (n - 1,2/ 10 + 1)). Then, we have T(Po, Qo) is piecewise linear function with
n-1
T(Po, (a)(()t)) = Σ
{1-FF)
{1
(a)(())())))))
+ +1},
1=0
for each knot alt) = 0 :- iI 1-1
1+1 Remark. Proposition 4.1 holds with equality and the bound for T(Po: Qo) is sharp.
w. F.
i (i-
Before stating our results for T(P,Q) we define some notations related to f-DP. For a function g: IR- RR let ge (v) == max, aay ((x) be its convex conjugate. For trade-off function f be its symmetrization, where f-1 is the left inverse function of f. i.e.
let C(J) = mi f f(x
Theorem 4.2. The shuffled mechanism Ashufe o A is C(Sshume) Here Sshume [stume(a((t)) is piecewise linear function where each knot a(t) has the form
=(()==uf) W/ (.)a(()) 2-
w P.
i++1 t+1
E [0..1].
for all ( 120 0,
with F; being the distribution function of Binom(ii, 1/2) and 1 = PIC = -or C ~ Binom(n 1, 2/(e00 + +)), and the value of Jshhutti at a knot (x is
n-1 1 (1- (1 +1}1
fstmuti (a())) -2w Id(a(t)) + (1-2w)
with w- Iterm
1 and ld(x)= = 1 - x being the identity trade-off function.
Remark. The bound in Theorem 4.2 is near-optimal. In fact, the proof of Theorem is based on a post-processing procedure in 23 joint concavity (Proposition 4. and advanced joint concavity (Proposition 6.4.. The post-processing procedure is sharp for specific mechanisms, such as the randomized response mechanism, as shown by Theorem 5.2 and Theorem 5.3 in 23 Proposition 4.1 holds with equality and is optimal. The advanced joint concavity, which is an fDD analog of the advanced joint convexity in [ is optimal for specific distributions. Compared to existing analysis of shuffled mechanisms (e.g.. (23), the main advantage of using f-DP is that we avoid the use of Hoeffding's 's inequality and the Chernoff bound to bound the distance between Po and Qu in Proposi-
tion which is adopted in [22 2 and leads to loose bounds, to bound the mixture of binomial
distributions. Moreover, Theorem 3.2 in
X holds with an assumption eo < log
1).
Ing
which is removed by using f-DP in our paper.
To convert f-DP to ()-D,, we use the primal-dual perspective in |E! and obtain the following Corollary.
Limo witn (1+1 Eis up (t- +
Corollary 4.3. Let (t) ;=
with p; being the probability mass function of Binom (i, (12). Then, we have Ashumo A is (c, ())))))(()) for any c <> 0 with
Fi i te +1 ) + (1 2w)
t. 1 )
dr. = (-e² + 2w:)
Σ
i+1
Σ w F; i 1 i+1 1 1=0
1=0
where to = =inf(t: -2w + (1 2w) 2 -e¹} and w c
5

---

0.75
0.75
0.75
tradeoff
0.50
0.50
0.50
Type
1-DP
0.5
0.00
0.00
0.00
2
0.50
0.75
1.00
Type
Type error
Type
(a) = 5.444 1.444
(b) 60 = 4.444
(c) 3.444
Figure 1: A comparison between the trade-off function given by Theorem 4.2 and (c, ()-D) with
10000 and 1.5 given by 23
2 requires that co log 8lg[(2/8) 1)
4.444. Thus,
there is no result for 6)P when eg 4.444.
4.2 Numerical results and comparisons
To the best of our understanding, the leading privacy analysis for shuffled mechanisms is given in 233 In this section, we compare the privacy bounds from our Theorem 4.2 and Corollary 4.3 with those found in Theorem 3.2 of 23]. Additionally, we assess the tightness of our bound against the empirical lower bounds obtained through binary search.
Specifically, Figure presents comparison of the trade-off function derived from our Theorem to that of [23]. This comparison clearly illustrates that f-DP offers tighter privacy bounds, given that its trade-oft off function aligns closer to the identity trade-off function.
In our Table 1 we compare the values of ó)-Dp(e), as derived from Corollary 4.3 with 8(e) in [X3
The results indicate that (p-)p(e) is significantly smaller than 8(e).
In T we present é (-DP alongside the numerical upper bound of from 23 and the numerical lower bound determined by binary search. Given its closeness to the lower bound, our Theorem can be considered near-optimal.
Table 1: Comparisons with A
6
0.5
0.6
0.7
0.8
0.9
1.0
5 in [23
0.9494
0.3764
0.1088
0.0181
0.0018
8 x 10 5
0 (ours)
3
10
10
4 10
9
10
10
2 x 10
with the corresponding 8 derived from value of Eo 4.444 and n = 10000. Notably, oD-DP is significantly smaller than 6.
We compare 6y-DP obtained in Corollary 4.3
[ using fixed
Table 2: Comparisons with numerical results
8
5
10-5
3 x 10-6
10-7
4 x
10-9
9 x 10-11
f (ours)
0.4
0.5
0.6
0.7
0.8
Numerical c upper bound [23]
1.014
1.085
6g
6p
<g
Numerical e lower bound
0.369
0.470
0.575
0.664
0.758
We compare EDD obtained from Corollary 4.3 with the corresponding numerical upper bound
derived from 2 using fixed value of Eo 4.444 and 10000. For 8 < 10-? the bound
in 2 fails as the assumption co S log
[log(2/a) 1) is violated while our theory removes this assumption and holds for all cg- Moreover, we compare our theoretical upper bound with the empirical lower bound obtained by binary search in [3 which shows that our bound is near-optimal.

---

In summary, our non-asympiotic privacy bound for shuffled mechanisms outperforms Theorem 3.2 in 23 This improvement a result of our Proposition 4. which optimally refines Lemma A.4 in 23 Besides Proposition 4.1 the remainder of our proof of Theorem 4.2 closely adheres to the
methodology presented in [3 Our near-optimal result complicated due to its tightness. Thus, it is difficult to compare our result with the asymptotic bound in [ analytically.
5 Privacy analysis of one-iteration DP-GD with random initialization
A significant challenge in the privacy analysis of the last-iteration model of DP-SGD lies in accounting for multiple randomization techniques used during iterations. This includes aspects like initialization, iterative steps, and sub-sampling. Since these techniques incorporate mixture of random noise, the joint convexity of F-divergence becomes crucial in the privacy analysis of DP-SGD 45 2]. Our Lemma which provides unified perspective on these convexity notations, has driven to include it in the privacy analysis of DP-GD. Nevertheless, analyzing the trajectories from multi-step iterations remains complex. Therefore, our initial exploration is investigate the effects of random initialization on a one-step iterate. It's noteworthy that in machine learning, training a deep neural network using (stochastic) gradient descent combined with random initialization is widely adopted [36] The significance of random initialization in noisy gradient descent is also emphasized by 46 within the framework of Kullback-Leibler privacy.
Consider a dataset D = {(x,, y:));=1 with x; E IR being the features and y E R being the labels. Let ((0, D) be loss function and let 98,, D) be the gradient of l with respect to f. The output of one-step iteration of DP-GD initialized at 0g with step-size 1 is given by
((D) 0g (g(Oo, D) + +N o²)).
(1)
In the setting of random initialization, 0o is chosen
Gaussian random variable. Without loss of generality, we consider 0g- ~ (0, 1) and rewrite ((D) sr + +V o²) with sy sr
I g-g(I, D). ((D) is Gaussian random variable when the initialization is given, that is, (D)) i i~ (D), o²). Thus, we can regard ((D) as an infinite mixture of Gaussian distributions with continuous Gaussian weights {4(i) where ip is the pdf of I and the corresponding trade-off function ((O(D)), (D))) can be bounded using the joint concavity.
For simplicity, define ((D) 7 as random variable with a given initialization J. For two neighbor- ing datasets Do and D, it holds
T((O(D))IT,T) -
with X|1 .N(0,) 1) and Y|1 N(rr, 1) for 1 ~ (O 1), where μr = (g(1, - g(1, Do))/o. Theorem 5.1. Let ((D)) and ((Di) be defined in Q for neighboring datasets Do and Dj. Then, we have
Do(,)
T(B(D.), (()))) 2 E, ( m1) wo + o(t - p1) -1u
with t = tH and (t) E, (#(t)) [|urso] + ( | Here & is the cumulative distribution function (0, 1) and the expectation is taken with respect to T.
Remark. Note that Theorem 5. is instance- based privacy guarantee as it relies on the datasets.
To extend it to the worst case, we let pumax maxD,, D. [l Dimax) g(I, Drma)) (/maa]//or] | be the
sensitivity of the gradient with a given initialization As result, (D) output by one-step DP-
máe
GD is fDD with f(a(t)) = E, [ttppax j=p=*)], where tpax aupiix + and a(t)
E, [=(-=xax)] The worst case trade-off function is bounded for strongly convex loss functions with a bounded data domain.
To numerically evaluate the trade-off function in Theorem 5. we consider an example Do (z,,,4))² with y a.; and 2 1 for some constant and we defined Dj by removing an arbitrary element in Do. Moreover, we assume that o = 1. Note that for this example without gradient clipping, the gradient is linear in I and ((D)) is the sum of two Gaussian random variables which is Gaussian. Thus, the trade-off function has a closed-form representation. In general, the output is non-Gaussian and we should adopt Theorem 5.1 For example, if we consider gradient clipping [1 9 and replace g( D) by the clipped gradient
(0)
(8. D) max (1, (0)
with (0) = (y: -0x,)(-2)
7

---

where the gradient of each data point g( is cut off by some constant > 0, then /r7 is given by
1
|a 1| S C a 2 C S -c
C,
which is not Gaussian. In this example (0, D) + (0, is considered as c-GDP if we disregard the effects of random initialization since the sensitivity of ge is c.
We illustrate the trade-off function of Theorem 5.1 computed numerically in Figure where we also compare it with c-GDP for 1 and varying values of Overall, the figure suggests that random initialization can amplify the privacy of DP-GD, as our bounds outperform those of c-GDP, which does not take into account the randomness of initialization. Furthermore, increases, the amplification effect caused by random initialization becomes more significant, since the difference between 7 T( T), (YI,,) and c-GDP also increases. This is reasonable, since the randomness resulting from initialization comes from such that la I| I c, whereas for |a I > c, fi remains constant and no randomness is introduced. Thus, the random initialization introduces greater levels of randomness as c increases.
observe that as
It is worth noting that in this example, without gradient clipping, we have 1 wupax dominate pair are two Gaussian distributions N (O, 1) and (0, The Rényi DP fails to measure the privacy of initialization. In fact, it holds Rş ()]l 2)) oo for ā large enough.
/ and the
1.00
Type II error
0.75
0.75
0.75
c-GDP
0.50
T(XIL
0.25
0.25
0.25
0.00
0.00
0.00
0.25
0.50
0.75
1.b0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Type emor
Type emor
Type error
(a) 0.5
(b) 2
(c) c =3
Figure 2: Trade-off functions for linear models with a = 1.
6 Optimality of joint concavity and advanced joint concavity
In this section, first explore the sufficient and necessary conditions under which Lemma 3 holds with equality. While Lemma i is generally not sharp, we introduce an f-DP analog of the advanced joint convexity of the hockey-stick divergence from 4 yielding tighter bounds in certain applications.
Recall the distributions P= (1 - Po wQu and Q - (1-11 + wPo that appear in the shuffled mechanisms. Bounding the trade-off function T(P, Q) directly using the joint concavity leads to loose bound (cf., Figure 3b). For the scenarios where Lemma i. not tight, introduce the fDDP analog of the advanced joint convexity of (c, 6DP 4 that may lead to tighter bounds and term it the "advanced joint concavity of trade-off functions".
The following proposition presents a necessary and sufficient condition for Lemma 3.1 to hold with equality.
Proposition 6.1. For m = 2, Lemma 3.1 holds with equality if and only if wi w (X)
E
wig1 wrgg
wi EL (X) + W2 22 (X) with X ~ Pw. where for px(X)/q((X) 0/0 and p3 (X)) (X) + 0/0 with m i + j, we set pi (x))q
m2
(x())/q)(X))
is not difficult to see that Po and Qo in shuffling models satisfy this necessary and sufficient condition when n 2.
As we discussed, Lemma may not be sharp in general. The following lemma about the advanced joint convexity of the hockey-stick divergence, which is slight generalization of Theorem 2 in 4
8

---

1.00
1.00
0.85
Type error
0.75
Advanced
Type ererr
0.90
0.50
0.25
0.00
Joint concavity
0.00
0.00
0.00
0 0.25
0.50 0.75 1.00
Type
Type I error
(a) Top-left corner of Figure 3b for small type error As the parameters (e,6) 8) computed by the trade-off function only depend on small a. ad- vanced joint concavity leads to tighter bound.
(b) Trade-off functions obtained by (advanced)
joint concavity. For example, for w 1/3 and 0.5, 8 derived from Lemma 6.3 1.5 10 while that from Lemma 3.1 is 0.0020.
Figure 3: Comparison between joint concavity (Lemma 3.1 and advanced joint concavity (Lemma 6.3
Lemma 6.2. For any non-negative é', co. 7, and satisfying exp(e') = (1 - exp((()))) + wexp((1) and exp(eo) - w)> exp(e1 Jun exp(e')w, have
ae ((1 Pi + w)) Σ - (1-w)
+
(2)
(Pill(1-7)Q) + 702) + wHar (Pal(11 - n)Q1 + +
Lemma 6.2 is reduced to the advanced joint convexity of the hockey-stick divergence
when
Pi = -1, by minimizing the right-hand-side of 2 with respect to 7, 7) 6n, and 61.
Recall the convex conjugate g" of function g defined by g" (y) sup, supx(ry g(z)} and C(f)
ff f-11"* which is the symmetrization of f. We have the following advanced joint concavity of trade-off functions.
Lemma 6.3 (Advanced joint concavity). Suppose that T(P.,QU) is symmetric for each Then, for
0 < w < 1, we have
T((1 P P1 + w nP2, (1 - w)Q1 + #x22)
2 c (1 (1--w)) w1(( Fi. + w01 - F2 + -i-Fi,, + wn
for arbitrary 0 S 7 < < 5n 1, where Feg(x) is given by FI,(()) S (x (=11-
(m-w)
and F2,((1) = S2, [w((-22) and the trade-off functions are defined us T(P,, Qi) for
(w--))
1 $ i,j S 2. Moreover, for T(( - P1 + wP2 w))-=))100) + wQ2)
w, it holds
2 20(1- (Pi, (1- w)Q1 wQ2) + wT (P2, (1 w)Q: + +w2))
Determining the trade-off functions using advanced joint concavity can be challenging in many practical situations. In fact, to apply the advanced joint concavity, one need to specify the choice of 17 by maximizing the right-hand-side of Lemma 6.3 Therefore, in real-world applications, we often rely on both joint concavity and advanced joint concavity.
For P = (1 w)Po + wQu and Q (1 w)Qo + wPo in shuffling models, we have the following bound derived from Lemma 6,3
(1 w) Po + wQo and Q (1 - w)Qu + wPo with some weight 0 S w < 1/2, we have T(P. Q) > C (2wld + +1 (Po. Qo)).
Propusition 6.4. For
The equality in Proposition 6.4 does not hold exactly. However, this lower bound almost the tightest closed-form expression. One may refer to Section E.I.I in the appendix for the proof details.

---

7 Discussion
This paper provides reñnedd privacy bounds for mixture mechanisms, including shuffling models and DP-GD with random initialization. For shuffling models, we present bound that is tighter than existing results based on (e, 6D- In the study of DP-GD, we demonstrate how random initialization can amplify privacy concerns. These bounds are derived using unified f-DP approach based on the joint concavity and advanced joint concavity of trade-off functions. We also investigate the sharpness and other properties of these concavity notions.
In our future work, we plan extend our analysis from one-step DP-GD to multi-step DP-SGD. For DP-SGD with multiple iterations, it is crucial to consider subsampling and privacy amplification by iteration in the privacy accountant, in addition to the randomness introduced by shuffling and random initialization. While there is an f-DP bound for subsampling provided in an independent work 42,, , as far as we know, there is limited research on f-DP results regarding privacy amplification by iteration.
Beyond DP-SGD, we intend to extend our theory to the privacy analysis of other key applications that involves various randomization techniques. These include the shuffled Gaussian mechanism for federated learning, discussed in [25] and the composition of mixture mechanisms. For extending our theory to federated learning, we might adopt the f-DP framework outlined in [4]]. Addressing
the composition of mixture mechanisms demands examination of the tensor product between trade-off functions. This is complex task, even when dealing with the simplest mixture mechanisms like sub-sampling, as highlighted [51].
Acknowledgments
Weijie Su was supported in part by Meta Research Award and NSF through CCF1934876.
Reza Shokri was supported by a Google PDPO Faculty Research Award, Intel within the www www.private- ai.org center, Meta Faculty Research Award, the NUS 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.
References
[1] Martín Abadi, Andy Chu, Ian J. Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Edgar R. Weippl. Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 308-318. ACM, 2016.
[2] Jason M. Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. NeurlPS, 2022.
[3] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. In Mare Aurelio Ranzato, Alina Beygelzimer. Yann N. Dauphin, Percy Liang. and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021. virtual, pages 17455-17466, 2021.
[4] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[5] Gilles Barthe and Federico Olmedo. Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs. In Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings. Part 40, pages 49-60. Springer, 2013.
[6] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014 4, Philadelphia, PA, USA, October 18-21, 2014, pages 464-473 IEEE Computer Society, 2014.
10

---

[7] David Blackwell. Equivalent comparisons of experiments. The annuls of mathematical statistics, pages 265-272, 1953.
[8] Jomathan M. Borwein and Adrian S. Lewis. Convex analysis and nonlinear optimization, volume 3 of CMS Books in MathemattesOOvrraes de Mathématiques de la SMC. Springer, New York, second edition, 2006. Theory and examples.
[9] Zhiqi Bu, Jinshuo Dong Qi Long, and Weijie Su. Deep learning with Gaussian differential privacy. Harvard Data Science Review, 2(3), Sep 30 2020. https://hdsr. htt.:dds..mmppessiii....o.. wtt..cdd///uuuuu2ii//....
[10] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing. STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 74 86, ACM, 2018.
[11] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. IACR Cryptol. ePrint Arch., page 816, 2016.
[12] Kamalika Chaudhuri, Claire Monteleoni. and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12:1069 1109, 2011.
[13] Albert Cheu, Adam D. Smith, Jonathan R. Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology EU- ROCRYPT -0t9-38th Annual International Conference the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part volume 11476 Lecture Notes in Computer Science, pages 375-403. Springer, 2019.
[14] Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. J. R. Stat, Soc. Ser. Stat. Methodol., (4),,44,4, 2022. With discussions and a reply by the authors.
[15] Jinshuo Dong. Weijie J. Su, and Linjun Zhang- A central limit theorem for differentially private query answering. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Perey Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14 2021, virtual, pages 14759- 14770, 2021.
[16] Cynthia Dwork. Differential privacy. In Michele Bugliesi, Bart Preneel. Vladimiro Sassone, and Ingo Wegener, editors, Automuta, Languages and P Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 1-. Springer, 2006.
[17] Cynthia Dwork. Differential privacy: A survey of results. In Manindra Agrawal, Ding- Du, Zhenhua Duan, and Angsheng Li. editors, Theory and Applications of Models Compulation, 5th International Conference, TAMC 2008, Xi an. China, April 25-29, 2008. Proceedings, volume 4978 of Lecture Notes in Computer Science, pages 1-19. Springer, 2008
[18] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothhlum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. Michael Mitzenmacher, editor, Proceedings of the 41st Anmual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD. USA, May 31 June 2, 2009, pages 38 381-390. ACM, 2009.
[19] Cynthia Dwork and Aaron Roth, The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4)221 1-7777, 2014.
[20] Cynthia Dwork and Guy Rothblum. Concentrated differential privacy. CoRR, abs/ abb//663.01187, 2016.
[21] Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Frank Neven, Catriel Beeri, and Tova Milo, editors, Proceedings of the SScony ACM SIGACT-SIGMOR SIGMOD-SIGART SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 21 211-222. ACM, 2003.
[22] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shufffing. In 62nd IEF. Annual Symposiun on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 954-964, IEFE, 2021.
[23] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 CMMM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25 2023, pages 4966 4981. SIAM, 2023.

---

[24] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In Mikkel Thorup, editor, 59th IEEE Annual Symposiun on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 521-532. IEEE Computer Society, 2018.
[25] Antonious M. Girgis, Deepesh Data, Suhas N. Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of differential privacy in federated learning. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 2521-2529. PMLR, 2021.
[26] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In Marina Meila and Tong Zhang. editors, Proceedings the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021. Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 5213-5225, PMLR. 2021.
[27] E. L. Lehmann and Joseph P. Romano. Testing statistical hypotheses. Springer Texts in Statistics. Springer, New York, third edition, 2005.
[28] Ximing Li, Chendi Wang, and Guang Cheng. Statistical theory of differentially private marginal- data synthesis algorithms. In The Eleventh International Conference on Learning Representations 2023.
[29] Ryan McKenna, Gerome Miklau, and Daniel Sheldon. Winning the NIST contest: A scalable and general approach to differentially private synthetic data. J. Priv. Confidentiality. 11(3), 2021.
[30] Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pages 263 275. JEEE Computer Society, 2017.
[31] Iyya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint 1908. 10530, 2019.
[32] Xiaosheng Mu, Luciano Pomatto, Philipp Strack, and Omer Tamuz. From Blackwell dominance in large samples to Rényi divergences and back again. Econometrica, 89(1)47755006, 2021.
[33] Sewoong Oh and Pramod Viswanath. The composition theorem for differential privacy. CoRR, abs/1311.0077, 2013.
[34] Maxim Raginsky. Shannon meets Blackwell and Le Cam: Channels, codes, and statistical experiments. In 2011 IEEE International Symposium Information Theory Proceedings, pages 1220-1224. IEEE, 2011.
[35] Igal Sason and Sergio Verdú, f-divergence inequalities. IEEE Trans. Inf. Theory, 62(11):5973 6006. 2016.
[36] Ilya Sutskever, James Martens, George E. Dahl, and Geoffrey E. Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 1139 1147, JMLR. org. 2013.
[37] Reihanch Torkzadchmahani, Peter Kairouz, and Benedict Paten. DP-CGAN: differentially private synthetic data and label generation. CoRR, abs/2001.09700. 2020.
[38] Tim van Erven and Peter Harremoës. Rényi divergence and Kullback-Leibler divergence. CoRR, Abs/1226.2455 2012.
[39] Hua Wang. Sheng Gao, Huanyu Zhang, Milan Shen, and Weijie J Su. Analytical composition of differential privacy via the Edgeworth accountant. arXiv preprint arXiv:2206.04236. 2022.
[40] Yu- Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 1226-1228 PMLR, 2019.
[41] Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In Themis Palpanas and Kostas Stefanidis, editors. Proceedings of the Workshops of the EDBT/ICDT 2016 Joint Conference, EDBT/CCTT Workshops 2016, Bordeaux, Frunce, March 15, 2016. volume 1558 of CEUR Workshop Proceedings. CEUR-WS.org 2016.
[42] Zhanyu Wang, Guang Cheng, and Jordan Awan. Differentially private bootstrap: New privacy analysis and inference strategies. arXiv preprint 40X01:2210.06100, 2023.
12

---

[43] Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. J. Amer. Statist. Assoc., 105(489):375-38. 2010.
[44] Shirong Xu, Chendi Wang, Will Wei Sun, and Guang Cheng. Binary classification under local label differential privacy using randomized response mechanisms. Transactions Machine Learning Research. 2023.
[45] Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). In NeurIPS, 2022.
[46] Jiayuan Ye, Zhenyu Zhu, Fanghui Liu, Reza Shokri, and Volkan Cevher. Initialization matters: Privacy- utility analysis of overparameterized neural networks. NeurIPS, 2023.
[47] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. CoRR, abs/2109.12299 2021.
[48]
Jun Zhang, Graham Cormode, Cecilia M. Procopiue, Divesh Srivastava, and Xiaokui Xiao. PrivBayes: Private data release via Bayesian networks. ACM Trans. Database Syst., 42(44)25:1-25:41, 2017.
[49] Qinqing Zheng, Shuxiao Chen, Qi Long, and Weijie
Federated f-differential privacy. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021. Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 2251 2229.. PMLR, 2021.
[50] Qinqing Zheng, Jinshuo Dong Qi Long, and Weijie J. Su. Sharp composition bounds for Gaussian differential privacy via edgeworth expansion. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 11420-1 1435. PMI.R, 2020.
[51] Yuqing Zhu, Jinshuo Dong, and Yu- Xiang Wang. Optimal accounting of differential privacy via charac- teristic function. In Gustau Camps Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 4782-4817. PMLR, 2022.
[52] Yuqing Zhu and Yu- Vu-Xiang Wang. Poission subsampled Rényi differential privacy. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedingy of Machine Learning Research, pages 7634-7642, PMLR, 2019.
13


Reviews:
[{"review_id": "A1TqLD3LvQ", "reviewer": "Reviewer_jEfn", "summary": "This paper studies improving the analysis of privacy bounds for two randomization processes (privacy amplifications): shuffling models (where each user record is privatized by some local randomizer like randomized response mechanism) and differentially-private gradient descent (DP-GD, where a Gaussian noise is added to the gradient update at each iteration). Previous bounds were given for the standard $(\\epsilon, \\delta)$-DP bound, while this paper analyzes through $f$-DP, a differential-privacy bound considering the trade-off between type I and type II errors (like the $f$-score), using some joint convexity arguments.\n\nWhen translating the $f$-DP bounds back to bounds on $\\epsilon$ and $\\delta$, this paper gets much tighter bounds that works for more general ranges of $\\epsilon$ and $\\delta$.", "questions": "After Proposition 4.8, the paper writes “One may refer to the supplementary materials for details”, but this reader is unsure where are the supplementary materials.", "limitations": "The theoretical results in this paper does not have broader societal impacts.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The improvement in DP bounds are non-negligible and more general, and the presentation is convincing.", "weaknesses": "Certain critical aspects of the proofs might be better explained: the proof depends on some close-form expressions of piecewise linear functions (Theorem 3.1, Corollary 3.2, Proposition 4.3), which might have meaning beyond just those arithmetic manipulations or expressions as is currently shown in the paper. A one- or two-sentence description, or some simple examples, might help here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments and valuable suggestions regarding our paper, particularly in acknowledging our main contributions. In response to the raised questions and weaknesses, we would like to provide the following explanations:\n\nResponse to the weakness:\n\nIn the revised version, we have explained the expressions of the trade-off functions derived in Theorem 3.1 in Section 3.1. Additionally, we have provided a comprehensive explanation of the trade-off function for testing two discrete distributions using the Neyman-Pearson lemma, employing the simple Bernoulli distribution as an example in Appendix A.\nThe trade-off function for testing two discrete distributions is known to be piecewise linear, a well-established result based on the Neyman-Pearson lemma. In this context, the slope of each line segment is $-Prob_{X\\sim Q}[p(X)/q(X) = t]/Prob_{X\\sim P}[p(X)/q(X) = t],$ which is constant as $t$ only relies on the knots, in the Neyman-Pearson lemma.\nFor example, for testing two Bernoulli distributions $Bern(p_0) v.s. Bern(p_1)$ with $p_1 > p_0$, the trade-off function is piecewise linear with 3 knots: $(0,1), (p_0, 1 - p_1)$, and $(1,0)$.\nSince the shuffling procedure introduces the mixture of binomial noise, which is a discrete distribution, the trade-off functions presented in Theorem 3.1, Corollary 3.2, and Proposition 4.3 are also piece-wise linear with numerous knots due to the mixture.\n\n\nResponse to the Question:\n\n\nWe acknowledge the confusion regarding the presentation of the proof of Proposition 4.8, which is contained implicitly in the proof of Theorem 3.1 in Section B.1.2 in the submitted version.\nPrecisely, in Section B.1.2, the content before line 542 is the proof of Proposition 4.8.\nTo address this, we have made the necessary modifications. Specifically, we have updated the title of Section B.1 to \"Proofs of Proposition 4.3, Proposition 4.8, and Theorem 3.1.\" Additionally, we have divided Section B.1.2 into two separate sections, one focusing on the proof of Proposition 4.8 and the other on the proof of Theorem 3.1. This reorganization aims to improve clarity and facilitate better understanding for the readers.\n\n"}, {"review_id": "Hd3OSQSiAu", "reviewer": "Reviewer_s9n5", "summary": "This paper studies an important problem in DP: the privacy quantification based on a mixture of randomness. Based on f-DP, the authors point out the joint concavity of the tradeoff function. Two potential examples are proposed, including the shuffling model and the privacy amplification from random initialization. ", "questions": "1. How to really apply the privacy amplification results in 3.2 under regular input-independent f-DP scenario?\n\n2. What the fundamental challenge to generalize the results to the subsampling case? I think the subsampled f-DP is already solved in \"Deep Learning with Gaussian Differential Privacy\" (https://arxiv.org/abs/1911.11607). \n\n3. For the theoretical analysis, can you characterize the improvement compared to previous works?  \n\n4. It would be more helpful if the authors can elaborate the background of shuffling model, at least why the output distributions from two adjacent datasets are in the form described at the beginning of Section 4. \n ", "limitations": "## Update after reading the authors responses: \nI summarize my concerns and suggestions for the authors to improve this paper:\n1. As I said, I always like the idea of privacy amplification from random initialization and this is an important open question widely-recognized in DP community. But the authors's results on this part, from my opinion, is trivial given that it can only study closed-form iterate distribution for the first round and thus negligible amplification in DP-SGD, and the authors agreed to put it as a minor contribution in the revision.\n\n2. I think some claims in the paper are overblown and the limitations of the proposed methods are not properly discussed. At least to me, the joint convexity thing in the tradeoff function is not that surprising given that Poisson subsampling has already been studied in Gaussian DP. The authors also agreed that their improvement over the subsampling case is limited either for i.i.d. sampling or with a fixed batch size. \n\n3. For the main contribution to the shuffling model, I never say that there is no novelty in this paper. I agree that the paper presents tighter bounds on some special cases, for example with additional assumptions on the ordering tradeoff function or special mixture weights. But for the shuffling model, the advantage is only measured empirically without a clear asymptotic analysis. As I mentioned, a small constant improvement on the $\\epsilon$ can lead to exponential improvement on $\\delta$. The authors' response on this part is somewhat double talk and constantly say they simulate it and it is better than prior works. But my question is always how better it is and the authors did not  directly give an answer to show analytical bound of improvement. Anyway, I suggest the authors clearly discussing about both the advantages and limitations. ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+ The problem studied is important to the privacy analyses of many applications. In particular, I really like the idea to consider the privacy amplification from the random initialization.\n\n+ The introduction and the potential limitation are nicely written. Motivation is clear. \n\n+ The improvement upon the privacy analysis on shuffling model seem interesting.", "weaknesses": "- Though I really like the idea to take the randomness of initialization into account and study its privacy implication, the results presented in Section 3.2 are not convincing. The claimed simulatable f-DP guarantees seem to be instance-based, or is with respect to a given adjacent datasets $D_0$ and $D_1$. Moreover, even for the particular instance-based guarantee, there is no analysis provided, such as high confidence bound, to allow us really apply this bound to produce rigorous privacy guarantee. Moreover, (please correct me if I get it wrong), based on my understanding, applying the joint concavity, Theorem 3.5 is essentially determined by the average case of the \"local\" sensitivity given the random initialization. So, I guess current studies cannot be generalized to the standard worst-case DP guarantee. \n\n- The notations are confusing. For example, I did not find the formal definition of $(\\theta(D)|I,I)$ in Section 3.2. My best guessing is because there are two random sources? But why we must assume the noise and random initialization are in the same distribution? \n\n-  Section 3.1 is lack of theoretical analysis on how tighter the f-DP bound given in Theorem 3.1 is, as compared to previous works. Though the empirical improvement on the $\\delta$ numbers seem significant, given that the dependence of $\\epsilon$ on $\\delta$ is in logarithm, it is not very clear whether such improvement is general. Another missing issue is the explanation on the computational accuracy $10^{-6}$ in Table 1. Where is this restriction coming from? Moreover, I think one major motivation to introduce f-DP in [14] is for tighter composition. The authors may also want to take it into consideration. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback on our paper and insightful comments. We have carefully considered the raised questions and weaknesses and offer the following responses and modifications. The reference number here is aligned with the supplementary materials.\n\nResponses to weaknesses:\n1. The first item. Section 3.2 is convincing but it has some restrictions, and in the revised version, we have added one paragraph discussing extension of Theorem 3.5 to the worst case and its restrictions:  In Theorem 3.5, given the initialization $I$, the sensitivity of the gradient $\\mu_I = \\mu_I(D_0, D_1)$ depends on choices of two neighboring datasets $D_0$ and $D_1$. To extend this to the worst-case, we consider the noiseless linear models with least squares loss (Example 3.3 and 3.4), which is also used in practice (https://arxiv.org/abs/2006.08212). \nIn fact, $\\mu_I (D_0,D_1)\\equiv a - I$ when $D_1$ is constructed by deleting $\\bf{arbitrary}$ element in $D_0$.\n\n    For more complicated models, such as those with general convex loss functions, the analysis of $\\mu_I$ is involved and will be addressed in our future study of DP-SGD. As discussed in the end of this section, even for this simplest linear model, we observe privacy amplification while R'enyi DP fails to account for the privacy amplification.\n\n\n     Overall, the DP-GD part is not as promising as our results on shuffling models but it is still novel and is convincing with specific applications.\n\n2. The second item. We acknowledged the potential misinterpretation of notations and have added an explanation for this notation in Sections 3 and similar notations in Section 4. Specifically, $(\\theta(D)|I, I)$ denotes the observation of both $\\theta(D)|I=i\\sim\\mathcal{N}(\\mu_i,1)$ and the initialization (index) $I$. This is a relaxation of observing the mixture distribution $\\theta(D)$ (a mixture of $\\mathcal{N}(\\mu_i,1)$ as stated in Line 167-168) without knowing the information of the index $I$. As observing the index exposes more information, distinguishing $\\theta(D_0)$ and $\\theta(D_1)$ is harder than distinguishing $(\\theta(D_0)|I, I)$ and $(\\theta(D_1)|I, I)$, which motivates Lemma 4.1 and Theorem 3.5. Releasing the index is essential to make the mixture distributions distinguishable (e.g., Example F.4 is not distinguishable without releasing indices). Moreover, we do not assume that $\\theta(D)|I$ has the same distribution as $I$, although the initialization is usually Gaussian in practice. The expectation in Theorem 3.5 is taken w.r.t. $I$ and $I$ can be any distribution.\n\n3. The first question of the third item. The tightness of Theorem 3.1 was discussed in Section 4 in the submitted version and we have added one more paragraph in Section 3.1 discussing the tightness in theory in the revised version.\nThe bound is near-optimal in theory, and it represents a significant enhancement compared to [23].The proof of Theorem 3.1 is based on a post-processing procedure in [23], the joint concavity (Proposition 4.3), and the advanced joint concavity (Proposition 4.8). The post-processing procedure is sharp for specific mechanisms, such as the randomized response mechanism, as shown by Theorem 5.2 and Theorem 5.3 in [23]. Proposition 4.3 is also sharp, as demonstrated in Section 4. Based on the proof of Proposition 4.8 in Section B.1.2 before line 542, the advanced joint concavity used in this example is almost the tightest closed-form bound that can be derived. Compared to [23], the main advantage of using $f$-DP (Proposition 4.3) is that we avoid the use of Hoeffding's inequality and Chernoff bound to bound the mixture of binomial distributions, which is adopted in [22, 23] and leads to loose bounds.\nMoreover, Theorem 3.2 in [23] holds with an assumption on the local privacy budget $\\epsilon_0$ which is removed by using $f$-DP in our paper.\nAdditionally, based on Table 3 and 4 in the pdf attached, our bound is near-optimal as it is close to the numerical lower bound computed by privacy auditing. \n\n4.  The second question in the third item. The accuracy $10^{-6}$ was due to calculating the dual function in Matlab. We have refined our code, and now the accuracy can be $10^{-20}$ as shown in the attached pdf.\n\n5. The third question in the third item. The composition property is a fundamental aspect of differential privacy (DP) and composition + shuffling will also be investigated in our future study. However, it differs from our current privacy analysis. Specifically, computing the privacy of DPSGD through composition requires releasing the parameters (models) output by every iteration while our primary focus lies in analyzing the privacy of the last-iterate parameter without disclosing intermediate ones (cf., [2,43] for the analysis using RDP). Although our present paper only examines the one-step iteration, we are actively extending it to DP-SGD in the future. This extension is highly non-trivial. The role of joint concavity (Lemma 4.1) is crucial, building on insights from the analysis in [43] for RDP.\n\nResponses to the questions:\nQuestion 1 & 3 are answered in Item 1 & 3 above.\n\n6. Question 2: Besides the simplest sampled mechanism in [9,14], there are other sampling mechanisms such as Poisson sampling or sampling with replacement. For sub-sample mechanisms, one may refer to [4] for privacy analysis, where the joint convexity and advanced joint convexity of the hockey-stick divergence play important roles. Our Lemma 4.1 and Lemma 4.7 are extensions from the hockey-stick divergence to trade-off functions.\n\n7. Question 4: We have taken the reviewer's suggestion and added a detailed citation (Theorem 3.2 in [23]) and provided clear explanations at the beginning of Section 4 to better elucidate the post-processing procedure. As we mentioned earlier, this post-processing technique from [23] is highly effective for specific mechanisms, making our $f$-DP bound near-optimal.\n\n"}, {"review_id": "KBvX1eIloS", "reviewer": "Reviewer_oyTp", "summary": "Randomization is an essential too in deriving differentially private algorithms. However, sophisticated randomization techniques such as shuffling induce complicated distributions on outputs, making analysis of privacy loss difficult. The paper uses the framework of f-differential privacy to provide tighter analysis on the privacy guarantees of shuffled DP-SGD than existing methods do. Additionally, the authors show that randomized initialization can beneficially improve privacy guarantees for one step problems.", "questions": "NA", "limitations": "-\tThe authors fairly discuss the limitations of their work, in particular their intentions to study multi-step SGD with random initialization.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tThe closed-form bounds for shuffled DP-SGD seem particularly important, even if the bounds are complicated. Table 1 does a good job of convincing the reader that the obtained bounds are significantly better than existing ones.\n-\tMoreover, the authors present some useful results for studying tradeoff functions in the f-DP framework. These will likely be useful for future investigations.\n", "weaknesses": "-\tResults for random initialization for one-step SGD do not seem particularly useful? In particular, this contribution seems like a bit of a toy problem.\n-\tSome demonstration of the improved bounds for Shuffle-SGD would be useful to the reader. In particular, it would be convincing if there was some simple learning task on which the accuracy of the model produced by shuffle-SGD (under the new analysis) significantly outperformed the model produced under the old analysis. This should happen for any experiment, as the privacy budget savings seems to be significant per table 1.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive comments and acknowledgment of the novelty of our results. In response to the identified weaknesses, we provide the following explanations:\n\n1. Response to the first item. In Section 3.2, we applied Theorem 3.5 to analyze privacy amplification in noiseless 1-dimensional linear models, where the sensitivity of the gradient $\\mu_I$ with a given initialization $I$ can be specified. It is worth noting that similar results are applicable to multidimensional linear models, where $y_i = a^T x_i$ and $x_ix_i^T = \\mathbb{I}$ with $\\mathbb{I}$ being the identity matrix. Noiseless linear models find relevance in various applications, as exemplified in the work by Berthier et al. (2020) titled \"Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model.\"\n\n     For more general applications, such as general convex loss functions, deriving $\\mu_I$ becomes more intricate and deserves further investigation, which we plan to address in our future study on the privacy of multi-step DP-SGD.\n\nOverall, the DP-GD part is not as promising as our results on shuffling models but it is still novel with applications to specific examples.\n\n2. Response to the second item. We are grateful for your valuable suggestions regarding the experiments. As mentioned by Feldman et al. (2020), it is indeed possible to analyze the privacy of shuffled DP-SGD when the number of iterations is given. However, despite extensive literature review on shuffling models, we have not come across any experimental results involving running shuffled DP-SGD. We have compiled a list of related papers, including a survey paper, but due to the constraints of time for this rebuttal, we intend to present our experimental results for shuffled DP-SGD in a subsequent study.\n\n\n    To make our theory more convincing, we added one paragraph in Section 3.1 regarding the tightness of Theorem 3.1 as follows: The bound in Theorem 3.1 is near-optimal in theory, and it represents a significant enhancement compared to [23], as demonstrated in Table 1 and Figure 1. In fact, the proof of Theorem 3.1 is based on a post-processing procedure in [23], joint concavity (Proposition 4.3), and advanced joint concavity (Proposition 4.8). The post-processing procedure is sharp for specific mechanisms, such as the randomized response mechanism, as shown by Theorem 5.2 and Theorem 5.3 in [23]. Proposition 4.3 is also sharp, as demonstrated in Section 4. Based on the proof of Proposition 4.8 in Section B.1.2, the advanced joint concavity used in this example is almost the tightest closed-form bound that can be derived. Compared to [23], the main advantage of using $f$-DP (Proposition 4.3) is that we avoid the use of Hoeffding's inequality, which is adopted in [22, 23] and leads to loose bounds, to bound the mixture of binomial distributions. Moreover, Theorem 3.2 in [23] holds with an assumption on the local privacy budget $\\epsilon_0$, which is removed by using $f$-DP in our paper.\n\n    Besides, we compared our upper bound with the numerical lower bound obtained by inference attacks which shows that our bound is near-optimal, as shown in Table 4 in the attached pdf.\n\n\nhttps://arxiv.org/pdf/2208.04591.pdf\n\nhttps://arxiv.org/pdf/2012.12803.pdf\n\nhttps://arxiv.org/pdf/2107.11839.pdf\n\nhttps://arxiv.org/pdf/2303.07160.pdf\n\nhttps://arxiv.org/abs/2105.05180\n\nhttp://proceedings.mlr.press/v139/ghazi21a/ghazi21a.pdf"}, {"review_id": "TJN0441AWX", "reviewer": "Reviewer_wgR7", "summary": "One of the main challenges the differential privacy frame work is facing these days, is the gap between the variety of randomization techniques applied in the machine learning community for various reasons, and our limited capability to prove the privacy amplifications they entail. Among primary examples we can mention random initialization and shuffling techniques.\n\nThe authors of this paper leverage the known connection between DP and hypothesis testing, specifically relaying on the newly presented notion of f-DP, to transition the analysis of the effect of these mechanism from the domain of privacy loss distribution to the domain of hypothesis testing, where they prove several key results. Combining these results with the known implications between f-DP and DP, they provide tighter bounds for privacy amplification by shuffling and new results for privacy amplification by random initialization (for the limited setting of one gradient step).", "questions": "i will appreciate some clarification regarding the choices made in the evaluation presented in figure 1, and the chosen baseline.", "limitations": "N/A", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper partially fills a long time gap in our understanding of the way privacy is improved by introducing various random steps to the learning algorithm. Unlike most previous works, the authors use the newly presented f-DP definition and the known implications between it and the DP definition, to analyze the effect of these randomization techniques on the trade-off function.\n\nThe contribution of this paper extends beyond its results, as the proof techniques presented in it might be used for the analysis of other potential amplification techniques as well.", "weaknesses": "At first glance, I got the impression that the results of this paper aim to provide guarantees using a separate notion of privacy, which cannot be compared to DP. This is indeed not the case, thanks to the known implications between DP and f-DP, but I found the current presentation somewhat confusing regarding this point, and I recommend the authors clarify it in the final version.\n\nI found some of the choices made in the numerical evaluations presented in Figure 1 to be not so clear. First of all, the sample size was chosen to 1,000 while the reference paper used 10,000, and $\\delta$ was chosen as $1/n$ while it is often expected to be of the order $o(1/n)$.\n\nA more substantial issue with the comparison presented in Figure 1 has to do with the presented baseline. If I understand correctly, the baseline results were chosen to be those of the closed-form presented in [20], but that work contains tighter results presented in Theorem III2, which can be numerically evaluated, and should be presented as the more relevant comparison.\n\nMinor comments:\n\n* In line 104, the inequality if a functional inequality, but this notion was not presented before, so the notation is somewhat confusing.\n\n=======\n\n**Edit after rebuttal discussion:**\n\nThe authors response satisfied my remaining concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your extremely positive rating and valuable comments. Thanks to your feedback, we revisited the numerical results of Feldman et al. (2023) and compared them with our own. The comparison showed that our methods outperformed their numerical upper bound. Additionally, we conducted a comparison with their numerical lower bound, which, to the best of our understanding based on their code, is obtained using binary search for privacy auditing. The results demonstrated that our bound is near-optimal. The reference number here is aligned with the supplementary materials. Below, we provide detailed responses.\n\nResponses to the weaknesses:\n\n\n1. The choices in Figure 1. We initially used a sample size of $n=1000$ and set $\\delta = 1/n$ as a simple example to demonstrate the sharpness of our $f$-DP bound. In response to the reviewer's suggestion, we have now updated Figure 1 and Table 1 with $n=10000$ and $\\delta = o(1/n)$ which is in line with exisiting literature [23]. Please refer to the attached PDF for both the updated figure (Figure 5) and the new table (Table 3&4). Here, we display a simplified table with $\\epsilon_0 = \\log\\left(\\frac{n}{8\\log (2/\\delta)} - 1 \\right) = 4.444$, which is the critical value required by Theorem 3.2 of Feldman et al. (2023) with $\\delta = 10^{-6}$. It is worth noting that this assumption, caused by Hoeffding's inequality, is removed in our $f$-DP analysis, as we utilize Lemma 4.1 instead of Hoeffding's inequality. As seen in the updated table, our bound still significantly outperforms previous results.\n\nTable 3 in the attached pdf:\n\n\n$\\epsilon$:   0.5             |      0.6     |    0.7    |    0.8     | 0.9       ｜ 1.0            ｜1.1\n\n $\\delta$ in [23]:  0.9494  |  0.3764 | 0.1038 | 0.0181 ｜0.0018 | $8 * 10^{-5}$| $2 * 10^{-6}$  \n\n $\\delta_{f-DP}$:  $3 * 10^{-6} |  10^{-7}  |   4* 10^{-9} |  9 * 10^{-11} | 2 * 10^{-12}| 2 * 10^{-14}| 3* 10^{-16}$\n\n\n2. Thank your for pointing out the minor errors in line 104. The functional inequality means the inequality holds pointwisely, which is pointed out in the revised version.\n\n\nResponses to the weaknesses:\n\n\n3.  Choosing the numerical upper bound in [23] as the baseline. In the submitted version of our paper, we solely compared our results with the theoretical upper bound presented in [23]. However, following the reviewer's suggestion, we reevaluated the numerical results in [23] and conducted a more comprehensive comparison with their work. For this comparison, we selected $n=10000$, and $\\epsilon_0$ was set to $4.444$, aligned with Item 1. The results of this comparison are listed in Table 4 in the attached PDF and we listed the simplified one below. It is important to note that for very small values of $\\delta$, the numerical results in [23] remain invalid due to their assumptions on $\\epsilon_0$ in their Theorem 3.2.\n\n     Additionally, we also compared our results with the numerical lower bound generated by inference attacks in [23]. This comparison further substantiates that our $f$-DP analysis is indeed near-optimal. From a theoretical standpoint, this near-optimality can be interpreted by considering the basis of our proofs. The proof of Theorem 3.1 relies on a post-processing procedure in [23], the joint concavity (Lemma 4.1 and Proposition 4.3), and the advanced joint concavity (Proposition 4.8). The post-processing procedure is sharp for specific mechanisms, such as the randomized response mechanism, as demonstrated by Theorem 5.2 and Theorem 5.3 in [23]. Proposition 4.3 also exhibits sharpness, as highlighted in Section 4. Furthermore, based on the proof of Proposition 4.8 in Section B.1.2, the advanced joint concavity utilized in this example is nearly the tightest closed-form bound attainable.\n\nTable 4 in the attached pdf:\n\n\n$\\delta$:  $5 \\times 10^{-5}| 3 \\times 10^{-6} | 10^{-7}| 4 \\times 10^{-9}| 9 \\times 10^{-11}| 2 \\times 10^{-12}| 2 \\times 10^{-14}$\n\n$\\epsilon_{fdp}$ (ours):   $0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0$\n\n  Numerical $\\epsilon$ upper bound in [23]:  $1.014  |  1.085 | \\epsilon_0 | \\epsilon_0 | \\epsilon_0 | \\epsilon_0 | \\epsilon_0$  \n\n   Numerical $\\epsilon$ lower bound:  $0.369 | 0.470 | 0.575 | 0.664 | 0.758 | 0.845| 0.944$\n\n"}, {"review_id": "c38CJNmxZk", "reviewer": "Reviewer_xB9B", "summary": "This paper introduces a framework for analyzing mixture distributions via $f$-DP and its tradeoff function. Additionally, the paper leverages this framework for improving bounds for shuffling mechanisms in DP, and the same framework to prove a statement about privacy of a single-step of gradient descent from random initialization.", "questions": "Simply a summary of some of my stream-of-consciousness comments above:\n\n* Could you comment more extensively on relation to prior results? Is the analysis here _always_ stronger?\n* Similarly, could you comment on the relation to https://arxiv.org/pdf/2304.05007.pdf? I listed my understanding of the way these relate above, but looking for some clarity here.", "limitations": "Tightness or lack thereof of particular results was discussed. Negative social impacts not immediately applicable.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper addresses a fundamental problem in DP: computing effective estimates on additive mixtures of random variables. Methods of analysis for these mixtures are, to date, reasonably ad-hoc and certainly not known to be tight. This paper presents a clean unified approach, making connections to more abstract and clean mathematically-posed problems (IMO, this is the manner in which DP should imagine evolving itself, away from its CS + statistics formulations, which are often focused on data structures and properties of particular random variables). Not only does this paper formulate a nice presentation, but  to my knowledge it improves existing statements through this framework. Clear accept.", "weaknesses": "\nWriting some nits no presentation that came up from a stream of consciousness read below. Not necessarily all weaknesses, just comments.\n\n* I would prefer a slight reordering of the content. AFAICT, the main logical flow is: Lemma 4.1 -> Prop 4.3 -> Thm 3.1, with the rest of the stuff more or less as add-ons (though FWIW i have not yet read the section on advanced concavity). I would really prefer this logical flow to be more clear. Ideally, for me, we would present the proofs straight through, beginning with the lemmas. However, I get that this is CS and we don't really do that here. I think a reasonable option is to sketch the proof in the main body, or discuss that the major results seem to follow primarily from the fairly simple Lemma 4.1, plus some calculations, given the reduction introduced by [20]. This logical flow is simple and quite nice, and IMO it should be highlighted on its own terms.\n\n* Editorially, I would suggest pushing the DP-GD stuff into an appendix. I think it confuses the message, and it's not clear either how extensible it is (presumably it breaks after one step due to the injected dependence? Though I could imagine conditioning on stuff and invoking nested mixtures, this may be prohibitively difficult since IIUC Gaussian-ness will go away). \n\n* Confusion on 'the outputs of two neighboring datasets are post-processing of r.v.s $X$ and $Y$' (beginning of section 4). Going back to the reference, it seems like the technical meat there is effectively a good reduction to scalar-valued random variables (if  I read correctly, the content of their Thm 3.1)--presumably that is what is invoked here? But it reads as if the development were restricted to scalar-valued mechanisms (which I assume it is not).\n\n* Setup to 4.1: the way that $X$, $Y$, and $I$ are coupled is unstated. Meaning: in the setup here, it is possible that $I$ is independent of $X$ and $Y$ (in which case $X|I$ and $Y|I$ would just be $X$ and $Y$). I guess the coupling is something like, e.g. $X$ is coupled with $I$ such that $X|\\{I=i\\} \\sim p_i$? But if so, I don't see this stated anywhere before the proof of Lemma 4.1.\n\n* I know this is not how CS papers are generally written, but (being an old mathematician myself) I would really personally prefer to read this paper straight through and without applications, building up to an improved analysis (which I assume is Thm 3.1), then closing with discussion of relation to prior results and tightness.\n\n* Speaking of relation to prior results, and putting my CS hat back on: this could really use some deeper dives / commentary. I would recommend cutting the DP-GD stuff (or pushing to an appendix) and extending the discussion of relationship to prior bounds. For example: there is a table showing $\\delta$s for varying $\\epsilon$s at a fixed $\\epsilon_0$. What happens when we vary this $\\epsilon_0$ over a wide range--are the results here _always_ better (and qualitatively similar)? Or are there some regimes in which previous analyses were tighter?\n\n* Following the citations of [20] leads me to https://arxiv.org/pdf/2304.05007.pdf. Glancing through this paper, it seems to me that one major difference with the present work is that this work claims improved amplification relative to [20] _independent_ of mechanism structure, whereas that work improves their bounds in the case of some particular mechanisms (and their worst-case bounds, for general mechanisms, are identical). Is this correct? Can you speak to this relationship?\n\n* One confusing thing on a read-through: it is difficult to find the proof of proposition 4.3. This proof can be found in the 'technical details for section 3.1', which is not where a reader like me would look right away (given, in particular, that there is an appendix section on proofs for section 4).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your extremely positive feedback and your valuable comments. I have organized the responses to the weaknesses and questions as follows, corresponding to the 8 items in weaknesses. The reference number provided here aligns with the supplementary material, which slightly differs from the 9-page paper.\n\n1. We have taken your advice into account concerning the structure of our paper. Initially, we highlighted the theoretical part as you metioned, but we finally moved it behind the applications section in the submitted version. This adjustment is aimed at enhancing the paper's accessibility to a wider audience, particularly NeurIPS readers, given the statistical nature of the theory. After careful consideration, we have opted to retain the current structure with certain modifications. We have clarified the proof of Theorem 3.1, which relies on both Proposition 4.3 (implied by Lemma 4.1) and Proposition 4.8 (a result of Lemma 4.7). In the submitted version, a proof sketch is contained at the beginning of Section 4 implicitly which has also been highlightened in the revised version. Moreover, a detailed citation and some discussions regarding the post-processing in [23] has also been provided at Section 4.\n\n\n2. We sincerely value your feedback regarding the DP-GD section (Section 3.2). In the submitted version, we show that it can be applied to noiseless linear models with least squares loss, which are also used in practice (cf., https://arxiv.org/abs/2006.08212). We acknowledge the need to address more general models and the difficulty to clarify the sensitivity $\\mu_I$ with given $I$ for general models and loss functions. While we have decided to retain this section, we included more discussions on the extensions and restrictions in the revised version.\n\n\n3. Both $X$ and $Y$ are 2-dimensional vector-valued random vectors, representing mixtures of binomial distributions.  As you indicated, the primary contribution of [23] is that they propose a promising post-processing procedure to convert the multi-dimensional shuffled model to 2-dimensional random vectors, which makes the likelihood ratio easy to verify.\n\n4. We have addressed the potentially confusing notation $(X|I, I)$ and introduced further clarification: $(X|I, I)$ means we observe two random variables, $X|I$ and $I$, where $X$ follows a mixture distribution $\\sum_{i=1}^m w_i p_i$, and $I$ represents the information of indices with $\\mathbb{P}[I=i] = w_i$. $X|I$ denotes $X|I=i \\sim p_i$. As releasing the indices exposes more information, the couple $((X|I, I), (Y|I, I))$ is more separable than $(X, Y)$ without knowing the indices, which motivates Lemma 4.1.\n\n5. We have introduced an explanatory paragraph regarding tightness immediately following Theorem 3.1: The bound in Theorem 3.1 is near-optimal in theory, and it represents a significant enhancement compared to [23], as demonstrated in Table 1 and Figure 1. In fact, the proof of Theorem 3.1 is based on a post-processing procedure in [23], joint concavity (Proposition 4.3), and advanced joint concavity (Proposition 4.8). The post-processing procedure is sharp for specific mechanisms, such as the randomized response mechanism, as shown by Theorem 5.2 and Theorem 5.3 in [23]. Proposition 4.3 is also sharp, as demonstrated in Section 4. Based on the proof of Proposition 4.8 in Section B.1.2, the advanced joint concavity used in this example is almost the tightest closed-form bound that can be derived. Compared to [23], the main advantage of using $f$-DP (Proposition 4.3) is that we avoid the use of Hoeffding's inequality, which is adopted in [22, 23] and leads to loose bounds, to bound the mixture of binomial distributions. Moreover, Theorem 3.2 in [23] holds with an assumption on the local privacy budget $\\epsilon_0$, which is removed by using $f$-DP in our paper.\n\n   Consequently, our bound is always better than the theoretical bound in Theorem 3.2 in [23] as Proposition 4.3 is tight and an $(\\epsilon,\\delta)$-DP version of Proposition 4.8 was also adopted in [23].\n\n6. In line with Item 5, we have discussed the tightness of the shuffling models in the revised version. Additionally, we have included Figure 6 in the attached pdf about varying $\\epsilon_0$ for your reference.\n\n\n    Considering the DP-GD stuff, we discussed the application and extensions from noiseless linear models as stated in Item 2. Since the revised paper does not exceed the pages required by the camera-ready version, we decided to keep this content.\n\n7.  Thank you for introducing the concurrent work https://arxiv.org/pdf/2304.05007.pdf. After reading through their paper, as you mentioned, one difference is that they analyze specific local randomizers satisfying certain assumptions. Their tightness is to design a tighter post-processing procedure (in comparison to [23]) to reduce the coupled distributions to the mixture of binomial noise for specific local randomizers. Their analysis of the mixture distribution similarly rests on Hoeffding's inequality, which, as discussed in Item 5, is refined by our Proposition 4.3. Combining their novel post-processing with our tight analysis of mixture distributions could potentially yield tighter bounds, an exciting avenue to explore.\n\n8. We have updated the title of Section B.1 to \"Proofs of Proposition 4.3, Proposition 4.8, and Theorem 3.1.\" Additionally, we have divided Section B.1.2 into two separate sections, one focusing on the proof of Proposition 4.8 and the other on the proof of Theorem 3.1. This reorganization aims to improve clarity and facilitate better understanding for the readers.\n\n"}]

Author rebuttal:
We greatly appreciate the reviews from all the reviewers, which have contributed to the thoroughness of our paper. We have attached a 1-page PDF here that provides detailed comparisons and extra numerical results.
Furthermore, we have noticed several frequently asked questions and would like to emphasize our responses as follows. Here the reference number is aligned with the supplementary materials, which is slightly different from the 9-page paper due to the appendix.

1. The tightness of Theorem 3.1 for shuffling models: Our Theorem 3.1 offers a near-optimal bound.

    Theoretically, we have added one paragraph right behind Theorem 3.1 to illustrate its near-optimality: 

    The proof of Theorem 3.1 is based on a post-processing procedure in [23], joint concavity (Proposition 4.3), and advanced joint concavity (Proposition 4.8). The post-processing procedure is sharp for specific mechanisms, such as the randomized response mechanism, as shown by Theorem 5.2 and Theorem 5.3 in [23]. Proposition 4.3 is also sharp, as demonstrated in Section 4. Based on the proof of Proposition 4.8 in Section B.1.2 (the content before line 542 is the proof of Proposition 4.8 and is clarified in the revised version), the advanced joint concavity used in this example is almost the tightest closed-form bound that can be derived. Compared to [23], the main advantage of using $f$-DP (Proposition 4.3) is that we avoid the use of Hoeffding's inequality and the Chernoff bound, which is adopted in [22, 23] and leads to loose bounds, to bound the mixture of binomial distributions. Moreover, Theorem 3.2 in [23] holds with an assumption on the local privacy budget $\epsilon_0$, which is removed by using $f$-DP in our paper.

     Numerically, we compare our theoretical bound with the numerical upper bound in [23] and the numerical lower bound obtained by privacy auditing in Table 4 in the attached PDF, which shows that our theoretical bound is near-optimal as it closely aligns with the lower bound.

2. The notation $(X|I,I)$ in Section 4 is confusing, and we have addressed this concern in the revised version. Specifically, we clarified the definition as follows: $(X|I, I)$ means we observe two random variables, $X|I$ and $I$, where $X$ follows a mixture distribution $\sum_{i=1}^m w_i p_i$, and $I$ represents the information of indices with $\mathbb{P}[I=i] = w_i$. $X|I$ denotes $X|I=i \sim p_i$. As releasing the indices exposes more information, the couple $((X|I, I), (Y|I, I))$ is more separable than $(X, Y)$ without knowing the indices, which motivates Lemma 4.1.

3. In Section 3.2, we applied Theorem 3.5 to analyze privacy amplification in noiseless 1-dimensional linear models (Example 3.3 and 3.4), where the sensitivity of the gradient $\mu_I$ with a given initialization $I$ can be specified. It is worth noting that similar results are applicable to multidimensional linear models, where $y_i = a^T x_i$ and $x_ix_i^T = \mathbb{I}$ with $\mathbb{I}$ being the identity matrix. Noiseless linear models find relevance in various applications, as exemplified in the work by Berthier et al. (2020) titled "Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model."

     For more general applications, such as general convex loss functions, deriving $\mu_I$ becomes more intricate and deserves further investigation, which we plan to address in our future study on the privacy of multi-step DP-SGD.

Overall, the DP-GD part is not as promising as our results on shuffling models but it is still novel with applications to specific examples.


Meta-review: The paper analyzes mixture mechanisms via f-DP and the corresponding tradeoff function. Using this method, the paper improves bounds for shuffled mechanisms for DP and applies it to DP-GD. The paper seems to have good contributions, however reviewers point out several issues including the writing, choice of numbers in experiments. I strongly encourage authors to incorporate all the reviewer comments before the camera ready version.
Decision: Accept (poster)