Rényi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning
Year: 2021

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 privacyoptimization 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-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.

heading: 1 Introduction
text: As learning moves towards the edge, there is a need to collaborate to build learning models1, 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 (2) in Section 2). To obtain a model parametrized by ✓ using ERM, the commonly used mechanism is Stochastic Gradient Descent (SGD) [12]. However, one needs to solve this while enabling strong privacy guarantees on local data from the server, while also obtaining good learning performance, i.e., a suitable privacy-learning performance operating point.
Differential privacy (DP) [18] is the gold standard notion of data privacy that gives a rigorous framework through quantifying the information leakage about individual training data points from the observed interactions. Though DP was originally proposed in a framework where data resides centrally [18], for distributed learning the more appropriate notion is 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
1This 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 (NeurIPS 2021).
from poor performance in comparison with the central DP mechanisms [17, 35, 32]. To overcome this, a new privacy framework using anonymization has been proposed in the so-called shuffled model [22, 25, 6, 26, 5, 15, 7, 8]. In the shuffled model, each client sends her private message to a 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.
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 a good model; setting up the tension between privacy and performance. The goal is to obtain as many such interactions as possible for a given privacy budget. This is quantified through analyzing the privacy of the composition of privacy mechanisms. Abadi et al. [1] developed a 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 random client participation and stochastic gradient descent (SGD), which can be written as
✓t+1 ✓t ⌘t 1 |I| X
i2I R(rfi(✓t)),
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, in several cases, is shown to yield a privacy advantage proportional to the subsampling rate; see [35, 42]. 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 1). Our contributions are:
• We analyze the RDP of subsampled mechanisms in the shuffle framework by developing a novel bound applicable to any discrete ✏0-LDP mechanism as a function of the RDP order , subsampling rate , the LDP parameter ✏0, and the number of clients n; see Theorem 1. The bound is explicit and amenable to numerics, including all constants.2 Furthermore, the bounds are valid for generic LDP mechanisms and all parameter regimes.3 We also provide a lower bound for the RDP in Theorem 2. We prove our upper bound (Theorem 1) 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 | |↵-DP [43] of shuffle (non sub-sampled) mechanisms; see Lemma 2. Then we reduce the computation of the ternary | |↵-DP 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 | |↵-DP 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 6).
• Using the core technical result in Theorem 1, we analyze privacy-convergence trade-offs of the CLDP-SGD algorithm (see Algorithm 1) 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 a factor 14⇥ in privacy (✏) over the best known results for approximate DP for shuffling [24] combined with strong composition [34] for T = 105, = 0.001, n = 106, and a factor of 2.5⇥ better than the best known RDP for shuffling bound [29] combined with the sub-sampling result in [43]. Translating these to privacy-performance operating point in distributed
2As emphasized in [43], “in differential privacy, constants matter”. 3Some of the best known approximate DP bounds for the shuffle model [7, 24] are restricted to certain
parameter regimes in terms of n, , ✏0, etc.
optimization, over the MNIST data set with `1 clipping we numerically show gains: For the same privacy budget of ✏ = 1.4, we get a test performance of 80% whereas using strong composition the test performance of [24] is 70%; furthermore, we achieves 90% accuracy with the total privacy budget ✏ = 2.91, whereas, [24] (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.
Related work: We give a more complete literature review in Appendix A, and focus here on the works that are closest to the results presented in this paper.
Private optimization in the shuffled model: Recently, [21] 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 a 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 to be loose for composition [1]. To the best of our knowledge, analyzing the private optimization framework using RDP and subsampling in the shuffled model is new to this paper.
Subsampled RDP: The works [38, 43, 45] have studied the RDP of subsampled mechanisms without shuffling. They demonstrated that this provides a 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 shuffled privacy framework has not been studied before,4 and is new to 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 is non-trivial. We overcome this by reducing our problem of computing RDP to bounding the ternary | |↵-DP, and bounding the latter is a core technical contribution of our paper. Paper organization: We give preliminaries and problem formulation in Section 2, main results (upper and lower bounds, and privacy-convergence tradeoff) in Section 3, numerical results in Section 4, proof of the upper bound in Section 5, and proof of the ternary DP of the shuffle model in Section 6. Omitted details/proofs from this paper are given in the supplementary material.

heading: 2 Preliminaries and Problem Formulation
text: We use several privacy definitions throughout this paper. Among these, the local and central differential privacy definitions are standard and we defer them to Appendix B. The other privacy definitions (Rényi DP and ternary | |↵-DP) are relatively less standard and we define them below. We say that two datasets D = {d1, . . . , dn} 2 Xn and D0 = {d01, . . . , d0n} 2 Xn are neighboring (and denoted by D ⇠ D0) if they differ in one data point, i.e., there exists an i 2 [n] such that di 6= d0i and for every j 2 [n], j 6= i, we have dj = d0j .
Definition 1 (( , ✏)-RDP (Rényi Differential Privacy) [37]). A randomized mechanism M : Xn ! Y is said to have ✏-Rényi differential privacy of order 2 (1,1) (in short, ( , ✏( ))-RDP), if for any neighboring datasets D, D0 2 Xn, the Rényi divergence of order between M(D) and M(D0) is upper-bounded by ✏( ), i.e.,
D (M(D)||M(D0)) = 1
1 log E✓⇠M(D0) "✓ M(D)(✓) M(D0)(✓) ◆ #!  ✏( ), (1)
where M(D)(✓) denotes the probability that M on input D generates the output ✓. Definition 2 (⇣-Ternary | |↵-differential privacy [43]). A randomized mechanism M : Xn ! Y is said to have ⇣-ternary-| |↵-DP, if for any triple of mutually adjacent datasets D,D0,D00 2 Xn (i.e., they mutually differ in the same location), the ternary-| |↵ divergence of M(D),M(D0),M(D0) is upper-bounded by (⇣(↵))↵ for all ↵ 1 (where ⇣ is a function from R+ to R+), i.e.,
D| |↵ (M(D),M(D0)||M(D00)) := EM(D00)  M(D) M(D0)
M(D00)
↵  (⇣(↵))↵ .
4One naive approach is to plug in the RDP analysis of shuffle model [29] into the results of [43]; however, our direct analysis of subsampled mechanisms yields better results in several interesting regimes; see Section 4.
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 | |↵-DP of the shuffled mechanism to bound the RDP of the sub-sampled shuffle model.
We can use the following result for converting the RDP guarantees of a 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]). Suppose for any > 1, a mechanism M is ( , ✏ ( ))-RDP. Then, the mechanism M is (✏, )-DP, where > 0 is arbitrary and ✏ is given by
✏ = min ✓ ✏ ( ) +
log (1/ ) + ( 1) log (1 1/ ) log ( ) 1
◆ .
Problem formulation: We consider a distributed private learning setup comprising a set of n clients, where the ith client has a data point di drawn from a universe X for i 2 [n]; see also Figure 1. 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
min ✓2C
⇣ F (✓,D) := 1
n
nX
i=1
f(✓, di) ⌘ , (2)
where C ⇢ Rd is a closed convex set, and f : C ⇥ D ! R is the loss function. Our goal is to construct a global learning model ✓ via stochastic gradient descent (SGD) while preserving privacy of individual data points in the training dataset D by providing strong DP guarantees.
Algorithm 1 Acldp: CLDP-SGD Input: Datasets D = (d1, . . . , dn), LDP privacy parameter ✏0, gradient norm bound C, and learning rate schedule {⌘t}.
1: Initialize: ✓0 2 C 2: for t 2 [T ] do 3: Client sampling: A random set Ut of k clients is chosen. 4: for clients i 2 Ut do 5: Compute gradient: gt (di) r✓tf (✓t, di) 6: Clip gradient: g̃t (di) gt (di) /max n 1, kgt(di)kpC o 7: Client i sends Rp (g̃t (di)) to the shuffler. 8: end for 9: Shuffling: The shuffler sends random permutation of
{Rp (g̃t (di)) : i 2 Ut} to the server. 10: Aggregate: gt 1k P i2Ut Rp (g̃t (di))
11: Descent Step: ✓t+1 Q C (✓t ⌘tgt), where Q
C is the projection operator onto the set C.
12: end for Output: The model ✓T and the privacy parameters ✏, . We revisit the CLDP-SGD algorithm presented in [27] and described in Algorithm 1 to solve the ERM (2). In each step of CLDP-SGD, we choose uniformly at random a set Ut of k  n clients out of n clients. Each client i 2 Ut computes and clips the `p-norm of the gradient r✓tf (✓t, di) to apply the LDP mechanism Rp, where Rp : Bdp ! {0, 1}b is an ✏0-LDP mechanism when inputs come from an `p-norm ball. In [27], the authors proposed different ✏0-LDP mechanisms for general `p-norm balls. After that, the shuffler randomly permutes the received k gradients {Rp (g̃t (di))}i2Ut 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 a stronger privacy analysis of the CLDP-SGD algorithm by characterizing the RDP of the sub-sampled shuffle model.

