Renyi Differential Privacy of The Subsampled Shuffle Model In Distributed Learning
Authors: Antonious M. Girgis
Deepesh Data
Suhas Diggavi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential privacy
Renyi divergence
distributed learning
privacy amplification via shuffling
privacy composition.

Abstract: We study privacy in a distributed learning framework, where clients collaboratively build a learning model iteratively through
interactions with a server from whom we need privacy. Motivated by stochastic optimization and the federated learning (FL) paradigm, we focus on the case where a small fraction of data samples are randomly sub-sampled in each round to participate in the learning process, which also enables privacy amplification.  To obtain even stronger local privacy guarantees, we study this in the shuffle privacy model, where each client randomizes its response using a local differentially private (LDP) mechanism and the server only receives a random permutation (shuffle) of the clients' responses without their
association to each client. The principal result of this paper is a privacy-optimization performance trade-off for discrete randomization mechanisms in this sub-sampled shuffle privacy model. This is enabled
through a new theoretical technique to analyze the Renyi Differential Privacy (RDP) of the sub-sampled shuffle model.  We numerically demonstrate that, for important regimes, with composition our bound
yields significant improvement in privacy guarantee over the state-of-the-art approximate Differential Privacy (DP) guarantee (with strong composition) for sub-sampled shuffled models. We also demonstrate numerically significant improvement in privacy-learning performance operating point using real data sets. Despite these advances, an open question is to bridge the gap between lower and upper privacy bounds in our RDP analysis.

Rényi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning
Antonious M. Girgis
Deepesh Data UCLA deepesh. data@gmail com
Suhas Diggavi UCLA subasciggeavibucla..dd edu
UCLA amgirgis0g. wcla.ellaeeeooo
Abstract
We study privacy in distributed learning framework, where clients collaboratively build learning model iteratively through interactions with a server from whom we need privacy. Motivated by stochastic optimization and the federated learning (FL) paradigm, we focus on the case where small fraction of data samples are randomly sub-sampled in each round to participate in the learning process, which also enables privacy amplification, To obtaín even stronger local privacy guarantees, we study this in the shuffle privacy model, where each client randomizes its response using a local differentially private (LDP) mechanism and the server only receives random permutation (shuffle) of the clients' responses without their association to each client. The principal result of this paper is a privacy- optimization performance trade-off for discrete randomization mechanisms in this sub-sampled shuffle privacy model. This is enabled through a new theoretical technique to analyze the Rényi Differential Privacy (RDP) of the sub-sam sub-sampled shuffle model. We numerically demonstrate that, for important regimes, with composition our bound yields significant improvement in privacy guarantee over the state-of-the-arr approximate Differential Privacy (DP) guarantee (with strong composition) for sub-sampled shuffled models. We also demonstrate numerically significant improvement in privacy-learnin data sets. Despite these advances an open question is to bridge the gap between lower and upper privacy bounds in our RDP analysis.
performance operating point using real
1 Introduction
As learning moves towards the edge, there is need to collaborate to build learning models]] such as in federated learning [36. 44 33). In this framework, the collaboration is typically mediated by a server. In particular, we want to collaboratively build a learning model by solving an empirical risk minimization (ERM) problem (see ( in Section 2}. To obtain model parametrized by 0 using ERM, the commonly used mechanism is Stochastic Gradient Descent (SGD) [12) However, one needs solve this while enabling strong privacy guarantees on local data from the server, while also obtaining good learning performance, i.e., a suitable privacy-leaming performance operating point.
Differential privacy (DP) [18] is the gold standard notion of data privacy that gives rigorous framework through quantifying the information leakage about individual training data points from the observed interactions. Though DP originally proposed in framework where data resides centrally 18], for distributed learning the more appropriate notion of local differential privacy (LDP) 35 17 Here, each client randomizes its interactions with the server from whom the data is to be kept private (e.g., see industrial implementations [23 31 16]). However, LDP mechanisms suffer
'Thi is because no client has access to enough data to build rich learning models locally and we do not want to directly share local data.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

from poor performance in comparison with the central DP mechanisms [17
32).
To overcome
this. new privacy framework using anonymization has been proposed in the so-called shuffled model [22] (25 6
5 15 7 []. In the shuffled model, each client sends her private message to secure shuffler that randomly permutes all the received messages before forwarding them to the server. This model enables significantly better privacy-utility performance by amplifying DP through this shuffling. Therefore, in this paper we consider the shuffle privacy framework for distributed learning.
26
In solving 2 using (distributed) gradient descent, each exchange leaks information about the local data, but we need as many steps as possible to obtain good model; setting up the tension between privacy and performance. The goal is to obtain as many such interactions as possible for given privacy budget. This is quantified through analyzing the privacy of the composition of privacy mechanisms. Abadi et al. [I] developed framework for tighter analysis of such compositions, and this was later reformulated in terms of Rényi Differential Privacy (RDP) 37 , and mapping this back to DP guarantee (38] Therefore, studying RDP is important to obtaining strong composition privacy results, and is the focus of this paper.
In distributed (and federated) learning, a fraction of the data samples are sampled; for example, with ran- dom client participation and stochastic gradient descent (SGD), which can be written as
Oc+1 c 0, -1k
Σ R(V)((.)).
I
where R is the local randomization mechanism and I are the indices of the sampled data. This is a subsampled mechanism that enables another privacy amplification opportunity; which, several cases, is shown to yield a privacy advantage proportional to the subsampling rate; see [355 22.. The central technical question addressed in this paper is how to analyze the RDP of an arbitrary discrete mechanism for the subsampled shuffle privacy model. This enables us to answer the overall question posed in this paper, which is an achievable privacy-learning performance trade-off point for solving (2) in the shuffled privacy model for distributed learning (see Figure T. Our contributions are:
d2
d2
dg d
ds
Figure 1: An iteration from the CLDP- SGD Algorithm, where clients are ran- domly chosen at each iteration. Each client sends the private gradient Rp (gi (d:)) to the shuffler that randomly permutes the gradients before passing them to the server.
We analyze the RDP of subsampled mechanisms in the shuffle framework by developing a novel bound applicable to any discrete Lp-LPP mechanism as a function of the RDP order X, subsampling rate y, the LDP parameter co, and the number of clients n: see Theorem The bound explicit and amenable to numerics, including all constants
2 Furthermore, the bounds are valid for generic We also provide a lower bound for the RDP in 2 We prove our upper bound (Theorem Th using the following novel analysis techniques: First, we reduce the problem of computing the RDP of sub-sampled shuffle mechanisms to the problem of computing ternary - (3] of shuffle (non sub-sampled) mechanisms; see Lemma 2 Then we reduce the computation of the ternary |x| of shuffle mechanisms for a generic triple of neighboring datasets to those that have a special structure (see Theorem 5 this reduction step is one of the core technical results of this paper. Then we bound the ternary -x of the shuffle mechanisms for triples of neighboring datasets having special structures by bounding the Pearson- Vajda divergence [43] using some concentration properties (see Theorem
LDP mechanisms and all parameter regimes y Theorem
Using the core technical result in Theorem I we amalyze criveeyconveergenc trade-offs of the CLDP-SGD algorithm (see Algorithm T) for Lipschitz convex functions in Theorem 3 This partially resolves an open question posed in [27]], to extend their privacy analysis to RDP and significantly strengthening their privacy guatantees.
Numerically, we save factor 14x in privacy (e) over the best known results for approximate
DP for shuffling [24] combined with strong composition [34] for T 10a 7 0.001, 10
and a factor of 2.5x better than the best known RDP for shuffling bound (29 combined with the sub- sampsan result in 43) Translating these to perrccy-prformancee operating point in distributed
2 As emphasized in "in differential privacy, constants matter".
3 'Some of the best known approximate DP bounds for the shufile model parameter regimes in terms of n, 6, co. etc.
7
24 are restricted to certain

---

optimization, over the MNIST data set with Es clipping we numerically show gains: For the same privacy budget of 1.4, we get test performance of 80% whereas using strong composition the test performance of [24] is 70%; furthermore, we achieves 90% accuracy with the total privacy (with strong composition) achieves the same accuracy with a total privacy budget of = 4.82. See Section 4 and the supplementary material for more results.
budget c = 2.91, whereas,
Related work: We give a more complete literature review in Appendix and focus here on the works that are closest to the results presented in this paper.
Private optimization in the shuffled model: Recently, [2] and 27 28 have proposed differentially private SGD algorithms for federated learning, where at each iteration, each client applies an LDP mechanism on the gradients with the existence of secure shuffler between the clients and the central server. However, the privacy analyses in these works developed approximate DP using advanced composition theorems for DP (e.g., (20 34)), )), which are known be loose for composition [T]. To the best of our knowledge, analyzing the private optimization framework using RDP and subsampling in the shuffled model new to this paper.
Subsampled RDP: The works 38 45 have studied the RDP subsampled mechanisms without shuffling. They demonstrated that this provides tighter bound on the total privacy loss than the bound that can be obtained using the standard strong composition theorems. The RDP analysis of subsampled mechanisms in the shuffledd privacy framework has not been studied before F this paper. The RDP of the shuffled model was very recently studied in (29], but without incorporating subsampling, which poses new technical challenges, as directly bounding the RDP of subsampled shuffle mechanisms non-trivial. We overcome this by reducing our problem of computing RDP to bounding the ternary |x| -P,, and bounding the latter is core technical contribution of our paper.
and is new to
Paper organization: We give preliminaries and problem formulation in Section main results (upper and lower bounds, and privacy-convergencce tradeoff) in Section []] numerical results in Section 4 proof of the upper bound Section 5] and proof of the ternary DP of the shuffle model in Section Omitted details/proofs from this paper given in the supplementary material.
2 Preliminaries and Problem Formulation
We use several privacy definitions throughout this paper. Among these, the local and central differen- tial privacy definitions are standard and we defer them to Appendix [ The other privacy definitions (Rényi DP and ternary IXI*-DP) are relatively less standard and we define them below.
We say that two datasets 'D = {di,..., dn} E X and D' = (d',..., (and denoted by D D if they differ in one data point, i.c., there exists an E [n] such that d: # di and for every j E [n]],] # i, we have d, = dzy.
.,. d',, E X are neighboring
Definition 1 ((), <) RDDP (Rényi Differential Privacy) 37). A randomized mechanism M ::44 X + y is said to have e- Rényi differential privacy of order À E (1, oo) (in short, (), (DD)- if for any neighboring datasets D, D' E X"", the Rényi divergence of order À between M(D) and M(D') is upper-boundes by e(A), i.e.,
1 - log EaLMron
[MMD10)) )1) < <E(A),
DX(M())IM((D))
(I)
where (!) denotes the probability that M on input D generates the output 0.
Definition (ÇTTernayy |x| -dffeerrrtllt privacy (3)). randomized mechanism M : X' + Viis said to have (-ternary-lxl" -DP D,, if for any triple of mutually adjacent datasets D, D', D" E X (i... they mutually differ in the same location), the ternary-Ix| divergence of MDD), M(D)),
MM(D)) M(D'),M(')) is R)), ie..
upper-bounded by aa for all 2 1 (where Ç is function from R+ to R
= EM(D") [
M(D) M(D) M(D")
Dix!'
< (c(a)))
'One naive approach is to plug in the RDP analysis of shuffle model 22 into the results of 43) however. direct analysis of subsampled mechanisms yields better results in several interesting regimes; Section 4
3

---

The ternary -DP was proposed in 43 to characterize the RDP of the sub-sampled mechanism without shuffling. In this work, we analyze the ternary Ix| DD of the shuffled mechanism bound the RDP of the sub-sampled shuffle model.
We the following result for converting the RDP guarantees of mechanism to its central DP guarantees. To the best of our knowledge, this result gives the best conversion.
Lemma 1 (From RDP to DP
13 4. Suppase for any À > 1, a mechanism M is (A, (A))-RDP. Then, the mechanism M is (e, 6DP, where is arbitrary and is given by
min c (A) + log (1/8) + (A 1) log (1 1/2) - log (A)
Problem formulation: We consider a distributed private learning setup comprising a set of n clients, where the ith client has data point d, drawn from universe X' for i E [ni]; see also Figure Let D (d1....; dn) denote the entire training dataset. The clients are connected to an untrusted server in order to solve the following empirical risk minimization (ERM) problem
1 Σ 1(0.d)))
min F(O,D): =
where C C Rd is a closed convex set, and ʃ C D + R is the loss function. Our goal is to construct global learning model 0 via stochastic gradient descent (SGD) while preserving privacy of individual data points in the training dataset by providing strong DP guarantees.
We revisit the CLDP-SGD al- gorithm presented [27] and described in Algorithm to solve the ERM 2 In each step of CLDP-SGD, we choose uniformly at random a set Uh of n
Algorithm 1 Acup:: CLDP-SGD
Input: Datasets D (dl,..., (is...,ddy,,, LDP privacy parameter co. gradient norm bound C², and learning rate schedule }m,}.
1: Initialize: 0g C
2: for t [T' do
of & < n clients clients. Each client E Uh computes and clips the f--norm f (0c, d() to apply the LDP mechanism Ry. where R2 By
3: Client sampling: A random set Ue of & clients is chosen.
4: for clients E Ue do
5:
Compute gradient: ge (d.) + Vo.f f (0,, d,)
of the gradient Ve,
Clip gradient: g (d,) + gt (d:) max {1, (I
6:
C
{0, 1) is an CD-LDP mechanism when
7:
Client sends R. (gr (d,)) to the shuffler.
8:
end for
inputs come from an f--norm
9:
Shuffling: The shuffler sends random permutation of
ball. In (27], the authors pro- posed different LDPLDP mecha-
(Rp (B. (d)) ; E Ue} to the server.
10:
Aggregate: B, 1/2 Exeu, Rp (Be (d4)
nisms for general -o-morm balls. After that, the shuffler randomly permutes the received & gra- dients RR, (g: (d4))) and sends them to the server. Finally, the server takes the average of the received gradients and updates the parameter vector. Our main contribution in this work is to present stronger privacy analysis of the CLDP-SGD algorithm by characterizing the RDP of the sub-sampled shuffle model.
11: Descent Step: 0c+1 Il (0, mcB.), where II is the projection operator onto the set C.
12: end for
Output: The model Or and the privacy parameters e, 6.
3
Main Results
In this section, we present our main results. First, we characterize the RDP of the subsampled shuffle mechanism by presenting an upper bound in Theorem aand a lower bound in Theorem 2 We then
present the privacy-convergence trade-offs of the CLDP Algorithm in Theorem 3
Consider arbitrary CD-LDP mechanism R, whose range is discrete set [B] {1, {1...., B) for
some B E N := (1.2.3....] Here, [B] could be the whole of N. Let M(D) be a subsampled shuffle mechanism defined follows: First subsample I clients of the clients (without replacement), where denotes the sampling parameter. Each client out of the & selected

---

clients applies R on d, and sends R(d;) to the shuffler who randomly permutes the received k inputs and outputs the result. To formalize this, let H+ y + y*k denote the shuffling operation that takes & imputs and outputs their uniformly random permutation. Let sampl x + X denote the sampling operation for choosing a random subset of k elements from a set of n elements. We define the subsampled-shufft mechanism as
M (D) ;= Hs sampp (R (d.).....,
..... R (dn)).
(3)
Observe that each iteration of Algorithm [ be represented as an output of the subsampled shuffle mechanism M. Thus, to analyze the privacy of Algorithm it sufficient to analyze the privacy of a sequence of identical T subsampled shuffle mechanisms, and then apply composition theorems.
Histogram notation. It will be useful to define the following notation. Since the output of H4 is random permutation of the outputs of R (subsampling is not important here), the server cannot associate the l messages to the clients; and the only information it can use from the messages is the histogram, i.e., the number of messages that give any particular output in [B]. We define a set A as
B
A h = (h) (hi....,hh hR): : Σh₂
h k
(4)
denote the set of all possible histograms of the output of the shuffler with k inputs. Therefore, we can assume, without loss of generality (w..lo.g.), that the output of .M is a distribution over A
Our main results for the RDP of the subsampled shuffled mechanism (defined in (3)) are given below. Our first result provides an upper bound (stated in Theorem [and proved in Section 5) and the second
result provides a lower bound (stated in Theorem (add proved in Appendix Dj.
Theorem (Upper Bound). For any n E N, l: < n, to 2 O, and any integer 2 2, the RDP of the
subsampled shuffle mechanism M (desined in (3)) is upper- cooper-bounded by
A
00
1)2
(2(22e 1)2
3/2
<(() S x-1 log
1 1++ 4
+
+ r
2
Tee
Tre2ro
5=3
where 1: _2000_ J + 1,
7=
n. and r (2)
So
dx is the Gamma function. The term Y is x2-le-
given by Y 1 +
220 -1- 11 dg
2g
2000-11 0
86
550
Theorem 2 (Lower Bound). For any n E, k S nu, ED 2 O, and any integer X 2 2, the RDP of the subsampled shuffle mechanism M (defined in (3) is lower-bounded by
(1+ 1+ (1+ 2 (+(2))
1
22 (6 1)2
(c200 -12
k
(A)) 2 1 log
Σ
E
keeo
keFo
eco
where expectation taken w.r.t. the binomial F.V. m Bin (k.p) with parameter p= T
Our CLDP-SGD algorithm and its privacy-convergee
trade-offs (stated in Theorem 3 beloww are
given for a general local randomizer R, (whose inputs comes from an b,-ball for any p E 1, oo)) that
satisfies the following conditions: (i) The randomized mechanism R, is an LpPLP mechanism. (ii) The randomized mechanism R2 is unbiased, i.e., E [R (x) |x] = x for all E (a( where a is the radius of the ball Bp. (iii) The output of the randomized mechanism R2 can be represented using B E N+ bits. (iv) The randomized Rp has a bounded variance: (a) RI (x) x1| < GZ(a).
where G2 is function from R++ + to R
Girgis et al. (27 proposed unbiased ép LDP mechanisms R.p for several values of norms E [1, oo] that require b = (log (d)) bits of communication and satisfy the above conditions. In this paper, achieving communication efficiency is not our goal (though we also achieve that since the LDPLP mechanism Rp that we use takes values in a discrete set), as our main focus on analyzing the RDP of the subsampled shuffle mechanism. If we use the LDP mechanism R. from [27), we would also get similar gains in communication as were obtained in (27].
The vriveeyconvvergence trade-off of our algorithm Acup is given below.
'With slight abuse of notation, in this paper we write R(d+) to denote that R takes as its input the gradient computed on d, using the current parameter vector.
5

---

10 12
2 T E-00--10
repyytoo 21) AEEEIAAT
nonggttoo 21) PiL-Rne
sDF paurr Sound
407
sai boudd:
Approsd Fre C7
077
Appod
100
27
12
12"
27
18
100
(a) Approx. DP as a function of ' (b) Approx. DP as a function of ''' (c) Approx. DP as a function of n for 60 2. = 0.001, n = 10t for 60 7 = 0.001, n = 102 for = 2, = 10 T 10
Figure 2: Comparison of several bounds on the Approximate (e, ()DP) for composition of sequence of subsampled shuffie mechanisms for 6 = 10 (i) Approximate DP obtained from our upper bound on the RDP in Theorem [ (blue); (ii) Approximate DP obtained from our lower bound on the RDP in Theorem 2 (red); (iil) Approximate DP obtained from the upper bound the RDP given in (2) with RDP amplification by subsampling from + (black); and (iv) Applying the strong composition theorem after getting the Approximate DP of the shuffled model given in [24) with subsampling 442 (magenta).
tradeoffs). Let the set be convex with diameter D and the function f (f:-)= :C x D R be convex and L. L-Lipschitz continuous with respect to the Lg-norm, which is the dual of the Ey-norm. Let 0* = arg minsec F (0) denote the minimizer of the problem E. we run Algorithm Astap over T iterations, then we have
Theorem 3
For a'
1. Privacy: Adap is (e,8)-DP, where ó 0 is arbilrary and is given by (A)++) + log (1/5) + (A 1) log (1 1/A) log (A)
6= c
(5)
where e (A) is the RDP of the subsampled shuffle mechanism given in Theorem
Convergence: If we run Acsap with 1)t GVt where G2 max ( (d--3 1,1.2, + C.(L)
7m we get
E (Fr)) - F (0*) 0 5 (DGlog(T) ((
VT
The proof outline of Theorem is as follows: Note that Actip is an iterative algorithm, where in each iteration we use the subsampled shuffle mechanism as defined in (3), for which we have computed the RDP guarantees in Theorem I Now, for the privacy analysis of Acidp. we use the adaptive composition theorem from 37 Proposition 1] and then use the RDP to DP conversion given in Lemma For the convergence analysis, we use standard non-private SGD convergence result and compute the required parameters for that. See Appendix F for complete proof of Theorem 3
Remark 1. Note that our convergence bound is affected by the variance of the LoP mechanism Ry For example, when f is L-Lipschitz continuous w.r.t. the mn-nrmm, we can use the LDP mechanism R2 proposed in [1] that has variance (L) 14T.2 +1*+1)= and when f is T--Lipschitz continuous w.r.t. the & norm or -norm, we can use the LDP mechanisms Ro or R1, respectively, proposed
in 27 that have variances G (L) = L2d ( e +1) and (L) L =00+1) (==((=++1) respectively. By plugging these variances G2(L) (for p = 1, oo) into Theorem 3 we get the convergence rate the L-Lipschitz continuous loss function w.r.t. the fp-norm (for p 00, 2, 1).
The privacy parameter in (5) is not in a closed form expression and could be obtained by solving an optimization problem. However, we numerically compute it for several interesting regimes of parameters in our numerical experiments; see Section for more details.
Remark 2.
4 Numerical Results
In this section, present numerical experiments to show the performance of our bounds RDP of the subsampled shuffle mechanism and its usage for getting approximate DP of Algorithm for training machine learning models.
Composition of sequence of subsampled shuffle models: In Figure we plot several bounds on the approximate (c, DD for composition of T mechanisms (M Mr). where M, is

---

a subsampled shuffle mechanism for t E [T). In all our experiments reported in Figure we fix 5 10- We observe that our new bound on the RDP of the subsampled shuffle mechanism achieves significant saving in total privacy compared to the state-of-the-art, For example, we save factor of 14x compared to the bound on DP 24 with strong composition theorem [34] and 2.5x compared to the bound on the RDP given in (2 with subsampled RDP [3] in computing the overall privacy parameter e for number of iterations T
subsampling parameter ? = 0.001, LDP parameter 10 We observe in Figure 2b that the bound given in 24 with
60 2, and number of clients
the strong composition theorem [34] behaves better than the bound on the RDP [2]] with subsampled
RDP bound 43 when the number of subsampled clients per iteration is equal to h "nn 10*; however, our bound beats both of them
In Figure 2c we fix the number of subsampled clients per iteration to be k yn 10?, and hence, the subsampling parameter 7 varies with
We numerically evaluate the proposed privacy-learning performance on training machine learning models. We consider the standard MNIST handwritten digit dataset that has 60, 000 training images and 10, 000 test images. We train a simple neural network that was also used in 21 [39] and described in Table This model has d = 13, 170 parameters and achieves an accuracy of 99% for non-private, uncompressed vanilla SGD. We assume that we have n = 60, 000 clients, where each client has one sample. At each step of the Algorithm [ we choose uniformly at random 10, 000 clients, where each client clips the -nom of the gradient with clipping parameter C' 1/100 and applies the Re Lp-LDP mechanism proposed in (27] with éo = 1.5. We run Algorithm[ with 10 -5 for 200 epochs, with learning rate 1) = 0.3 for the first 70 epochs, and then decrease it 0.18 in the remaining epochs.
Distributed private learning:
|
Layer
Parameters
Test accuracy
Convolution
16 filters of 8 x 8, Stride 2 x
Max-Poolin
Convolution
32 filters of 4 x 4, Stride 2
Max-Pooling
x 2
40
Fully connected
32 units
30
Mean via RDP tupper bound)
(ones((M120)=stooo compositoo(K0V15)
Softmax
10 units
20
STD via RDP (upper bound)
10
STD via Clonss(FMTZ0) strong coMpositoo<KOV155
Table 1: Model architecture for MNIST
Figure 3:
Privacy-Utility trade-offs on the MNIST dataset with Loo -nom clipping.
Figure3]loo the mean and the standard deviation of crivacy-accuraas trade-off's averaged over 10 runs. For our privacy analysis, the total privacy budget is computed by optimizing over RDP order using our upper bound given in Theorem For privacy analysis of [24), we first compute the privacy amplification by shuffling numerically given in [24]; then we compute its privacy obtained when
amplified via subsampling [42] and finally we use the strong composition theorem [4 to obtain the central privacy parameter e.
We observe that we achieve an accuracy of 80%(+..8) with total privacy budget of c = 1.4 using our new privacy analysis, whereas, [24 achieves an accuracy of only 70.7%(+2.1) with the same privacy budget of e = 1.4 using the standard composition theorems. Furthermore, we can see that we achieves accuracy 90% (+0.5) with total privacy budget 2.91 using our new privacy analysis. whereas, [24] (together with the standard strong composition theorem) achieves the same accuracy with total privacy budget of 4.82.
5 Proof of Theorem 1 Upper Bound
For any dataset Da (di,...,dle du) E x containing of data points, define shuffle mechanism (Ds) as follows:
(Ds( H4 ..... (dx)), (R..))....R((.))
'In fact, there are several parameter regimes of great practical interest for which the results of 24 are not even valid; Appendix G for more details this, and also for more numerical comparisons.
7

---

where Ms takes k inputs and outputs a uniformly random permutation of them. Recall from (3) for any dataset D,, (d)..... da) X containing n data points, the subsampled-shune -hufffe mechanism is defined as M (D) = He samp2 (R (di),..., R.
(dn))-
The proof of Theorem consists of two steps. First, we bound the ternary-Ix| -DP of the shuffle mechanism Man (see Theorem[4). which is the main technical contribution in this proof. Then, using this, we bound the RDP of the subsampled shuffle mechanism M.
Theorem 4 (f-ternary-lx|0-DD) of the shuffle mechanism M For any integer k 2 2, co > 0, and all a 2 2, the <-ternary-xx"
of the shuffle mechanism Man is bounded by:
4 1000-11-
+ (e -
if 2,
kero
((a)"
(2()"+0-1))
a/2
al (a/2)
+ -E-0
otherwise,
ke
where & 2er6
R-1
+ and I' [=)=(())
= (z)=
x--1e is the Gamma function.
Theorem is of the core technical results of this paper, and we prove it in Section 6
was shown 43 Proposition 16] that if mechanism obeys Ç-ternary-Ph -xa |x|--DP, then its subsampled version (with subsampling parameter 7) will obey ?(-ternary- x/ - Using that result, the authors then bounded the RDP of the subsampled mechanism in [3] Eq. (9)]. Adapting that result to our setting, we have the following lemma.
Lemma 2 (From (-ternary-IxI" -DP to subsampled RDP). Suppose the shuffle mechanism Msh obeys -almaar-lxxi--P For any X 2 2, k S RDP of the subsampled shuffle mechanism M (with subsampling parameter 7 = /n) is bounded by: <(A) S - log Ea ((a)))
((a))).
Lemma 2 can be seen as a corollary to [43 Proposition and Eq. (9)]. However, for completeness,
prove Appendix E.1 E Substituting the bound on ((a:) from Theorem 4 into Lemma 2 together
with some algebraic manipulation gives proves Theorem I see Appendix E.2 for details.
Proof of Theorem 4 Ternary | -DP of the Shuffle Model
The proof has two main steps. In the first step, reduce the problem of deriving ternary divergence for arbitrary neighboring datasets to the problem of deriving the ternary divergence for specific neighboring datasets, D D' D where all elements in DD are the same and D' DD' differ from DD in one entry. In the second step, we derive the ternary divergence for the special neighboring datasets.
The specific neighboring datasets to which we reduce general problem has the following form: D = {(Dm: D', m. D'..) ) Dm (d,...,d, d, e) E X", D'n = (d,..., d, )') E Xm", and D" = (d,..., d') E Xm,, where d, d', d" E EX,,
(8)
Consider arbitrary neighboring datasets D = (d1. d dz), D' (di,..., d d') and D" (di,..., dx-1, d each having is elements. For any m E 1o,...,,-11]] we define new neigh- boring datasets (k) m+ (d"...., d% dx), m++1 (dh d% dg),), and D"(R)) (d% ..... d
each having m + elements. Observe that (D)(A) ((A) Dik) (D++1: m+1 m+t) E Dm
same.
The first step of the proof is given in the following theorem.
Theorem 5 (Reduction to the Special Case). Let q
a. We have:
MMn (D) Men (D)) Msn (h)
(R)( (K) (1)) (M ()++)) Man Man(D (D)(()
S Emm-Bin(k-1..0
A.MMa m411)
We know (by Chernoff bound) that the binomial r.v. is concentrated around its mean, which implies that the terms in the RHS of 2 that correspond to m < (1 - T)q(k 1) (we will take T 1/2) will contribute in negligible amount. Then we show that Em
8

---

ManlDin ((A)))))a)) Ma (D (0) m+1 XA)
(l-MMatt"ME)) m-11)
is non-increasing function of m. These obser-
Ma ((A)
vation together imply that the RHS in (9) is approximately equal ((1-))u(E-1)-
Since Em is precisely what is required to bound the ternary DP for the specific neighboring datasets, we have reduced the problem of computing the ternary DP for arbitrary neighboring datasets to the problem of computing ternary DP for specific neighboring datasets. The second step of the proof bounds (n)-r)g(n-1), which follows from the result below that holds for any E N.
Theorem 6 ([x|= for special case). For any m E N, integer a 2 2, and (D", D Pm) E DDu
same
4 -1"
(an(Di)))) - (D mn
if =
me00
(P..)
Mah (1m)
aT aT(a/2) (
(2 112
0/2
otherwise.
me²
Missing details of how Theorem follows from Theorems 5 can be found in Appendix C.4
Proof sketch of Theorem Let p., E [k], Pi: PK denote the distributions of R when the input data point is d,, dz. di respectively. The main idea of the proof is the observation that each p; can be written as mixture distribution P; P + (1 e P.. where P, is defined in terms of Pa, Pk-- So, instead of client i E [k: mapping its data point d, according to P:s we can view it as the client i maps d, according to PKK with probability (w.p.) 1/e"0 and according to P; w.p. (1 - 1/ero). As result, the number of clients that sample from the distribution p/ follows a binomial distribution Bin(k: - 1, ).- This allows to write the distribution of M,s. when clients map their data points according to ........ Pk- Pk- P/ as a convex combination of the distribution of M when clients map their data points according to PI..... Pk-1, . Pk- P'. :K:: see Lemma 4 Then using a joint convexity argument (see Lemma 3). we write the ternary divergence between the original triple of distributions of Mah in terms of the same convex combination of the ternary divergence between the resulting triples of distributions of Mah as in Lemma 4 Using a monotonicity argument (see Lemma 50, we can remove the effect of clients that do not sample from the distribution pk without decreasing the ternary divergence. By this chain of arguments, we have reduced the problem to the one involving the computation of ternary divergence only for the special form of neighboring datasets (as in Theorem 6 See Appendix C. for a complete proof.
which proves Theorem
5.
Proof sketch of Theorem 6 Consider (D%, D'm Dm) E D as in the statement of Theorem First we observe that for any a 2 1 and any three distributions q, r over the same domain, we can write E,, of the standard inequality |x + y/ < 20x + lyy which holds for all x, y E R and a 2 1. Now, by taking p Ma (D' (D'm), q Man.D"",, and r MDa((mm) we reduce the problem of computing the ternary |x] divvergeee (which we need to bound) to the problem of computing the Pearson-Vajda divergence [43, which can write in terms of the a-th absolute moment of the r.v.
| < 20-1 (E, [| - [0] + E, 1| 11))). This is a straight- forward application
(M.((")(h)) - -1) for all h E Aø (where D' E (D'm. D",, }) X : :A + R. defined as X(h)= = (Mx(D ((h)
and distributed according to (h) Mea (D))))) (h). In [29]. the authors have bounded the absolute moments of the r.v. X(h) by showing that X()) is sub-Gaussian r.v. and using standard concentration
results. See Appendix C.3 for complete proof.
7 Discussion
In this paper, we analyzed the Rényi differential privacy of the subsampled shuffle model by bounding the ternary -DP of the shuffle model. We numerically demonstrated the importance of our proposed bound, where we obtain a significant improvement over using the state-of-the-art in practical regimes. Furthermore, we used our privacy analysis to study the privacy-accuracy trade-offs on the MNIST dataset, where we obtained 90% accuracy with total privacy budget of = 2.91, which is an improvement over an analysis yielding 4.82, using standard strong composition theorem.
Closing the gap (shown numerically) between our lower bound in Theorem 2 and the achievable upper bound in Theorem is an important unresolved question. Another direction to explore would be analyze the RDP of the subsampled shuffle model for different sub-sampling techniques such as Poisson subsampling
45). random check-in [9] client self-sampling (30].

---

Societal Impact. Collaborative learning comes with significant societal risks of privacy violations, which is the main topic addressed in this paper. However, such learning is only as good as the data used for training, and if the data is not unbiased, this could lead to significant issues related to fairness and could also lead to societally undesirable outcomes. Such an issue is exacerbated when privacy is guaranteed on the data used for training, making a-priori fairness checks on data infeasible. This can be ameliorated by properly testing models finally obtained against fairness criteria and rejecting models that fail the test. This paper did not consider the issue of robustness to security, and this could also be an important societal issue in collaborative learning, where small subset users could insert malicious imputs disrupt the learning process worse bias the learned model covertly. This could also lead to negative outcomes. This issue of robustness to malicious participants has been studied in several papers, and incorporating this into the framework of the paper is an important future research topic.
Acknowledgment
This work supported in part by NSF grants #2007714 and #1955632 and Google Faculty research award and an Amazon Research Award.
References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-30 108-318,20 2016.
[2] N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan. epsgd: Communication- efficient and differrentallly-rrivaee distributed sgd. In Advances in Neural Information Processing Systems, pages 7564-7575, 2018.
[3] S. Asoodch, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar. Three variants of differential privacy: Lossless conversion and applications. IEEE Journal on Selected Areas in Information T'heory, 2(1):208-22) 222, 2021.
[4] B. Balle, G. Barthe. M. Gaboardi, J. Hsu, and T. Sato. Hypothesis testing interpretations and renyi differential privacy. In S. Chiappa and R. Calandra, editors, International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 2496-2506. PMLR, 2020.
[5] B. Balle, Bell, A. Gascon, and K. Nissim. Differentially private summation with multi- message shuffling. arXiv preprint arXiv:1906.091 16, 2019.
[6] B. Balle, J. Bell, A. Gascón, and K. Nissim. Improved summation from shuffling, arXiv preprint arXiv: 1909. 1225, 2019.
[7] B. Balle, J. Bell, A. Gascón, and K. Nissim. The privacy blanket of the shuffle model. In Annual International Cryptology Conference, pages 638-667. Springer, 2019.
[8] B. Balle, J. Bell, A. Gascón, and K. Nissim. Private summation in the multi mesti--mesage shuffle model. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 657-676, 2020.
[9] B. Balle, P. Kairouz, B. McMahan, O. D. Thakkar, and A. Thakurta. Privacy amplification via random check-ins. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[10] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473. IEEE, 2014.
[11] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers. Protection against recon- struction and its applications in private federated learning. arXiv preprint 1 1.00009 2018.
10

---

[12] L. Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pages 177-186. Springer, 2010.
[13] C. L. Canonne, G. Kamath, and T. Steinke. The discrete gaussian for differential privacy. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[14) K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 12(3), 2011.
[15] A. Cheu, A. D. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In Advances in Cryptology EUROCRYPT 2019, volume 11476, pages 375-403. Springer, 2019.
[16] B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately, In Proceedings of the 31tt International Conference Neural Information Processing Systems, NIPS' 17, page 3574-3583, Red Hook, NY, USA, 2017. Curran Associates Inc.
[17] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429-438. IEEE, 2013.
[18] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), pages 265-284, 2006.
[19] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-40) 2014.
[20] C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In 2010 IEEE 5 Annual Symposium Foundations of Computer Science, pages 51-60. IEEE, 2010.
[21] Ú. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, S. Song, K. Talwar, and A. Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. CORR, abs/2001.0361 2020.
[22] Ó. Frlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta. Amplifi- cation by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithmss, pages 2019.
SIAM,
[23] U. Erlingsson, V. Pihur, and A. Korolova. Rappor: Randomized aggregatable privacy-preserving preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
[24] V. Feldman, A. McMillan, and K. Talwar. Hiding among the clones: simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science. IEEE, 2021.
[25] B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker. On the power of multiple anonymous messages. IACR Cryptol. ePrint Arch., 2019;1382, 2019.
[26] B. Ghazi, R. Pagh, and A. Velingker. Scalable and differentially private distributed aggregation in the shuffled model. arXiv preprint arXiv: 08320, 2019.
[27] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. Theertha Suresh. Shuffled model of differential privacy in federated learning. In A. Banerjee and K. Fukumizu, editors, Proceedings The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages
PMLR, 13-15 Apr 2021.
[28] A. M. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh. Shuffled model of federated learning: Privacy, accuracy and communication trade-offs. IEEE Journal on Selected Areas in Information Theory, 2(1 2(1):464 4788,444788 2021.

---

[29] A. M. Girgis, D. Data, S. Diggavi. A. T. Suresh, and P. Kairouz. On the renyi differential privacy of the shuffle model. In Proceedings of the 2021 ACM SIGSAC conference on computer and communications security. ACM, 2021.
[30] A. M. Girgis, D. Data, and S. N. Diggavi. Differentially private federated learning with shuffling and client self-sampling. In IEEE International Symposium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021, pages 338- 338-333. IEEE, 2021.
[31] A. Greenberg. Apple's 'differential privacy' is about collecting your data but not your data. Wired, June, 13, 2016.
[32] P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy, In International Conference on Machine Learning, ICML, pages 2436-2444, 2016.
[33] Kairouz, H. B. McMahan, Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz,
Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv: 191::9922.00 1912.49977 2019.
[34] Kairouz, S. Oh, and Viswanath. The composition theorem for differential privacy. In International conference machine learning, pages 1376-1385. PMLR, 2015,
[35] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
[36] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtarik, A. T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop on Private Multi-Party Machine Learning, 2016.
[37] I. Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[38] I. Mironov, K. Talwar, and L. Zhang. R\ 'enyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv:1908 10530, 2019.
[39] N. Papernot, A. Thakurta, S. Song. S. Chien, and U. Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. arXiv preprint arXiv:2007.14191, 2020.
[40] S. Shalev-Shwartz et al. Online learning and online convex optimization. Trends& in Machine Learning, 4(2):107-194, 2012.
Foundations and
[41] O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pages 71-79, 2013.
[42] J. Ullman. Cs7880. rigorous approaches to data privacy. 2017.
[43] Y.-.. Wang, B. Balle, and S. P. Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant, In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR, 2019.
[44] Q Yang, Y. Liu, T. Chen, and Y. Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
[45] Y. Zhu and Y.-.. Wang. Poission subsampled rényi differential privacy, In International Conference on Machine Learning, pages 7634-7642. PMLR, 2019.
12


Reviews:
[{"review_id": "iskNljxQb7k", "reviewer": "Reviewer_jtYS", "summary": "This paper studies the problem of bounding the privacy loss of the sub-sampled shuffle model, motivated by the real-world application of federated learning with differential privacy.\n\nThe broad type of mechanism studied in this paper is as follows:\\\nSetup:\n- Consider dataset $(d_1, \\ldots, d_n)$ where client #$i$ has the datapoint $d_i \\in \\mathcal{X}$.\n- Consider any $\\epsilon_0$-locally differentially private mechanism $\\mathcal{R} : \\mathcal{X} \\to [B]$.\n\n(One round of) the mechanism is as follows:\n- $k$ out of $n$ clients are chosen. Each chosen client $i$ send $\\mathcal{R}(d_i)$ to the _shuffler_.\n- The shuffler randomly permutes the received responses from the $k$ chosen clients and sends it to a central server, which can post-process the same in an arbitrary manner.\n\nThe goal is to know, for any given $\\delta$, what is the smallest $\\epsilon$ for which the above mechanism is $(\\epsilon, \\delta)$-differentially private (DP) : this $\\epsilon$ can depend on $\\epsilon_0$, $k$, $n$ and $\\delta$.\n\nOne approach for analyzing the privacy loss is to compose (in some way) the privacy loss guarantees of each of the two steps : sub-sampling and shuffling. One such way is to compose the Renyi differential privacy guarantees of the two steps (since Renyi-DP usually gives better bounds than the standard \"advanced composition\"). This paper instead takes a direct approach to bounding the Renyi-DP loss, and also demonstrates empirically that doing so, does better than performing any kind of composition of the two steps.\n\nThe paper uses the recently introduced technique of _ternary-$|\\chi|^{\\alpha}$-differential-privacy_ to prove the theorems.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem studied in this paper is practically very relevant and timely, as federated algorithms are being deployed in practice at a massive scale and privacy is a mounting concern. The shuffle model is emerging as an important middle ground between the central and local models of differential privacy.\\\nIt is important to have as tight a guarantee on the privacy parameters as possible, so as to have good utility while preserving privacy. Even constant factor improvements in estimating the privacy loss can be practically relevant.\n\nThe main contribution in the paper is the direct analysis of the privacy loss in the subsampled shuffle model. The main technique used is the ternary $|\\chi|^{\\alpha}$-DP that was introduced in a recent work of [Wang et al. 2019].\n\nThis direct analysis is empirically shown to yield better bounds than composing the privacy guarantees that have been obtained previously for sub-sampling and for shuffling separately (different kinds of compositions are considered, and the bound proved in this paper is significantly better than these). Moreover, the paper also proves a lower bound on the Renyi-DP loss of the sub-sampled shuffled mechanism : this is also useful to know in practice.\n\n#### Significance and originality:\n\nWhile the direct analysis in the paper is technically challenging and involved, I feel it is somewhat incremental over the prior work of [Wang et al. 2019].\\\nHowever, the improved bounds could be highly impactful in practice.\n\n#### Quality of the paper:\n\nThe paper is well-written overall, and contributions are clearly stated.\\\nWhile I did not carefully verify all the proof details, they make sense at a high level.\n\n#### Minor Typo:\n\n- Page 3 (Defn 1). Since this definition is for a fixed $\\lambda$, I think $(\\lambda, \\epsilon(\\lambda))$ should be simply $(\\lambda, \\epsilon)$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper raises good points about the potential negative societal impacts of this work: namely that private learning is inherently at odds with checkability of fairness criteria (since the data is private, it can be hard to directly check whether the data was biased or not). It also points out that a small subset of adversarial users could contribute malicious data to the learning algorithm, thereby leading to unfavorably learnt models.\n\nThese issues are not specific to the results in this paper, but are broadly applicable to learning with differential privacy.\n", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns regarding this paper.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "IgEf1YE1iYb", "reviewer": "Reviewer_HpvA", "summary": "The focus of the paper is on Rényi differential privacy (RDP) in the shuffle model of DP. The main result in the paper is to introduce (at least somewhat loose) upper and lower RDP bounds for an arbitrary subsampled discrete mechanisms in the shuffle model. I think this is a novel, if fairly limited contribution.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-- after rebuttals & discussion:\nI still think this is a borderline paper and I therefore keep my score unchanged. I agree with the authors that the proofs have some novelty, but the paper also has some clear weaknesses (mainly the close relationship with the existing arXiv paper, looseness of the bounds, and the gap between the upper and the lower bound).\n--\n\nThe authors consider privacy accounting of arbitrary discrete mechanisms with subsampling in the shuffle model of DP, a recently introduced distributed setting assuming a trusted shuffler besides the dataholders and the analyst or central server. As the main results of the paper, the authors introduce an upper and a lower bound for RDP. The bounds are not tight, and there is a significant gap between the bounds. However, the upper bound does improve on the existing methods.\n\nThe main reservations I have about this paper is that it seems almost as a small slice cut off from the more extensive paper on archive (and cited in the current paper, Girgis et al. 2021: On the renyi differential privacy of the shuffle model), and the contribution in this paper alone seems limited. Without properly checking the proofs, it also seems like they are mostly simple modifications on the existing proofs of the arXiv paper, combined with some techniques from an earlier subsampled RDP paper (Wang et al. Subsampled Rényi Differential Privacy and Analytical Moments Accountant).\n\nAll in all, the paper does make some clear improvement on the current methods, but it seems to be fairly limited in scope.\n\nQuestions/comments for the authors:\n1) Since most of the proofs follow closely (sometimes almost verbatim) the proofs of the arXiv paper, I think this needs to be stated clearly also in the main paper for each Thm (currently this is mentioned in the Supplement).\n\nMinor comments\n* Add bibliography to the Supplement as the citation numbers differ from the main text.\n* You could add a paragraph on alternative approaches to privacy accounting (maybe in the extended related work?) to dispel the idea that RDP is the only possible approach (compare e.g. privacy loss distributions or Gaussian DP). However, since these haven't been used in the shuffle model (as far as I know), I do not think this needs to be too extensive.\n* Fix the spelling of Rényi, pretty please.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limiting assumptions are stated clearly-enough. I do not think this paper needs to specifically discuss societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "8EtcVNBBLeF", "reviewer": "Reviewer_65kL", "summary": "This paper follows the line of research aiming at tightening the privacy analysis of existing differentially private learning schemes. The authors consider the distributed learning framework, where a group of clients collaborate within a parameter-server architecture to learn a joint ML model under privacy (against the server). In this context, the paper analyzes the differential privacy guarantees obtained by  combining (i) subsampling of the clients (ii) local randomization at the client level and (iii) shuffling clients’ responses before sending them to the server. The authors provide new (upper and lower) bounds on the privacy guarantee of the above scheme for discrete local randomizers.  To do so, they rely on some well-known result from differential privacy (especially Renyi differential privacy), but also devise some interesting new proof schemes. The numerical comparison with existing works show that in some parameter regimes, the proposed bound considerably improves existing bounds studying the same framework.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Relevance: The problem of tightening the privacy analysis of the distributed learning paradigm is an active and important line of research that is perfectly suited to a major ML conference like NeurIPS.\n\nClarity: The paper is overall clear and well written. I like that the authors provided sketch of proof and discussions on their results while presenting them (i.e., in the main body of the paper). \n\nQuality: I did not have the time to go over all details of the proofs (hence my low confidence), but from my level of reading, both the technical and empirical contents look sound.  I just list below a couple of questions to the authors. \n- The problem formulation (line 139) considers only one data point per user, which is quite restrictive. The authors briefly explained in the limitations paragraph (line 90) that it might not be trivial to generalize their results to arbitrary numbers of data points per user, and claim that their results are close ‘in spirit’ to uniform sampling. However it is unclear to me if the present results are simple to generalize even in the uniform sampling case. Could the authors clarify this point for me? \n- Numerical results presented in Figure 2 and 3 presents some considerable improvements in the privacy/accuracy trade-off compared to previous works in certain parameter regimes. However in some other cases (e.g., in the extreme privacy/ low accuracy regime on the left of Figure 3), the comparison seems at the disadvantage of the new technique. Do the authors have some (theoretical or empirical) insight on what parameter regimes are the best suited to their analysis? \n\nOriginality: I think that the paper is not very original, but its theoretical contribution seems sufficiently significant to me. I think the authors provided an analysis of the subsampled + shuffle framework by making a good use of previously known results and by devising new proof schemes when needed. In particular, I believe that the reduction in Section 6 could be of independent interest in future works.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the authors adequately addressed both the limitations and social impact of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 to 7"}, "extra_text": {}}, {"review_id": "4Mf1sTvvp3e", "reviewer": "Reviewer_cNC6", "summary": "The paper studies discrete randomization mechanism in the subsampled Renyi DP model. They give a bound on the RDP of the subsampled shuffle mechanism and also give a lower bound. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The biggest positive of the paper is the upper bound on subsampled renyi DP. The bound is concrete and can be implemented in practice to account for the privacy loss in the real world when we use shuffle DP. I verified the proof and it is correct to the best of my understanding. \n\nI will next point out the cons against the paper. \n1. The paper studies pure LDP mechanism whose range is a discrete set while one of the applications of the paper is SGD. The loss function in the SGD has the range over the real. This is a discrepancy which I do not understand. For example, for p=2, the mechanism of DJW samples a uniform point in the \\ell_2 ball in the direction of the gradient with probability e^eps/(1+e^eps). This would always yield a point whose coordinates are real. \n2. The proof technique in the paper is almost identical to that by Girgis et al. \"On the Renyi Differential Privacy of the Shuffle Model.\" The only difference is that the reduction to the special case where they have to consider three databases of special form. This has to do with the proof technique introduced in Balle et al. analytic moment paper for subsampled RDP (BKW19). Even the observation that the randomization in the shuffle model can be seen as a weighted convolution of two probability distributions was made in FMT20. I fail to see what it new in this paper. I would appreciate if the authors can point exactly what is new in the paper or whether it is just the adaption of Girgis et al. to BKW19 and FMT20. \n3. Since the expectation is not always on a single distribution, I would suggest the authors to make it explicit. For example, when they prove the joint convexity of ternary divergence, what is the expectation over in each of the term? Is it over R_a, R_0 and R_1, respectively? Then I believe you need to use Jensen, the joint convexity of bivariate function, and Fubini. \n\nFinally comparing the result with the Girgis et al.'s main result, setting gamma=1 in Theorem 1 does not yield Theorem 1 in Girgis et al. As a result, there is a big discontinuity near 1 when we map RDP guarantee with subsampling rate. \n\nUnless these concerns are not addressed explicitly, I am afraid the paper is a clear reject for me. I am currently keeping the score high enough in an optimistic hope that the authors address it clearly and concisely giving me reasons to increase my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a consensus that the paper provides an interesting theoretical contribution to an important and timely problem, the shuffle model being an actively studied model of privacy that is also increasingly studied in federated learning (FL).

The authors' result on analyzing the privacy loss in the subsampled shuffle model and the accompanying empirical evaluation are valuable contributions towards tightening the privacy/utility trade-offs of DP-SGD in a natural FL setting.

However, there is also a consensus that the paper has a somewhat limited technical novelty, with proofs very similar to ones in recent work. Also, some concerns are raised regarding the remaining gap between the obtained lower and upper bounds.

That said, the reviewers are in agreement in leaning towards acceptance.
Decision: Accept (Poster)