heading: 3 Main Results
text: 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 1 and a lower bound in Theorem 2. We then present the privacy-convergence trade-offs of the CLDP-SGD Algorithm in Theorem 3.
Consider an arbitrary ✏0-LDP mechanism R, whose range is a discrete set [B] = {1, . . . , B} for some B 2 N := {1, 2, 3, . . .}. Here, [B] could be the whole of N. Let M(D) be a subsampled shuffle mechanism defined as follows: First subsample k  n clients of the n clients (without replacement), where = kn denotes the sampling parameter. Each client i out of the k selected
clients applies R on di and sends R(di) to the shuffler,5 who randomly permutes the received k inputs and outputs the result. To formalize this, let Hk : Yk ! Yk denote the shuffling operation that takes k inputs and outputs their uniformly random permutation. Let sampnk : Xn ! X k denote the sampling operation for choosing a random subset of k elements from a set of n elements. We define the subsampled-shuffle mechanism as
M (D) := Hk sampnk (R (d1) , . . . ,R (dn)) . (3) Observe that each iteration of Algorithm 1 can be represented as an output of the subsampled shuffle mechanism M. Thus, to analyze the privacy of Algorithm 1, it is 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 Hk is a random permutation of the k outputs of R (subsampling is not important here), the server cannot associate the k 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 AkB as
AkB = ⇢ h = (h1, . . . , hB) : BX
j=1
hj = k , (4)
to 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.l.o.g.), that the output of M is a distribution over AkB . 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 1 and proved in Section 5) and the second result provides a lower bound (stated in Theorem 2 and proved in Appendix D). Theorem 1 (Upper Bound). For any n 2 N, k  n, ✏0 0, and any integer 2, the RDP of the subsampled shuffle mechanism M (defined in (3)) is upper-bounded by
✏( )  1 1 log
0 @1 + 4 ✓
2
◆ 2 (e✏0 1)2
ke✏0 +
X
j=3
✓
j
◆ jj (j/2) 2 e2✏0 1 2
ke2✏0
!j/2 +⌥
1
A ,
where k = b k 12e✏0 c+ 1, = k n , and (z) = R1 0 x z 1e xdx is the Gamma function. The term ⌥ is
given by ⌥ = ✓⇣ 1 + e
2✏0 1 e✏0
⌘ 1 e
2✏0 1 e✏0
◆ e k 1 8e✏0 .
Theorem 2 (Lower Bound). For any n 2 N, k  n, ✏0 0, and any integer 2, the RDP of the subsampled shuffle mechanism M (defined in (3)) is lower-bounded by
✏ ( ) 1 1 log
0 @1 + ✓
2
◆ 2 (e✏0 1)2
ke✏0 +
X
j=3
✓
j
◆ j
e2✏0 1
ke✏0
!j E ✓ m k
e✏0 + 1
◆j 1
A ,
where expectation is taken w.r.t. the binomial r.v. m ⇠ Bin (k, p) with parameter p = 1e✏0+1 .
Our CLDP-SGD algorithm and its privacy-convergence trade-offs (stated in Theorem 3 below) are given for a general local randomizer Rp (whose inputs comes from an `p-ball for any p 2 [1,1]) that satisfies the following conditions: (i) The randomized mechanism Rp is an ✏0-LDP mechanism. (ii) The randomized mechanism Rp is unbiased, i.e., E [Rp (x) |x] = x for all x 2 Bp(a), where a is the radius of the ball Bp. (iii) The output of the randomized mechanism Rp can be represented using B 2 N+ bits. (iv) The randomized Rp has a bounded variance: supx2Bp(a) EkRp (x) xk 2 2  G2p(a), where G2p is a function from R+ to R+.
Girgis et al. [27] proposed unbiased ✏0-LDP mechanisms Rp for several values of norms p 2 [1,1] that require b = O (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 ✏0-LDP mechanism Rp that we use takes values in a discrete set), as our main focus is on analyzing the RDP of the subsampled shuffle mechanism. If we use the ✏0-LDP mechanism Rp from [27], we would also get similar gains in communication as were obtained in [27].
The privacy-convergence trade-off of our algorithm Acldp is given below. 5With a slight abuse of notation, in this paper we write R(di) to denote that R takes as its input the gradient computed on di using the current parameter vector.
RDP in Theorem 1 (blue); (ii) Approximate DP obtained from our lower bound on the RDP in Theorem 2 (red); (iii) Approximate DP obtained from the upper bound on the RDP given in [29] with RDP amplification by subsampling from [43] (black); and (iv) Applying the strong composition theorem [34] after getting the Approximate DP of the shuffled model given in [24] with subsampling [42] (magenta).
Theorem 3 (Privacy-Convergence tradeoffs). Let the set C be convex with diameter D and the function f (✓; .) : C ⇥ D ! R be convex and L-Lipschitz continuous with respect to the `g-norm, which is the dual of the `p-norm. Let ✓⇤ = argmin✓2C F (✓) denote the minimizer of the problem (2). For = kn , if we run Algorithm Acldp over T iterations, then we have 1. Privacy: Acldp is (✏, )-DP, where > 0 is arbitrary and ✏ is given by
✏ = min ✓ T ✏ ( ) +
log (1/ ) + ( 1) log (1 1/ ) log ( ) 1
◆ , (5)
where ✏ ( ) is the RDP of the subsampled shuffle mechanism given in Theorem 1.
2. Convergence: If we run Acldp with ⌘t = DGpt , where G 2 = max{d1 2 p , 1}L2 + G
2 p(L)
n , we get
E [F (✓T )] F (✓⇤)  O ✓ DG log(T )p
T
◆ .
The proof outline of Theorem 3 is as follows: Note that Acldp 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 1. Now, for the privacy analysis of Acldp, we use the adaptive composition theorem from [37, Proposition 1] and then use the RDP to DP conversion given in Lemma 1. For the convergence analysis, we use a standard non-private SGD convergence result and compute the required parameters for that. See Appendix F for a complete proof of Theorem 3. Remark 1. Note that our convergence bound is affected by the variance of the ✏0-LDP mechanism Rp. For example, when f is L-Lipschitz continuous w.r.t. the `2-norm, we can use the LDP mechanism R2 proposed in [11] that has variance G22(L) = 14L2d e✏0+1 e✏0 1
2; and when f is L-Lipschitz continuous w.r.t. the `1-norm or `1-norm, we can use the LDP mechanisms R1 or R1, respectively, proposed in [27] that have variances G21(L) = L2d2 e✏0+1 e✏0 1 2 and G21(L) = L2d e✏0+1 e✏0 1
2, respectively. By plugging these variances G2p(L) (for p = 1, 2,1) into Theorem 3, we get the convergence rate of the L-Lipschitz continuous loss function w.r.t. the `p-norm (for p =1, 2, 1). Remark 2. 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 4 for more details.

heading: 4 Numerical Results
text: In this section, we present numerical experiments to show the performance of our bounds on RDP of the subsampled shuffle mechanism and its usage for getting approximate DP of Algorithm 1 for training machine learning models.
Composition of a sequence of subsampled shuffle models: In Figure 2, we plot several bounds on the approximate (✏, )-DP for a composition of T mechanisms (M1, . . . ,MT ), where Mt is
a subsampled shuffle mechanism for t 2 [T ]. In all our experiments reported in Figure 2, we fix = 10 8. We observe that our new bound on the RDP of the subsampled shuffle mechanism achieves a significant saving in total privacy ✏ compared to the state-of-the-art. For example, we save a factor of 14⇥ compared to the bound on DP [24] with strong composition theorem [34] and 2.5⇥ compared to the bound on the RDP given in [29] with subsampled RDP [43] in computing the overall privacy parameter ✏ for number of iterations T = 105, subsampling parameter = 0.001, LDP parameter ✏0 = 2, and number of clients n = 106. We observe in Figure 2b that the bound given in [24] with the strong composition theorem [34] behaves better than the bound on the RDP [29] with subsampled RDP bound [43] when the number of subsampled clients per iteration is equal to k = n = 104; however, our bound beats both of them.6 In Figure 2c, we fix the number of subsampled clients per iteration to be k = n = 103, and hence, the subsampling parameter varies with n.
Distributed private learning: 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 1. 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 1, we choose uniformly at random 10, 000 clients, where each client clips the `1-norm of the gradient with clipping parameter C = 1/100 and applies the R1 ✏0-LDP mechanism proposed in [27] with ✏0 = 1.5. We run Algorithm 1 with = 10 5 for 200 epochs, with learning rate ⌘ = 0.3 for the first 70 epochs, and then decrease it to 0.18 in the remaining epochs.
Figure 3: Privacy-Utility trade-offs on the MNIST dataset with `1-norm clipping.
Figure 3 plots the mean and the standard deviation of privacy-accuracy trade-offs 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 1. 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 [34] to obtain the central privacy parameter ✏.
We observe that we achieve an accuracy of 80%(±1.8) with a total privacy budget of ✏ = 1.4 using our new privacy analysis, whereas, [24] achieves an accuracy of only 70.7%(±2.1) with the same privacy budget of ✏ = 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 a total privacy budget of ✏ = 4.82.

heading: 5 Proof of Theorem 1: Upper Bound
text: For any dataset Dk = (d1, . . . , dk) 2 X k containing of k data points, we define a shuffle mechanism Msh(Dk) as follows:
Msh(Dk) = Hk (R (d1) , . . . ,R (dk)) , (6)
6In fact, there are several parameter regimes of great practical interest for which the results of [24] are not even valid; see Appendix G for more details on this, and also for more numerical comparisons.
where Hk takes k inputs and outputs a uniformly random permutation of them. Recall from (3), for any dataset Dn = (d1, . . . , dn) 2 Xn containing n data points, the subsampled-shuffle mechanism is defined as M (D) := Hk sampnk (R (d1) , . . . ,R (dn)). The proof of Theorem 1 consists of two steps. First, we bound the ternary-| |↵-DP of the shuffle mechanism Msh (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 (⇣-ternary-| |↵-DP of the shuffle mechanism Msh). For any integer k 2, ✏0 > 0, and all ↵ 2, the ⇣-ternary-| |↵-DP of the shuffle mechanism Msh is bounded by:
⇣ (↵)↵ 
8 ><
>:
4 (e ✏0 1)2
ke✏0 + (e✏0 e ✏0)↵e
k 1 8e✏0 if ↵ = 2,
↵ (↵/2)
✓ 2(e2✏0 1)2
ke2✏0
◆↵/2 + (e✏0 e ✏0)↵e k 1 8e✏0 otherwise,
(7)
where k = b k 12e✏0 c+ 1 and (z) = R1 0 x z 1e xdx is the Gamma function.
Theorem 4 is one of the core technical results of this paper, and we prove it in Section 6.
It was shown in [43, Proposition 16] that if a mechanism obeys ⇣-ternary-| |↵-DP, then its subsampled version (with subsampling parameter ) will obey ⇣-ternary-| |↵-DP. Using that result, the authors then bounded the RDP of the subsampled mechanism in [43, Eq. (9)]. Adapting that result to our setting, we have the following lemma. Lemma 2 (From ⇣-ternary-| |↵-DP to subsampled RDP). Suppose the shuffle mechanism Msh obeys ⇣-ternary-| |↵-DP. For any 2, k  n, RDP of the subsampled shuffle mechanism M (with subsampling parameter = k/n) is bounded by: ✏( )  1 1 log 1 + P ↵=2 ↵ ↵⇣(↵)↵ .
Lemma 2 can be seen as a corollary to [43, Proposition 16 and Eq. (9)]. However, for completeness, we prove it in Appendix E.1. Substituting the bound on ⇣(↵) from Theorem 4 into Lemma 2 together with some algebraic manipulation gives proves Theorem 1; see Appendix E.2 for details.

heading: 6 Proof of Theorem 4: Ternary | |↵-DP of the Shuffle Model
text: The proof has two main steps. In the first step, we reduce the problem of deriving ternary divergence for arbitrary neighboring datasets to the problem of deriving the ternary divergence for specific neighboring datasets, D ⇠ D0 ⇠ D00, where all elements in D are the same and D0,D00 differ from D 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 our general problem has the following form:
Dmsame = {(Dm,D0m,D00m) : Dm = (d, . . . , d, d) 2 Xm, D0m = (d, . . . , d, d0) 2 Xm, and D00m = (d, . . . , d, d00) 2 Xm, where d, d0, d00 2 X} , (8)
Consider arbitrary neighboring datasets D = (d1, . . . , dk 1, dk), D0 = (d1, . . . , dk 1, d0k), and D00 = (d1, . . . , dk 1, d00k), each having k elements. For any m 2 {0, . . . , k 1}, we define new neighboring datasets D(k)m+1 = (d00k , . . . , d00k , dk), D 0(k) m+1 = (d 00 k , . . . , d 00 k , d 0 k), and D 00(k) m+1 = (d 00 k , . . . , d 00 k), each having m+ 1 elements. Observe that (D00(k)m+1,D 0(k) m+1,D (k) m+1) 2 Dmsame.
The first step of the proof is given in the following theorem. Theorem 5 (Reduction to the Special Case). Let q = 1e✏0 . We have:
Eh⇠Msh(D00)  Msh(D)(h) Msh(D0)(h)
Msh(D00)(h)
↵
 Em⇠Bin(k 1,q) " E h⇠Msh(D00(k)m+1) " Msh(D(k)m+1)(h) Msh(D 0(k) m+1)(h)
Msh(D00(k)m+1)(h)
↵## . (9)
We know (by Chernoff bound) that the binomial r.v. is concentrated around its mean, which implies that the terms in the RHS of (9) that correspond to m < (1 ⌧)q(k 1) (we will take ⌧ = 1/2) will contribute in a negligible amount. Then we show that Em :=
E h⇠Msh(D00(k)m+1)
 Msh(D(k)m+1)(h) Msh(D 0(k) m+1)(h)
Msh(D00(k)m+1)(h)
↵
is a non-increasing function of m. These obser-
vation together imply that the RHS in (9) is approximately equal to E(1 ⌧)q(k 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 E(1 ⌧)q(n 1), which follows from the result below that holds for any m 2 N. Theorem 6 (| |↵-DP for special case). For any m 2 N, integer ↵ 2, and (D00m,D0m,Dm) 2 Dmsame,
Eh⇠Msh(Dm)  Msh(D0m)(h) Msh(D00m)(h)
Msh(Dm)(h)
↵ 
8 <
: 4 (e ✏0 1)2 me✏0 if ↵ = 2, ↵ (↵/2) ⇣
2(e2✏0 1)2 me2✏0
⌘↵/2 otherwise.
Missing details of how Theorem 4 follows from Theorems 5, 6 can be found in Appendix C.4.
Proof sketch of Theorem 5. Let pi, i 2 [k],p0k,p00k denote the distributions of R when the input data point is di, d0k, d 00 k , respectively. The main idea of the proof is the observation that each pi can be written as a mixture distribution pi = 1 e✏0 p 00 k + 1 1e✏0 p̃i, where p̃i is defined in terms of pi,p00k . So, instead of client i 2 [k 1] mapping its data point di according to pi, we can view it as the client i maps di according to p00k with probability (w.p.) 1/e✏0 and according to p̃i w.p. (1 1/e✏0). As a result, the number of clients that sample from the distribution p00k follows a binomial distribution Bin(k 1, 1/e✏0 ). This allows us to write the distribution of Msh when clients map their data points according to p1, . . . ,pk,p0k,p 00 k as a convex combination of the distribution of M when clients map their data points according to p̃1, . . . , p̃k 1,pk,p0k,p 00 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 Msh in terms of the same convex combination of the ternary divergence between the resulting triples of distributions of Msh as in Lemma 4. Using a monotonicity argument (see Lemma 5), we can remove the effect of clients that do not sample from the distribution p00k 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), which proves Theorem 5. See Appendix C.1 for a complete proof. ⌅
Proof sketch of Theorem 6. Consider (D00m,D0m,Dm) 2 Dmsame as in the statement of Theorem 6. First we observe that for any ↵ 1 and any three distributions p, q, r over the same domain, we can write Er h p q r ↵ i  2↵ 1 Er ⇥ p r 1 ↵⇤+ Er ⇥ q r 1
↵⇤ . This is a straight-forward application of the standard inequality |x + y|↵  2↵ 1(|x|↵ + |y|↵) which holds for all x, y 2 R and ↵ 1. Now, by taking p = Msh(D0m), q = Msh(D00m), and r = Msh(Dm), we reduce the problem of computing the ternary | |↵-divergence (which we need to bound) to the problem of computing the Pearson-Vajda divergence [43], which we can write in terms of the ↵-th absolute moment of the r.v. X : AmB ! R, defined as X(h) := Msh(D0)(h) Msh(Dm)(h) 1 for all h 2 AmB (where D0 2 {D0m,D00m}) and distributed according to X(h) ⇠Msh(Dm)(h). In [29], the authors have bounded the absolute moments of the r.v. X(h) by showing that X(h) is sub-Gaussian r.v. and using standard concentration results. See Appendix C.3 for a complete proof. ⌅

heading: 7 Discussion
text: 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 1 is an important unresolved question. Another direction to explore would be to analyze the RDP of the subsampled shuffle model for different sub-sampling techniques such as Poisson subsampling [45], random check-in [9], or 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 a small subset of users could insert malicious inputs to disrupt the learning process or 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.

heading: Acknowledgment
text: This work was supported in part by NSF grants #2007714 and #1955632 and a Google Faculty research award and an Amazon Research Award.

Review summaries:
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.

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.  The broad type of mechanism studied in this paper is as follows:\ Setup: - Consider dataset $(d_1, \ldots, d_n)$ where client #$i$ has the datapoint $d_i \in \mathcal{X}$. - Consider any $\epsilon_0$-locally differentially private mechanism $\mathcal{R} : \mathcal{X} \to [B]$.  (One round of) the mechanism is as follows: - $k$ out of $n$ clients are chosen. Each chosen client $i$ send $\mathcal{R}(d_i)$ to the _shuffler_. - 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.  The 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$.  One 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.  The paper uses the recently introduced technique of _ternary-$|\chi|^{\alpha}$-differential-privacy_ to prove the theorems.

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.