# Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed
Learning

Antonious M. Girgis, Deepesh Data, Suhas Diggavi

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

##  1 Introduction

As learning moves towards the edge, there is a need to collaborate to build
learning models111This 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.,
such as in federated learning [KMY+16, YLCT19, KMA+19]. 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 (4) in Section 2). To obtain a model
parametrized by $\theta$ using ERM, the commonly used mechanism is Stochastic
Gradient Descent (SGD) [Bot10]. 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) [DMNS06] 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
[DMNS06], for distributed learning the more appropriate notion is of local
differential privacy (LDP) [KLN+11, DJW13]. Here, each client randomizes its
interactions with the server from whom the data is to be kept private (_e.g.,_
see industrial implementations [EPK14, Gre16, DKY17]). However, LDP mechanisms
suffer from poor performance in comparison with the central DP mechanisms
[DJW13, KLN+11, KBR16]. To overcome this, a new privacy framework using
anonymization has been proposed in the so-called _shuffled model_ [EFM+19,
GGK+19, BBGN19b, GPV19, BBGN19a, CSU+19, BBGN19c, BBGN20]. 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 (4) 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._ [ACG+16] developed a
framework for tighter analysis of such compositions, and this was later
reformulated in terms of Renyi Differential Privacy (RDP) [Mir17], and mapping
this back to DP guarantee [MTZ19]. Therefore, studying RDP is important to
obtaining strong composition privacy results, and is the focus of this paper.

Figure 1: An iteration from the CLDP-SGD Algorithm, where $3$ clients are
randomly chosen at each iteration. Each client sends the private gradient
$\mathcal{R}_{p}\left(g_{t}(d_{i})\right)$ to the shuffler that randomly
permutes the gradients before passing them to the server.

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

$\theta_{t+1}\leftarrow\theta_{t}-\eta_{t}\frac{1}{|\mathcal{I}|}\sum_{i\in\mathcal{I}}\mathcal{R}(\nabla
f_{i}(\theta_{t})),$

where $\mathcal{R}$ is the local randomization mechanism and $\mathcal{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
[KLN+11, Ull17]. 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 (4) 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 $\epsilon_{0}$-LDP
mechanism as a function of the RDP order $\lambda$, subsampling rate $\gamma$,
the LDP parameter $\epsilon_{0}$, and the number of clients $n$; see Theorem
1. The bound is explicit and amenable to numerics, including all
constants.222As emphasized in [WBK19], “in differential privacy, constants
matter”. Furthermore, the bounds are valid for generic LDP mechanisms and all
parameter regimes.333Some of the best known approximate DP bounds for the
shuffle model [BBGN19c, FMT20] are restricted to certain parameter regimes in
terms of $n,\delta,\epsilon_{0}$, etc. 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
$|\chi|^{\alpha}$-DP [WBK19] of shuffle (non sub-sampled) mechanisms; see
Lemma 2. Then we reduce the computation of the ternary $|\chi|^{\alpha}$-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
$|\chi|^{\alpha}$-DP of the shuffle mechanisms for triples of neighboring
datasets having special structures by bounding the Pearson-Vajda divergence
[WBK19] 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
[GDD+21b], to extend their privacy analysis to RDP and significantly
strengthening their privacy guarantees.

  * •

Numerically, we save a factor of $14\times$ in privacy ($\epsilon$) over the
best known results for approximate DP for shuffling [FMT20] combined with
strong composition [KOV15] for $T=10^{5},\gamma=0.001,n=10^{6}$. Translating
these to privacy-performance operating point in distributed optimization, over
the MNIST data set with $\ell_{\infty}$-norm clipping we numerically show
gains: For the same privacy budget of $\epsilon=1.4$, we get a test
performance of $80\%$ whereas using strong composition the test performance of
[FMT20] is $70\%$; furthermore, we achieve $90\%$ accuracy with the total
privacy budget $\epsilon=2.91$, whereas, [FMT20] (with strong composition)
achieve the same accuracy with a total privacy budget of $\epsilon=4.82$. See
Section 4 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, [EFM+20] and [GDD+21b]
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.,_ [DRV10, KOV15]), which are
known to be loose for composition [ACG+16]. 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 [MTZ19, WBK19, ZW19] 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 of the
shuffled model was very recently studied in [GDD+21a], 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
$|\chi|^{\alpha}$-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.

##  2 Preliminaries and Problem Formulation

We use several privacy definitions throughout this paper. Among these, the
local and central differential privacy definitions are standard. The other
privacy definitions (Renyi DP and ternary $|\chi|^{\alpha}$-DP) are relatively
less standard and we define them below.

######  Definition 1 (Local Differential Privacy - LDP [KLN+11]).

For $\epsilon_{0}\geq 0$, a randomized mechanism
$\mathcal{R}:\mathcal{X}\to\mathcal{Y}$ is said to be $\epsilon_{0}$-local
differentially private (in short, $\epsilon_{0}$-LDP), if for every pair of
inputs $d,d^{\prime}\in\mathcal{X}$, we have

$~{}\Pr[\mathcal{R}(d)\in\mathcal{S}]\leq
e^{\epsilon_{0}}\Pr[\mathcal{R}(d^{\prime})\in\mathcal{S}],\qquad\forall\mathcal{S}\subseteq\mathcal{Y}.$
(1)

Let $\mathcal{D}=\\{d_{1},\ldots,d_{n}\\}$ denote a dataset comprising $n$
points from $\mathcal{X}$. We say that two datasets
$\mathcal{D}=\\{d_{1},\ldots,d_{n}\\}$ and
$\mathcal{D}^{\prime}=\\{d_{1}^{\prime},\ldots,d_{n}^{\prime}\\}$ are
neighboring (and denoted by $\mathcal{D}\sim\mathcal{D}^{\prime}$) if they
differ in one data point, i.e., there exists an $i\in[n]$ such that $d_{i}\neq
d^{\prime}_{i}$ and for every $j\in[n],j\neq i$, we have
$d_{j}=d^{\prime}_{j}$.

######  Definition 2 (Central Differential Privacy - DP [DMNS06, DR14]).

For $\epsilon,\delta\geq 0$, a randomized mechanism
$\mathcal{M}:\mathcal{X}^{n}\to\mathcal{Y}$ is said to be
$(\epsilon,\delta)$-differentially private (in short, $(\epsilon,\delta)$-DP),
if for all neighboring datasets
$\mathcal{D},\mathcal{D}^{\prime}\in\mathcal{X}^{n}$ and every subset
$\mathcal{S}\subseteq\mathcal{Y}$, we have

$~{}\Pr\left[\mathcal{M}(\mathcal{D})\in\mathcal{S}\right]\leq
e^{\epsilon_{0}}\Pr\left[\mathcal{M}(\mathcal{D}^{\prime})\in\mathcal{S}\right]+\delta.$
(2)

######  Definition 3 ($(\lambda,\epsilon)$-RDP (Renyi Differential Privacy)
[Mir17]).

A randomized mechanism $\mathcal{M}:\mathcal{X}^{n}\to\mathcal{Y}$ is said to
have $\epsilon$-Renyi differential privacy of order $\lambda\in(1,\infty)$ (in
short, $(\lambda,\epsilon(\lambda))$-RDP), if for any neighboring datasets
$\mathcal{D}$, $\mathcal{D}^{\prime}\in\mathcal{X}^{n}$, the Renyi divergence
of order $\lambda$ between $\mathcal{M}(\mathcal{D})$ and
$\mathcal{M}(\mathcal{D}^{\prime})$ is upper-bounded by $\epsilon(\lambda)$,
i.e.,

$D_{\lambda}(\mathcal{M}(\mathcal{D})||\mathcal{M}(\mathcal{D}^{\prime}))=\frac{1}{\lambda-1}\log\left(\mathbb{E}_{\theta\sim\mathcal{M}(\mathcal{D}^{\prime})}\left[\left(\frac{\mathcal{M}(\mathcal{D})(\theta)}{\mathcal{M}(\mathcal{D}^{\prime})(\theta)}\right)^{\lambda}\right]\right)\leq\epsilon(\lambda),$
(3)

where $\mathcal{M}(\mathcal{D})(\theta)$ denotes the probability that
$\mathcal{M}$ on input $\mathcal{D}$ generates the output $\theta$.

######  Definition 4 ($\zeta$-Ternary $|\chi|^{\alpha}$-differential privacy
[WBK19]).

A randomized mechanism $\mathcal{M}:\mathcal{X}^{n}\to\mathcal{Y}$ is said to
have $\zeta$-ternary-$|\chi|^{\alpha}$-DP, if for any triple of mutually
adjacent datasets
$\mathcal{D},\mathcal{D}^{\prime},\mathcal{D}^{\prime\prime}\in\mathcal{X}^{n}$
(i.e., they mutually differ in the same location), the
ternary-$|\chi|^{\alpha}$ divergence of
$\mathcal{M}(\mathcal{D}),\mathcal{M}(\mathcal{D}^{\prime}),\mathcal{M}(\mathcal{D}^{\prime})$
is upper-bounded by $(\zeta(\alpha))^{\alpha}$ for all $\alpha\geq 1$ (where
$\zeta$ is a function from $\mathbb{R}^{+}$ to $\mathbb{R}^{+}$), i.e.,

$D_{|\chi|^{\alpha}}\left(\mathcal{M}(\mathcal{D}),\mathcal{M}(\mathcal{D}^{\prime})||\mathcal{M}(\mathcal{D}^{\prime\prime})\right):=\mathbb{E}_{\mathcal{M}(\mathcal{D}^{\prime\prime})}\left[\left|\frac{\mathcal{M}(\mathcal{D})-\mathcal{M}(\mathcal{D}^{\prime})}{\mathcal{M}(\mathcal{D}^{\prime\prime})}\right|^{\alpha}\right]\leq\left(\zeta(\alpha)\right)^{\alpha}.$

The ternary $|\chi|^{\alpha}$-DP was proposed in [WBK19] to characterize the
RDP of the sub-sampled mechanism without shuffling. In this work, we analyze
the ternary $|\chi|^{\alpha}$-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 [CKS20, BBG+20]).

Suppose for any $\lambda>1$, a mechanism $\mathcal{M}$ is
$\left(\lambda,\epsilon\left(\lambda\right)\right)$-RDP. Then, the mechanism
$\mathcal{M}$ is $\left(\epsilon,\delta\right)$-DP, where $\delta>0$ is
arbitrary and $\epsilon$ is given by

$\epsilon=\min_{\lambda}\left(\epsilon\left(\lambda\right)+\frac{\log\left(1/\delta\right)+\left(\lambda-1\right)\log\left(1-1/\lambda\right)-\log\left(\lambda\right)}{\lambda-1}\right).$

###  2.1 Problem formulation

We consider a distributed private learning setup comprising a set of $n$
clients, where the $i$th client has a data point $d_{i}$ drawn from a universe
$\mathcal{X}$ for $i\in\left[n\right]$; see also Figure 1. Let
$\mathcal{D}=\left(d_{1},\ldots,d_{n}\right)$ 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_{\theta\in\mathcal{C}}\Big{(}F(\theta,\mathcal{D}):=\frac{1}{n}\sum_{i=1}^{n}f(\theta,d_{i})\Big{)},$
(4)

where $\mathcal{C}\subset\mathbb{R}^{d}$ is a closed convex set, and
$f:\mathcal{C}\times\mathcal{D}\to\mathbb{R}$ is the loss function. Our goal
is to construct a global learning model $\theta$ via stochastic gradient
descent (SGD) while preserving privacy of individual data points in the
training dataset $\mathcal{D}$ by providing strong DP guarantees.

Algorithm 1 $\mathcal{A}_{\text{cldp}}$: CLDP-SGD

1:Input: Datasets $\mathcal{D}=\left(d_{1},\ldots,d_{n}\right)$, LDP privacy
parameter $\epsilon_{0}$, gradient norm bound $C$, and learning rate schedule
$\\{\eta_{t}\\}$.

2:Initialize: $\theta_{0}\in\mathcal{C}$

3:for $t\in\left[T\right]$ do

4: Client sampling: A random set $\mathcal{U}_{t}$ of $k$ clients is chosen.

5: for clients $i\in\mathcal{U}_{t}$ do

6: Compute gradient:
$\mathbf{g}_{t}\left(d_{i}\right)\leftarrow\nabla_{\theta_{t}}f\left(\theta_{t},d_{i}\right)$

7: Clip gradient:
$\tilde{\mathbf{g}}_{t}\left(d_{i}\right)\leftarrow\mathbf{g}_{t}\left(d_{i}\right)/\max\left\\{1,\frac{\|\mathbf{g}_{t}\left(d_{i}\right)\|_{p}}{C}\right\\}$

8: Client $i$ sends
$\mathcal{R}_{p}\left(\tilde{\mathbf{g}}_{t}\left(d_{i}\right)\right)$ to the
shuffler.

9: Shuffling: The shuffler sends random permutation of
$\\{\mathcal{R}_{p}\left(\tilde{\mathbf{g}}_{t}\left(d_{i}\right)\right):i\in\mathcal{U}_{t}\\}$
to the server.

10: Aggregate:
$\overline{\mathbf{g}}_{t}\leftarrow\frac{1}{k}\sum_{i\in\mathcal{U}_{t}}\mathcal{R}_{p}\left(\tilde{\mathbf{g}}_{t}\left(d_{i}\right)\right)$

11: Descent Step:
$\theta_{t+1}\leftarrow\prod_{\mathcal{C}}\left(\theta_{t}-\eta_{t}\overline{\mathbf{g}}_{t}\right)$,
where $\prod_{\mathcal{C}}$ is the projection operator onto the set
$\mathcal{C}$.

12:

13:Output: The model $\theta_{T}$ and the privacy parameters $\epsilon$,
$\delta$.

We revisit the CLDP-SGD algorithm presented in [GDD+21b] and described in
Algorithm 1 to solve the ERM (4). In each step of CLDP-SGD, we choose
uniformly at random a set $\mathcal{U}_{t}$ of $k\leq n$ clients out of $n$
clients. Each client $i\in\mathcal{U}_{t}$ computes and clips the
$\ell_{p}$-norm of the gradient
$\nabla_{\theta_{t}}f\left(\theta_{t},d_{i}\right)$ to apply the LDP mechanism
$\mathcal{R}_{p}$, where $\mathcal{R}_{p}:\mathcal{B}_{p}^{d}\to\\{0,1\\}^{b}$
is an $\epsilon_{0}$-LDP mechanism when inputs come from the $\ell_{p}$-norm
ball
$\mathcal{B}_{p}^{d}=\\{\boldsymbol{x}\in\mathbb{R}^{d}:\|\boldsymbol{x}\|_{p}\leq
1\\}$, where
$\|\boldsymbol{x}\|_{p}=\left(\sum_{i=1}^{d}|x_{i}|^{p}\right)^{1/p}$ denotes
the $\ell_{p}$-norm of the vector $\boldsymbol{x}\in\mathbb{R}^{d}$. In
[GDD+21b], we proposed different $\epsilon_{0}$-LDP mechanisms for general
$\ell_{p}$-norm balls. After that, the shuffler randomly permutes the received
$k$ gradients
$\\{\mathcal{R}_{p}\left(\tilde{\mathbf{g}}_{t}\left(d_{i}\right)\right)\\}_{i\in\mathcal{U}_{t}}$
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.

##  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 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 $\epsilon_{0}$-LDP mechanism $\mathcal{R}$, whose range
is a discrete set $\left[B\right]=\left\\{1,\ldots,B\right\\}$ for some
$B\in\mathbb{N}:=\\{1,2,3,\ldots\\}$. Here, $[B]$ could be the whole of
$\mathbb{N}$. Let $\mathcal{M}(\mathcal{D})$ be a subsampled shuffle mechanism
defined as follows: First subsample $k\leq n$ clients of the $n$ clients
(without replacement), where $\gamma=\frac{k}{n}$ denotes the sampling
parameter. Each client $i$ out of the $k$ selected clients applies
$\mathcal{R}$ on $d_{i}$ and sends $\mathcal{R}(d_{i})$ to the
shuffler,444With a slight abuse of notation, in this paper we write
$\mathcal{R}(d_{i})$ to denote that $\mathcal{R}$ takes as its input the
gradient computed on $d_{i}$ using the current parameter vector. who randomly
permutes the received $k$ inputs and outputs the result. To formalize this,
let $\mathcal{H}_{k}:\mathcal{Y}^{k}\to\mathcal{Y}^{k}$ denote the shuffling
operation that takes $k$ inputs and outputs their uniformly random
permutation. Let $\mathrm{samp}_{k}^{n}:\mathcal{X}^{n}\to\mathcal{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

$\mathcal{M}\left(\mathcal{D}\right):=\mathcal{H}_{k}\circ\mathrm{samp}_{k}^{n}\left(\mathcal{R}\left(d_{1}\right),\ldots,\mathcal{R}\left(d_{n}\right)\right).$
(5)

Observe that each iteration of Algorithm 1 can be represented as an output of
the subsampled shuffle mechanism $\mathcal{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
$\mathcal{H}_{k}$ is a random permutation of the $k$ outputs of $\mathcal{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 $\mathcal{A}_{B}^{k}$ as

$\mathcal{A}_{B}^{k}=\bigg{\\{}\boldsymbol{h}=\left(h_{1},\ldots,h_{B}\right):\sum_{j=1}^{B}h_{j}=k\bigg{\\}},$
(6)

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 $\mathcal{M}$ is a distribution over
$\mathcal{A}_{B}^{k}$.

Our main results for the RDP of the subsampled shuffled mechanism (defined in
(5)) 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 Section 7).

######  Theorem 1 (Upper Bound).

For any $n\in\mathbb{N}$, $k\leq n$, $\epsilon_{0}\geq 0$, and any integer
$\lambda\geq 2$, the RDP of the subsampled shuffle mechanism $\mathcal{M}$
(defined in (5)) is upper-bounded by

$\epsilon(\lambda)\leq\frac{1}{\lambda-1}\log\left(1+4\binom{\lambda}{2}\gamma^{2}\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{\epsilon_{0}}}+\sum_{j=3}^{\lambda}\binom{\lambda}{j}\gamma^{j}j\Gamma\left(j/2\right)\left(\frac{2\left(e^{2\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{2\epsilon_{0}}}\right)^{j/2}+\Upsilon\right),$

where $\overline{k}=\lfloor\frac{k-1}{2e^{\epsilon_{0}}}\rfloor+1$,
$\gamma=\frac{k}{n}$, and
$\Gamma\left(z\right)=\int_{0}^{\infty}x^{z-1}e^{-x}dx$ is the Gamma function.
The term $\Upsilon$ is given by
$\Upsilon=\left(\left(1+\gamma\frac{e^{2\epsilon_{0}}-1}{e^{\epsilon_{0}}}\right)^{\lambda}-1-\lambda\gamma\frac{e^{2\epsilon_{0}}-1}{e^{\epsilon_{0}}}\right)e^{-\frac{k-1}{8e^{\epsilon_{0}}}}$.

######  Theorem 2 (Lower Bound).

For any $n\in\mathbb{N}$, $k\leq n$, $\epsilon_{0}\geq 0$, and any integer
$\lambda\geq 2$, the RDP of the subsampled shuffle mechanism $\mathcal{M}$
(defined in (5)) is lower-bounded by

$\epsilon\left(\lambda\right)\geq\frac{1}{\lambda-1}\log\left(1+\binom{\lambda}{2}\gamma^{2}\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{ke^{\epsilon_{0}}}+\sum_{j=3}^{\lambda}\binom{\lambda}{j}\gamma^{j}\left(\frac{\left(e^{2\epsilon_{0}}-1\right)}{ke^{\epsilon_{0}}}\right)^{j}\mathbb{E}\left(m-\frac{k}{e^{\epsilon_{0}}+1}\right)^{j}\right),$

where expectation is taken w.r.t. the binomial r.v.
$m\sim\text{Bin}\left(k,p\right)$ with parameter
$p=\frac{1}{e^{\epsilon_{0}}+1}$.

The CLDP-SGD algorithm and its privacy-convergence trade-offs (stated in
Theorem 3 below) are given for a general local randomizer $\mathcal{R}_{p}$
(whose inputs comes from an $\ell_{p}$-ball for any $p\in[1,\infty]$) that
satisfies the following conditions: (i) The randomized mechanism
$\mathcal{R}_{p}$ is an $\epsilon_{0}$-LDP mechanism. (ii) The randomized
mechanism $\mathcal{R}_{p}$ is unbiased, i.e.,
$\mathbb{E}\left[\mathcal{R}_{p}\left(\mathbf{x}\right)|\mathbf{x}\right]=\mathbf{x}$
for all $\mathbf{x}\in\mathcal{B}_{p}(a)$, where $a$ is the radius of the ball
$\mathcal{B}_{p}$. (iii) The output of the randomized mechanism
$\mathcal{R}_{p}$ can be represented using $B\in\mathbb{N}^{+}$ bits. (iv) The
randomized $\mathcal{R}_{p}$ has a bounded variance:
$\sup_{\mathbf{x}\in\mathcal{B}_{p}(a)}\mathbb{E}\|\mathcal{R}_{p}\left(\mathbf{x}\right)-\mathbf{x}\|_{2}^{2}\leq
G_{p}^{2}(a)$, where $G_{p}^{2}$ is a function from $\mathbb{R}^{+}$ to
$\mathbb{R}^{+}$.

[GDD+21b] proposed unbiased $\epsilon_{0}$-LDP mechanisms $\mathcal{R}_{p}$
for several values of norms $p\in[1,\infty]$ that require
$b=\mathcal{O}\left(\log\left(d\right)\right)$ 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
$\epsilon_{0}$-LDP mechanism $\mathcal{R}_{p}$ 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 $\epsilon_{0}$-LDP mechanism
$\mathcal{R}_{p}$ from [GDD+21b], we would also get similar gains in
communication as were obtained in [GDD+21b].

The privacy-convergence trade-off of our algorithm $\mathcal{A}_{\text{cldp}}$
is given below.

######  Theorem 3 (Privacy-Convergence tradeoffs).

Let the set $\mathcal{C}$ be convex with diameter $D$ and the function
$f\left(\theta;.\right):\mathcal{C}\times\mathcal{D}\to\mathbb{R}$ be convex
and $L$-Lipschitz continuous with respect to the $\ell_{g}$-norm, which is the
dual of the $\ell_{p}$-norm. Let
$\theta^{*}=\arg\min_{\theta\in\mathcal{C}}F\left(\theta\right)$ denote the
minimizer of the problem (4). For $\gamma=\frac{k}{n}$, if we run Algorithm
$\mathcal{A}_{\emph{cldp}}$ over $T$ iterations, then we have

  1. 1.

Privacy: $\mathcal{A}_{\emph{cldp}}$ is $\left(\epsilon,\delta\right)$-DP,
where $\delta>0$ is arbitrary and $\epsilon$ is given by

$\epsilon=\min_{\lambda}\left(T\epsilon\left(\lambda\right)+\frac{\log\left(1/\delta\right)+\left(\lambda-1\right)\log\left(1-1/\lambda\right)-\log\left(\lambda\right)}{\lambda-1}\right),$
(7)

where $\epsilon\left(\lambda\right)$ is the RDP of the subsampled shuffle
mechanism given in Theorem 1.

  2. 2.

Convergence: If we run $\mathcal{A}_{\emph{cldp}}$ with
$\eta_{t}=\frac{D}{G\sqrt{t}}$, where
$G^{2}=\max\\{d^{1-\frac{2}{p}},1\\}L^{2}+\frac{G_{p}^{2}(L)}{\gamma n}$, we
get

$\displaystyle\mathbb{E}\left[F\left(\theta_{T}\right)\right]-F\left(\theta^{*}\right)\leq\mathcal{O}\left(\frac{DG\log(T)}{\sqrt{T}}\right).$

The proof outline of Theorem 3 is as follows: Note that
$\mathcal{A}_{\text{cldp}}$ is an iterative algorithm, where in each iteration
we use the subsampled shuffle mechanism as defined in (5), for which we have
computed the RDP guarantees in Theorem 1. Now, for the privacy analysis of
$\mathcal{A}_{\text{cldp}}$, we use the adaptive composition theorem from
[Mir17, 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 Section 8 for a
complete proof of Theorem 3.

######  Remark 1.

Note that our convergence bound is affected by the variance of the
$\epsilon_{0}$-LDP mechanism $\mathcal{R}_{p}$. For example, when $f$ is
$L$-Lipschitz continuous w.r.t. the $\ell_{2}$-norm, we can use the LDP
mechanism $\mathcal{R}_{2}$ proposed in [BDF+18] that has variance
$G_{2}^{2}(L)=14L^{2}d\big{(}\frac{e^{\epsilon_{0}}+1}{e^{\epsilon_{0}}-1}\big{)}^{2}$;
and when $f$ is $L$-Lipschitz continuous w.r.t. the $\ell_{1}$-norm or
$\ell_{\infty}$-norm, we can use the LDP mechanisms $\mathcal{R}_{\infty}$ or
$\mathcal{R}_{1}$, respectively, proposed in [GDD+21b] that have variances
$G_{\infty}^{2}(L)=L^{2}d^{2}\big{(}\frac{e^{\epsilon_{0}}+1}{e^{\epsilon_{0}}-1}\big{)}^{2}$
and
$G_{1}^{2}(L)=L^{2}d\big{(}\frac{e^{\epsilon_{0}}+1}{e^{\epsilon_{0}}-1}\big{)}^{2}$,
respectively. By plugging these variances $G_{p}^{2}(L)$ (for $p=1,2,\infty$)
into Theorem 3, we get the convergence rate of the $L$-Lipschitz continuous
loss function w.r.t. the $\ell_{p}$-norm (for $p=\infty,2,1$).

######  Remark 2.

The privacy parameter in (7) 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.

##  4 Numerical Results

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.

(a) Approx. DP as a function of $T$ for $\epsilon_{0}=2$, $\gamma=0.001$,
$n=10^{6}$

(b) Approx. DP as a function of $T$ for $\epsilon_{0}=1$, $\gamma=0.001$,
$n=10^{7}$

(c) Approx. DP as a function of $n$ for $\epsilon_{0}=2$, $\gamma n=10^{3}$,
$T=10^{5}$

Figure 2: Comparison of several bounds on the Approximate
$\left(\epsilon,\delta\right)$-DP for composition of a sequence of subsampled
shuffle mechanisms for $\delta=10^{-8}$: (i) Approximate DP obtained from our
upper bound on the RDP in Theorem 1 (blue); (ii) Approximate DP obtained from
our lower bound on the RDP in Theorem 2 (red); and (iii) Applying the strong
composition theorem [KOV15] after getting the Approximate DP of the shuffled
model given in [FMT20] with subsampling [Ull17] (magenta).

(a) Approx. DP as a function of $T$ for $\epsilon_{0}=1$, $\gamma=0.001$,
$n=10^{6}$

(b) Approx. DP as a function of $T$ for $\epsilon_{0}=1$, $\gamma=0.001$,
$n=10^{7}$

(c) Approx. DP as a function of $n$ for $\epsilon_{0}=1$, $\gamma n=10^{4}$,
$T=10^{5}$

Figure 3: Comparison of our bound on the Approximate
$\left(\epsilon,\delta\right)$-DP (blue) for composition of a sequence of
subsampled shuffle mechanisms for $\delta=10^{-8}$ with applying the strong
composition theorem [KOV15] after getting the Approximate DP of the shuffled
model given in [FMT20] with subsampling [Ull17] (magenta).

(a) Approx. DP as a function of $T$ for $\epsilon_{0}=3$, $\gamma=0.001$,
$n=10^{6}$

(b) Approx. DP as a function of $T$ for $\epsilon_{0}=3$, $\gamma=0.0001$,
$n=10^{7}$

(c) Approx. DP as a function of $n$ for $\epsilon_{0}=3$, $\gamma n=10^{3}$,
$T=10^{5}$

Figure 4: Comparison of several bounds on the Approximate
$\left(\epsilon,\delta\right)$-DP for composition of a sequence of subsampled
shuffle mechanisms for $\delta=10^{-8}$: (i) Approximate DP obtained from our
upper bound on the RDP in Theorem 1 (blue); (ii) Approximate DP obtained from
our lower bound on the RDP in Theorem 2 (red); and (iv) Applying the strong
composition theorem [KOV15] after getting the Approximate DP of the shuffled
model given in [FMT20] with subsampling [Ull17] (magenta).

#### Composition of a sequence of subsampled shuffle models:

In Figures 2 and 3, we plot several bounds on the approximate
$\left(\epsilon,\delta\right)$-DP for a composition of $T$ mechanisms
$\left(\mathcal{M}_{1},\ldots,\mathcal{M}_{T}\right)$, where $\mathcal{M}_{t}$
is a subsampled shuffle mechanism for $t\in\left[T\right]$. In all our
experiments reported in Figures 2 and 3, we fix $\delta=10^{-8}$. In Figures
2(c) and 3(c), we fix the number of subsampled clients per iteration to be
$k=\gamma n=10^{3}$ and $k=10^{4}$, respectively. Hence, the subsampling
parameter $\gamma$ varies with $n$. We observe that our new bound on the RDP
of the subsampled shuffle mechanism achieves a significant saving in total
privacy $\epsilon$ compared to the state-of-the-art. For example, we save a
factor of $14\times$ compared to the bound on DP [FMT20] with strong
composition theorem [KOV15] in computing the overall privacy parameter
$\epsilon$ for number of iterations $T=10^{5}$, subsampling parameter
$\gamma=0.001$, LDP parameter $\epsilon_{0}=2$, and number of clients
$n=10^{6}$.

Observe that our RDP bound presented in 1 is general for any values of LDP
parameter $\epsilon_{0}$, number of clients $n$, and RDP order $\lambda\geq
2$. On the other hand, the result of the privacy amplification by shuffling
presented in [FMT20] is valid under the condition on the LDP parameter:

$\epsilon_{0}\leq\log\left(\frac{n}{16\log(2/\delta)}\right).$ (8)

Furthermore, the result of the privacy amplification by shuffling presented in
[BBGN19c] is valid under the condition on the LDP parameter:

$\epsilon_{0}\leq\frac{1}{2}\log\left(\frac{n}{\log(1/\delta)}\right).$ (9)

Thus, if the conditions in (8)-(9) do not hold, then the results in [FMT20,
BBGN19c] have the privacy bound $\epsilon=\epsilon_{0}$ and $\delta=0$. For
example, when total number of clients $n=10^{6}$, LDP parameter
$\epsilon_{0}=3$, and we choose uniformly at random $k=1000$ clients at each
iteration, then the conditions in (8) and (9) do not hold.

In Figure 4, we plot our bound on the approximate
$\left(\epsilon,\delta\right)$-DP for a composition of $T$ mechanisms
$\left(\mathcal{M}_{1},\ldots,\mathcal{M}_{T}\right)$, where $\mathcal{M}_{t}$
is a subsampled shuffle mechanism for $t\in\left[T\right]$. In all our
experiments reported in Figure 4, we fix $\delta=10^{-8}$ and $\epsilon_{0}=3$
and the conditions (8)-(9) do not hold with the parameter setting in these
experiments. Thus, we compare our results with the bound
$\epsilon=\epsilon_{0}$ and $\delta=0$.

Layer | Parameters
---|---
Convolution |  $16$ filters of $8\times 8$, Stride $2$
Max-Pooling | $2\times 2$
Convolution |  $16$ filters of $4\times 4$, Stride $2$
Max-Pooling | $2\times 2$
Fully connected |  $32$ units
Softmax |  $10$ units
Table 1: Model Architecture for MNIST

#### 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 [EFM+20, PTS+20] 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.

(a) Privacy-Utility trade-offs on the MNIST dataset with $\ell_{\infty}$-norm
clipping.

(b) Privacy-Utility trade-offs on the MNIST dataset with $\ell_{2}$-norm
clipping.

Figure 5: Distributed private learning.

In Figure 5(a), we choose uniformly at random $10,000$ clients at each step of
the Algorithm 1, where each client clips the $\ell_{\infty}$-norm of the
gradient with clipping parameter $C=1/100$ and applies the
$\mathcal{R}_{\infty}$ $\epsilon_{0}$-LDP mechanism proposed in [GDD+21b] with
$\epsilon_{0}=1.5$. We run Algorithm 1 with $\delta=10^{-5}$ for $200$ epochs,
with learning rate $\eta=0.3$ for the first $70$ epochs, and then decrease it
to $0.18$ in the remaining epochs. Figure 5(a) plots the mean and the standard
deviation of privacy-accuracy trade-offs averaged over $10$ runs for
$\ell_{\infty}$-norm clipping.

In Figure 5(b), we choose uniformly at random $2,000$ clients at each step of
the Algorithm 1, where each client clips the $\ell_{2}$-norm of the gradient
with clipping parameter $C=0.005$ and applies the $\mathcal{R}_{2}$
$\epsilon_{0}$-LDP mechanism (PrivUnit) proposed in [DJW13] with
$\epsilon_{0}=2$. We run Algorithm 1 with $\delta=10^{-5}$ for $200$ epochs,
with learning rate $\eta=12$ for the first $30$ epochs, and then decrease it
to $4$ in the next $30$ epochs. We decrease the learning rate to $3.5$ for the
remaining epochs. Figure 5(b) plots the mean and the standard deviation of
privacy-accuracy trade-offs averaged over $4$ runs for $\ell_{2}$-norm
clipping.

For our privacy analysis, the total privacy budget is computed by optimizing
over RDP order $\lambda$ using our upper bound given in Theorem 1. For privacy
analysis of [FMT20], we first compute the privacy amplification by shuffling
numerically given in [FMT20]; then we compute its privacy obtained when
amplified via subsampling [Ull17]; and finally we use the strong composition
theorem [KOV15] to obtain the central privacy parameter $\epsilon$.

For the $\ell_{\infty}$-norm clipping, we achieve an accuracy of $80\%(\pm
1.8)$ with a total privacy budget of $\epsilon=1.4$ using our new privacy
analysis, whereas, [FMT20] achieves an accuracy of $70.7\%(\pm 2.1)$ with the
same privacy budget of $\epsilon=1.4$ using the standard composition theorems.
Furthermore, we achieve an accuracy of $90\%(\pm 0.5)$ with total privacy
budget of $\epsilon=2.91$ using our new privacy analysis, whereas, [FMT20]
(together with the standard strong composition theorem) achieve the same
accuracy with a total privacy budget of $\epsilon=4.82$. Similarly, for
$\ell_{2}$-norm clipping, we achieve an accuracy of $81.15\%(\pm 0.7)$ with a
total privacy budget of $\epsilon=3$ using our new privacy analysis, whereas,
[FMT20] achieves an accuracy of only $76.46\%(\pm 1.9)$ with the same privacy
budget of $\epsilon=3$ using the standard composition theorems. Furthermore,
we achieve an accuracy of $89.7\%(\pm 0.5)$ with a total privacy budget of
$\epsilon=5.8$ using our new privacy analysis, whereas, [FMT20] (together with
the standard strong composition theorem) achieve the same accuracy with a
total privacy budget of $\epsilon=18.3$.

##  5 Proof of Theorem 1: Upper Bound

For any dataset $\mathcal{D}_{k}=(d_{1},\ldots,d_{k})\in\mathcal{X}^{k}$
containing of $k$ data points, we define a shuffle mechanism
$\mathcal{M}_{sh}(\mathcal{D}_{k})$ as follows:

$\mathcal{M}_{sh}(\mathcal{D}_{k})=\mathcal{H}_{k}\left(\mathcal{R}\left(d_{1}\right),\ldots,\mathcal{R}\left(d_{k}\right)\right),$
(10)

where $\mathcal{H}_{k}$ takes $k$ inputs and outputs a uniformly random
permutation of them. Recall from (5), for any dataset
$\mathcal{D}_{n}=(d_{1},\ldots,d_{n})\in\mathcal{X}^{n}$ containing $n$ data
points, the subsampled-shuffle mechanism is defined as
$\mathcal{M}\left(\mathcal{D}\right):=\mathcal{H}_{k}\circ\mathrm{samp}_{k}^{n}\left(\mathcal{R}\left(d_{1}\right),\ldots,\mathcal{R}\left(d_{n}\right)\right)$.

The proof of Theorem 1 consists of two steps. First, we bound the
ternary-$|\chi|^{\alpha}$-DP of the shuffle mechanism $\mathcal{M}_{sh}$ (see
Theorem 4), which is the main technical contribution in this proof. Then,
using this, we bound the RDP of the subsampled shuffle mechanism
$\mathcal{M}$.

######  Theorem 4 ($\zeta$-ternary-$|\chi|^{\alpha}$-DP of the shuffle
mechanism $\mathcal{M}_{sh}$).

For any integer $k\geq 2$, $\epsilon_{0}>0$, and all $\alpha\geq 2$, the
$\zeta$-ternary-$|\chi|^{\alpha}$-DP of the shuffle mechanism
$\mathcal{M}_{sh}$ is bounded by:

$\zeta\left(\alpha\right)^{\alpha}\leq\left\\{\begin{array}[]{ll}4\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{\epsilon_{0}}}+(e^{\epsilon_{0}}-e^{-\epsilon_{0}})^{\alpha}e^{-\frac{k-1}{8e^{\epsilon_{0}}}}&\text{if\
}\alpha=2,\\\
\alpha\Gamma\left(\alpha/2\right)\left(\frac{2\left(e^{2\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{2\epsilon_{0}}}\right)^{\alpha/2}+(e^{\epsilon_{0}}-e^{-\epsilon_{0}})^{\alpha}e^{-\frac{k-1}{8e^{\epsilon_{0}}}}&\text{otherwise},\end{array}\right.$
(11)

where $\overline{k}=\lfloor\frac{k-1}{2e^{\epsilon_{0}}}\rfloor+1$ and
$\Gamma\left(z\right)=\int_{0}^{\infty}x^{z-1}e^{-x}dx$ 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 [WBK19, Proposition $16$] that if a mechanism obeys
$\zeta$-ternary-$|\chi|^{\alpha}$-DP, then its subsampled version (with
subsampling parameter $\gamma$) will obey
$\gamma\zeta$-ternary-$|\chi|^{\alpha}$-DP. Using that result, the authors
then bounded the RDP of the subsampled mechanism in [WBK19, Eq. $(9)$].
Adapting that result to our setting, we have the following lemma.

######  Lemma 2 (From $\zeta$-ternary-$|\chi|^{\alpha}$-DP to subsampled RDP).

Suppose the shuffle mechanism $\mathcal{M}_{sh}$ obeys
$\zeta$-ternary-$|\chi|^{\alpha}$-DP. For any $\lambda\geq 2,k\leq n$, RDP of
the subsampled shuffle mechanism $\mathcal{M}$ (with subsampling parameter
$\gamma=k/n$) is bounded by:
$\epsilon(\lambda)\leq\frac{1}{\lambda-1}\log\big{(}1+\sum_{\alpha=2}^{\lambda}\binom{\lambda}{\alpha}\gamma^{\alpha}\zeta(\alpha)^{\alpha}\big{)}$.

Lemma 2 can be seen as a corollary to [WBK19, Proposition $16$ and Eq. $(9)$].
However, for completeness, we prove it in Appendix C. Substituting the bound
on $\zeta(\alpha)$ from Theorem 4 into Lemma 2, we get

$\displaystyle\epsilon\left(\lambda\right)$
$\displaystyle\leq\frac{1}{\lambda-1}\log\left[1+\binom{\lambda}{2}\gamma^{2}\left(4\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{\epsilon_{0}}}+(e^{\epsilon_{0}}-e^{-\epsilon_{0}})^{2}e^{-\frac{k-1}{8e^{\epsilon_{0}}}}\right)\right.$
$\displaystyle\hskip
71.13188pt\left.+\sum_{\alpha=3}^{\lambda}\binom{\lambda}{\alpha}\gamma^{\alpha}\left(\alpha\Gamma(\alpha/2)\left(\frac{2\left(e^{2\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{2\epsilon_{0}}}\right)^{\alpha/2}+(e^{\epsilon_{0}}-e^{-\epsilon_{0}})^{\alpha}e^{-\frac{k-1}{8e^{\epsilon_{0}}}}\right)\right]$
$\displaystyle=\frac{1}{\lambda-1}\log\left[1+4\binom{\lambda}{2}\gamma^{2}\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{\epsilon_{0}}}+\sum_{\alpha=3}^{\lambda}\binom{\lambda}{\alpha}\gamma^{\alpha}\alpha\Gamma(\alpha/2)\left(\frac{2\left(e^{2\epsilon_{0}}-1\right)^{2}}{\overline{k}e^{2\epsilon_{0}}}\right)^{\alpha/2}+\Upsilon\right],$
(12)

where
$\Upsilon=\sum_{\alpha=2}^{\lambda}\binom{\lambda}{\alpha}\gamma^{\alpha}(e^{\epsilon_{0}}-e^{-\epsilon_{0}})^{\alpha}e^{-\frac{k-1}{8e^{\epsilon_{0}}}}=\left(\left(1+\gamma\frac{e^{2\epsilon_{0}}-1}{e^{\epsilon_{0}}}\right)^{\lambda}-1-\lambda\gamma\frac{e^{2\epsilon_{0}}-1}{e^{\epsilon_{0}}}\right)e^{-\frac{k-1}{8e^{\epsilon_{0}}}}$.

The above expression in (12) is the bound given in Theorem 1.

##  6 Proof of Theorem 4: Ternary $|\chi|^{\alpha}$-DP of the Shuffle Model

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,
$\mathcal{D}\sim\mathcal{D}^{\prime}\sim\mathcal{D}^{\prime\prime}$, where all
elements in $\mathcal{D}$ are the same and
$\mathcal{D}^{\prime},\mathcal{D}^{\prime\prime}$ differ from $\mathcal{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:

$\displaystyle\mathcal{D}_{\text{same}}^{m}$
$\displaystyle=\left\\{(\mathcal{D}_{m},\mathcal{D}^{\prime}_{m},\mathcal{D}^{\prime\prime}_{m}):\mathcal{D}_{m}=(d,\ldots,d,d)\in\mathcal{X}^{m},\
\mathcal{D}^{\prime}_{m}=(d,\ldots,d,d^{\prime})\in\mathcal{X}^{m},\text{ and
}\right.$ $\displaystyle\left.\hskip
113.81102pt\mathcal{D}^{\prime\prime}_{m}=(d,\ldots,d,d^{\prime\prime})\in\mathcal{X}^{m},\text{
where }d,d^{\prime},d^{\prime\prime}\in\mathcal{X}\right\\},$ (13)

Consider arbitrary neighboring datasets
$\mathcal{D}=(d_{1},\ldots,d_{k-1},d_{k})$,
$\mathcal{D}^{\prime}=(d_{1},\ldots,d_{k-1},d^{\prime}_{k})$,
$\mathcal{D}^{\prime\prime}=(d_{1},\ldots,d_{k-1},d^{\prime\prime}_{k})$, each
having $k$ elements. For any $m\in\\{0,\ldots,k-1\\}$, we define new
neighboring datasets
$\mathcal{D}_{m+1}^{(k)}=(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d_{k})$,
$\mathcal{D}^{\prime(k)}_{m+1}=(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d^{\prime}_{k})$,
and
$\mathcal{D}^{\prime\prime(k)}_{m+1}=(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k})$,
each having $m+1$ elements. Observe that
$(\mathcal{D}^{\prime\prime(k)}_{m+1},\mathcal{D}^{\prime(k)}_{m+1},\mathcal{D}^{(k)}_{m+1})\in\mathcal{D}_{\text{same}}^{m}$.
The first step of the proof is given in the following theorem:

######  Theorem 5 (Reduction to the Special Case).

Let $q=\frac{1}{e^{\epsilon_{0}}}$. We have:

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}^{\prime})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime})(\boldsymbol{h})}\right|^{\alpha}\right]$
$\displaystyle\hskip
28.45274pt\leq\mathbb{E}_{m\sim\emph{Bin}\left(k-1,q\right)}\left[\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{(k)})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime(k)})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})(\boldsymbol{h})}\right|^{\alpha}\right]\right].$
(14)

We present a proof of Theorem 5 in Section 6.1. We know (by Chernoff bound)
that the binomial r.v. is concentrated around its mean, which implies that the
terms in the RHS of (14) that correspond to $m<(1-\tau)q(k-1)$ (we will take
$\tau=1/2$) will contribute in a negligible amount. Then we show that
$E_{m}:=\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{(k)})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime(k)})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})(\boldsymbol{h})}\right|^{\alpha}\right]$
is a non-increasing function of $m$. These observation together imply that the
RHS in (14) is approximately upper bounded by $E_{(1-\tau)q(k-1)}$.

Since $E_{m}$ 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-\tau)q(n-1)}$, which follows from the result below that holds
for any $m\in\mathbb{N}$.

######  Theorem 6 ($|\chi|^{\alpha}$-DP for special case).

For any $m\in\mathbb{N}$, integer $\alpha\geq 2$, and
$(\mathcal{D}^{\prime\prime}_{m},\mathcal{D}^{\prime}_{m},\mathcal{D}_{m})\in\mathcal{D}_{\text{same}}^{m}$,

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime}_{m})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}\right|^{\alpha}\right]\leq\left\\{\begin{array}[]{ll}4\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{me^{\epsilon_{0}}}&\text{if\
}\alpha=2,\\\
\alpha\Gamma(\alpha/2)\left(\frac{2(e^{2\epsilon_{0}}-1)^{2}}{me^{2\epsilon_{0}}}\right)^{\alpha/2}&\text{otherwise}.\end{array}\right.$

The proof of Theorem 6 is presented in Section 6.2. Missing details of how
Theorem 4 follows from Theorems 5, 6 can be found in Appendix B.

###  6.1 Proof of Theorem 5: Reduction to the Special Case

First, we prove the joint-convexity of the ternary
$|\chi|^{\alpha}$-divergence as it is important in the following proof.

######  Lemma 3 (Joint-convexity of the ternary $|\chi|^{\alpha}$-divergence).

For all $\alpha\geq 1$, the ternary-$|\chi|^{\alpha}$-divergence
$\mathbb{E}\left[\left|\frac{P-Q}{R}\right|^{\alpha}\right]$ is jointly convex
in $P,Q$ and $R$. In other words, if $P_{a}=aP_{0}+(1-a)P_{1}$,
$Q_{a}=aQ_{0}+(1-a)Q_{1}$, and $R_{a}=aR_{0}+(1-a)R_{1}$ for some
$a\in\left[0,1\right]$, then the following holds

$\mathbb{E}\left[\left|\frac{P_{a}-Q_{a}}{R_{a}}\right|^{\alpha}\right]\leq
a\mathbb{E}\left[\left|\frac{P_{0}-Q_{0}}{R_{0}}\right|^{\alpha}\right]+(1-a)\mathbb{E}\left[\left|\frac{P_{1}-Q_{1}}{R_{1}}\right|^{\alpha}\right]$
(15)

###### Proof.

First, observe that $g(x,y)=|x-y|$ is jointly convex on $\mathbb{R}^{2}$,
i.e., if $x_{a}=ax_{0}+(1-a)x_{1}$ and $y_{a}=ay_{0}+(1-a)y_{1}$, we have

$\displaystyle|x_{a}-y_{a}|$
$\displaystyle=|a(x_{0}-y_{0})+(1-a)(x_{1}-y_{1})|$ $\displaystyle\leq
a|x_{0}-y_{0}|+(1-a)|x_{1}-y_{1}|$ (16)

Let $f(x,y)=x^{j}/y^{j-1}$, which is jointly convex on $\mathbb{R}_{+}^{2}$
for $j\geq 1$; see [WBK19, Lemma $20$] for a proof. Thus, we get

$\displaystyle\frac{|P_{a}-Q_{a}|^{j}}{R_{a}^{j-1}}$
$\displaystyle\leq\frac{\left(a|P_{0}-Q_{0}|+(1-a)|P_{1}-Q_{1}|\right)^{j}}{(aR_{0}+(1-a)R_{1})^{j-1}}$
$\displaystyle\leq
a\frac{|P_{0}-Q_{0}|^{j}}{R_{0}^{j-1}}+(1-a)\frac{|P_{1}-Q_{1}|^{j}}{R_{1}^{j-1}},$
(17)

where the first inequality is obtained from (16) and the second inequality is
obtained from the convexity of $f(x,y)$. ∎

Now, we prove Theorem 5. Our proof is an adaptation of the proof of [GDD+21a,
Theorem $4$]. The difference comes from the fact that [GDD+21a, Theorem $4$]
was for Renyi divergence, whereas, here we are working with ternary
$|\chi|^{\alpha}$-divergence. This changes some details and we provide a full
proof of Theorem 5 below.

Let $\boldsymbol{p}_{i}:=(p_{i1},\ldots,p_{iB})$,
$\boldsymbol{p}^{\prime}_{k}:=(p^{\prime}_{k1},\ldots,p^{\prime}_{kB})$,
$\boldsymbol{p}^{\prime\prime}_{k}:=(p^{\prime\prime}_{k1},\ldots,p^{\prime\prime}_{kB})$
denote the probability distributions over $\mathcal{Y}$ when the input to
$\mathcal{R}$ is $d_{i}$, $d^{\prime}_{k}$, and $d^{\prime\prime}_{k}$
respectively, where $p_{ij}=\Pr[\mathcal{R}(d_{i})=j]$ for all $j\in[B]$ and
$i\in\left[n\right]$. Let
$\mathcal{P}=\\{\boldsymbol{p}_{i}:i\in\left[k\right]\\}$,
$\mathcal{P}^{\prime}=\\{\boldsymbol{p}_{i}:i\in\left[k-1\right]\\}\bigcup\\{\boldsymbol{p}^{\prime}_{k}\\}$,
and
$\mathcal{P}^{\prime\prime}=\\{\boldsymbol{p}_{i}:i\in\left[k-1\right]\\}\bigcup\\{\boldsymbol{p}^{\prime\prime}_{k}\\}$.

For $i\in[k-1]$, let
$\mathcal{P}_{-i}=\mathcal{P}\setminus\\{\boldsymbol{p}_{i}\\}$ and also
$\mathcal{P}_{-k}=\mathcal{P}\setminus\\{\boldsymbol{p}_{k}\\}$. Here,
$\mathcal{P},\mathcal{P}^{\prime},\mathcal{P}^{\prime\prime}$ correspond to
the datasets
$\mathcal{D}=\\{d_{1},\ldots,d_{k}\\},\mathcal{D}^{\prime}=\\{d_{1},\ldots,d_{k-1},d^{\prime}_{k}\\}$,
and
$\mathcal{D}^{\prime\prime}=\\{d_{1},\ldots,d_{k-1},d^{\prime\prime}_{k}\\}$
respectively, and for any $i\in[k]$, $\mathcal{P}_{-i}$ corresponds to the
dataset $\mathcal{D}_{-i}=\\{d_{1},\ldots,d_{i-1},d_{i+1},\ldots,d_{k}\\}$.

For any collection
$\mathcal{P}=\\{\boldsymbol{p}_{1},\ldots,\boldsymbol{p}_{k}\\}$ of $k$
distributions, we define $F(\mathcal{P})$ to be the distribution over
$\mathcal{A}_{B}^{k}$ (which is the set of histograms on $B$ bins with $k$
elements as defined in (6)) that is induced when every client $i$ (independent
to the other clients) samples an element from $[B]$ accordingly to the
probability distribution $\boldsymbol{p}_{i}$. Formally, for any
$\boldsymbol{h}\in\mathcal{A}_{B}^{k}$, define

$\displaystyle\mathcal{U}_{\boldsymbol{h}}:=\left\\{(\mathcal{U}_{1},\ldots,\mathcal{U}_{B}):\mathcal{U}_{1},\ldots,\mathcal{U}_{B}\subseteq[k]\text{
s.t. }\bigcup_{j=1}^{B}\mathcal{U}_{j}=[k]\text{ and
}|\mathcal{U}_{j}|=h_{j},\forall j\in[B]\right\\}.$ (18)

Note that for each
$(\mathcal{U}_{1},\ldots,\mathcal{U}_{B})\in\mathcal{U}_{\boldsymbol{h}}$,
$\mathcal{U}_{j}$ for $j=1,\ldots,B$ denotes the identities of the clients
that map to the $j$’th element in $[B]$ – here $\mathcal{U}_{j}$’s are
disjoint for all $j\in[B]$. Note also that
$|\mathcal{U}_{\boldsymbol{h}}|=\binom{k}{\boldsymbol{h}}=\frac{k!}{h_{1}!h_{2}!\ldots
h_{B}!}$. It is easy to verify that for any
$\boldsymbol{h}\in\mathcal{A}_{B}^{k}$, $F(\mathcal{P})(\boldsymbol{h})$ is
equal to

$\displaystyle
F(\mathcal{P})(\boldsymbol{h})=\sum_{(\mathcal{U}_{1},\ldots,\mathcal{U}_{B})\in\mathcal{U}_{\boldsymbol{h}}}\prod_{j=1}^{B}\prod_{i\in\mathcal{U}_{j}}p_{ij}$
(19)

Similarly, we can define
$F(\mathcal{P}^{\prime}),F(\mathcal{P}^{\prime\prime}),F(\mathcal{P}_{-i}),F(\mathcal{P}^{\prime}_{-i})$,
and $F(\mathcal{P}^{\prime\prime}_{-i})$. Note that $F(\mathcal{P})$,
$F(\mathcal{P}^{\prime})$ and $F(\mathcal{P}^{\prime\prime})$ are
distributions over $\mathcal{A}_{B}^{k}$, whereas, $F(\mathcal{P}_{-i})$,
$F(\mathcal{P}^{\prime}_{-i})$, and $F(\mathcal{P}^{\prime\prime}_{-i})$ are
distributions over $\mathcal{A}_{B}^{k-1}$. It is easy to see that
$F(\mathcal{P})=\mathcal{M}_{sh}(\mathcal{D})$,
$F(\mathcal{P}^{\prime})=\mathcal{M}_{sh}(\mathcal{D}^{\prime})$, and
$F(\mathcal{P}^{\prime\prime})=\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime})$.

A crucial observation is that any distribution $\boldsymbol{p}_{i}$ can be
written as the following mixture distribution:

$\boldsymbol{p}_{i}=q\boldsymbol{p}^{\prime\prime}_{k}+\left(1-q\right)\tilde{\boldsymbol{p}}_{i},$
(20)

where $q=\frac{1}{e^{\epsilon_{0}}}$. The distribution
$\tilde{\boldsymbol{p}}_{i}=\left[\tilde{p}_{i1},\ldots,\tilde{p}_{iB}\right]$
is given by $\tilde{p}_{ij}=\frac{p_{ij}-qp^{\prime\prime}_{kj}}{1-q}$, where
it is easy to verify that $\tilde{p}_{ij}\geq 0$ and
$\sum_{j=1}^{B}\tilde{p}_{ij}=1$. The idea of writing the distribution of the
output of an LDP mechanism as a mixture distribution was previously proposed
in [BBGN19c, FMT20]. However, the way these mixture distributions are used in
our RDP analysis is quite different from their use in studying the hockey-
stick divergence.

For any $\mathcal{C}\subseteq[k-1]$, define three sets
$\mathcal{P}_{\mathcal{C}},\mathcal{P}^{\prime}_{\mathcal{C}}$, and
$\mathcal{P}^{\prime\prime}_{\mathcal{C}}$ having $k$ distributions each, as
follows:

$\displaystyle\mathcal{P}_{\mathcal{C}}$
$\displaystyle=\\{\hat{\boldsymbol{p}}_{1},\ldots,\hat{\boldsymbol{p}}_{k-1}\\}\bigcup\\{\boldsymbol{p}_{k}\\},$
(21) $\displaystyle\mathcal{P}^{\prime}_{\mathcal{C}}$
$\displaystyle=\\{\hat{\boldsymbol{p}}_{1},\ldots,\hat{\boldsymbol{p}}_{k-1}\\}\bigcup\\{\boldsymbol{p}^{\prime}_{k}\\},$
(22) $\displaystyle\mathcal{P}^{\prime\prime}_{\mathcal{C}}$
$\displaystyle=\\{\hat{\boldsymbol{p}}_{1},\ldots,\hat{\boldsymbol{p}}_{k-1}\\}\bigcup\\{\boldsymbol{p}^{\prime\prime}_{k}\\},$
(23)

where, for every $i\in[k-1]$, $\hat{\boldsymbol{p}}_{i}$ is defined as
follows:

$\hat{\boldsymbol{p}}_{i}=\begin{cases}\boldsymbol{p}^{\prime\prime}_{k}&\text{
if }i\in\mathcal{C},\\\ \tilde{\boldsymbol{p}}_{i}&\text{ if
}i\in[k-1]\setminus\mathcal{C}.\end{cases}$ (24)

In the following lemma, we show that $F(\mathcal{P}),F(\mathcal{P}^{\prime})$,
and $F(\mathcal{P}^{\prime\prime})$ can be written as convex combinations of
$\\{F(\mathcal{P}_{\mathcal{C}}):\mathcal{C}\subseteq[k-1]\\},\\{F(\mathcal{P}^{\prime}_{\mathcal{C}}):\mathcal{C}\subseteq[n-1]\\}$,
and
$\\{F(\mathcal{P}^{\prime\prime}_{\mathcal{C}}):\mathcal{C}\subseteq[k-1]\\}$,
respectively, where for any $\mathcal{C}\subseteq[k-1]$,
$F(\mathcal{P}_{\mathcal{C}}),F(\mathcal{P}^{\prime}_{\mathcal{C}})$. and
$F(\mathcal{P}^{\prime\prime}_{\mathcal{C}})$ can be computed analogously as
in (19).

######  Lemma 4 (Mixture Interpretation [GDD+21a, Lemma $3$]).

$F(\mathcal{P}),F(\mathcal{P}^{\prime})$, and $F(\mathcal{P}^{\prime\prime})$
can be written as the following convex combinations:

$\displaystyle F(\mathcal{P})$
$\displaystyle=\sum_{\mathcal{C}\subseteq[k-1]}q^{|\mathcal{C}|}(1-q)^{k-|\mathcal{C}|-1}F(\mathcal{P}_{\mathcal{C}}),$
(25) $\displaystyle F(\mathcal{P}^{\prime})$
$\displaystyle=\sum_{\mathcal{C}\subseteq[k-1]}q^{|\mathcal{C}|}(1-q)^{k-|\mathcal{C}|-1}F(\mathcal{P}^{\prime}_{\mathcal{C}}),$
(26) $\displaystyle F(\mathcal{P}^{\prime\prime})$
$\displaystyle=\sum_{\mathcal{C}\subseteq[k-1]}q^{|\mathcal{C}|}(1-q)^{k-|\mathcal{C}|-1}F(\mathcal{P}^{\prime\prime}_{\mathcal{C}}),$
(27)

where
$\mathcal{P}_{\mathcal{C}},\mathcal{P}_{\mathcal{C}}^{\prime},\mathcal{P}_{\mathcal{C}}^{\prime\prime}$
are defined in (21)-(24).

From Lemma 3 and Lemma 4, we get

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim
F(\mathcal{P}^{\prime\prime})}\left[\left|\frac{F(\mathcal{P})(\boldsymbol{h})-F(\mathcal{P}^{\prime})(\boldsymbol{h})}{F(\mathcal{P}^{\prime\prime})(\boldsymbol{h})}\right|^{\alpha}\right]$
$\displaystyle\hskip
56.9055pt\leq\sum_{\mathcal{C}\subseteq\left[k-1\right]}q^{|\mathcal{C}|}\left(1-q\right)^{k-|\mathcal{C}|-1}\mathbb{E}_{\boldsymbol{h}\sim
F\left(\mathcal{P}^{\prime\prime}_{\mathcal{C}}\right)}\left[\left|\frac{F(\mathcal{P}_{\mathcal{C}})(\boldsymbol{h})-F(\mathcal{P}^{\prime}_{\mathcal{C}})(\boldsymbol{h})}{F(\mathcal{P}^{\prime\prime}_{\mathcal{C}})(\boldsymbol{h})}\right|^{\alpha}\right].$
(28)

For any $\mathcal{C}\subseteq[k-1]$, let
$\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}}=\\{\tilde{\boldsymbol{p}}_{i}:i\in\left[k-1\right]\setminus\mathcal{C}\\}$.
With this notation, note that
$\mathcal{P}_{\mathcal{C}}\setminus\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}}=\\{\boldsymbol{p}^{\prime\prime}_{k},\ldots,\boldsymbol{p}^{\prime\prime}_{k}\\}\bigcup\\{\boldsymbol{p}_{k}\\}$,
$\mathcal{P}^{\prime}_{\mathcal{C}}\setminus\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}}=\\{\boldsymbol{p}^{\prime\prime}_{k},\ldots,\boldsymbol{p}^{\prime\prime}_{k}\\}\bigcup\\{\boldsymbol{p}^{\prime}_{k}\\}$,
and
$\mathcal{P}^{\prime\prime}_{\mathcal{C}}\setminus\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}}=\\{\boldsymbol{p}^{\prime\prime}_{k},\ldots,\boldsymbol{p}^{\prime\prime}_{k}\\}\bigcup\\{\boldsymbol{p}^{\prime\prime}_{k}\\}$
are a triple of specific neighboring distributions, each containing
$|\mathcal{C}|+1$ distributions. In other words, if we define
$\mathcal{D}_{|\mathcal{C}|+1}^{(k)}=\left(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d_{k}\right)$,
$\mathcal{D}_{|\mathcal{C}|+1}^{\prime(k)}=\left(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d_{k}^{\prime}\right)$,
and
$\mathcal{D}_{|\mathcal{C}|+1}^{\prime\prime(k)}=\left(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d_{k}^{\prime\prime}\right)$,
each having $(|\mathcal{C}|+1)$ data points (note that
$(\mathcal{D}_{|\mathcal{C}|+1}^{\prime\prime(k)},\mathcal{D}_{|\mathcal{C}|+1}^{\prime(k)},\mathcal{D}_{|\mathcal{C}|+1}^{(k)})\in\mathcal{D}_{\text{same}}^{|\mathcal{C}|+1}$),
then the mechanisms $\mathcal{M}_{sh}(\mathcal{D}_{|\mathcal{C}|+1}^{(k)})$,
$\mathcal{M}_{sh}(\mathcal{D}_{|\mathcal{C}|+1}^{\prime(k)})$, and
$\mathcal{M}_{sh}(\mathcal{D}_{|\mathcal{C}|+1}^{\prime\prime(k)})$ will have
distributions
$F(\mathcal{P}_{\mathcal{C}}\setminus\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}})$,
$F(\mathcal{P}^{\prime}_{\mathcal{C}}\setminus\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}})$,
and
$F(\mathcal{P}^{\prime\prime}_{\mathcal{C}}\setminus\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}})$,
respectively.

Now, since
$(\mathcal{D}_{|\mathcal{C}|+1}^{\prime\prime(k)},\mathcal{D}_{|\mathcal{C}|+1}^{\prime(k)},\mathcal{D}_{|\mathcal{C}|+1}^{(k)})\in\mathcal{D}_{\text{same}}^{|\mathcal{C}|+1}$,
if we remove the effect of distributions in
$\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}}$ in the RHS of (28), we
would be able to bound the RHS of (28) using the ternary
$|\chi|^{\alpha}$-divergence for the special neighboring datasets in
$\mathcal{D}_{\text{same}}^{|\mathcal{C}|+1}$. This is precisely what we will
do in the following lemma and the subsequent corollary, where we will
eliminate the distributions in
$\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}}$ in the RHS (28).

The following lemma holds for arbitrary triples
$(\mathcal{P},\mathcal{P}^{\prime},\mathcal{P}^{\prime\prime})$ of neighboring
distributions
$\mathcal{P}=\\{\boldsymbol{p}_{1},\ldots,\boldsymbol{p}_{k-1},\boldsymbol{p}_{k}\\}$,
$\mathcal{P}^{\prime}=\\{\boldsymbol{p}_{1},\ldots,\boldsymbol{p}_{k-1},\boldsymbol{p}^{\prime}_{k}\\}$,
and
$\mathcal{P}^{\prime\prime}=\\{\boldsymbol{p}_{1},\ldots,\boldsymbol{p}_{k-1},\boldsymbol{p}^{\prime\prime}_{k}\\}$,
where we show that the ternary $|\chi|^{\alpha}$-divergence
$\mathbb{E}_{\boldsymbol{h}\sim
F(\mathcal{P}^{\prime\prime})}\left[\left|\frac{F(\mathcal{P})(\boldsymbol{h})-F(\mathcal{P}^{\prime})(\boldsymbol{h})}{F(\mathcal{P}^{\prime\prime})(\boldsymbol{h})}\right|^{\alpha}\right]$
does not decrease when we eliminate a distribution $\boldsymbol{p}_{i}$ (i.e.,
remove the data point $d_{i}$ from the datasets) for any $i\in[k-1]$.

######  Lemma 5 (Monotonicity).

For any $i\in\left[k-1\right]$, we have

$\mathbb{E}_{\boldsymbol{h}\sim
F\left(\mathcal{P}^{\prime\prime}\right)}\left[\left|\frac{F\left(\mathcal{P}\right)(\boldsymbol{h})-F\left(\mathcal{P}^{\prime}\right)(\boldsymbol{h})}{F\left(\mathcal{P}^{\prime\prime}\right)(\boldsymbol{h})}\right|^{\alpha}\right]\leq\mathbb{E}_{\boldsymbol{h}\sim
F\left(\mathcal{P}^{\prime\prime}_{-i}\right)}\left[\left|\frac{F\left(\mathcal{P}_{-i}\right)(\boldsymbol{h})-F\left(\mathcal{P}^{\prime}_{-i}\right)(\boldsymbol{h})}{F\left(\mathcal{P}^{\prime\prime}_{-i}\right)(\boldsymbol{h})}\right|^{\alpha}\right].$
(29)

###### Proof.

This can be proved along the lines of the proof of [GDD+21a, Lemma $5$], which
shows that $\mathbb{E}_{\boldsymbol{h}\sim
F\left(\mathcal{P}^{\prime}\right)}\left[\left(\frac{F\left(\mathcal{P}\right)\left(\boldsymbol{h}\right)}{F\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)}\right)^{\lambda}\right]\leq\mathbb{E}_{\boldsymbol{h}\sim
F\left(\mathcal{P}^{\prime}_{-i}\right)}\left[\left(\frac{F\left(\mathcal{P}_{-i}\right)\left(\boldsymbol{h}\right)}{F\left(\mathcal{P}^{\prime}_{-i}\right)\left(\boldsymbol{h}\right)}\right)^{\lambda}\right]$
holds for all $i\in[k-1]$. This is a result about Renyi divergence, and the
only property of the Renyi divergence that is used in the proof of [GDD+21a,
Lemma $5$] is that $\mathbb{E}_{\boldsymbol{h}\sim
F(\mathcal{P}^{\prime})}\left[\left(\frac{F(\mathcal{P})(\boldsymbol{h})}{F(\mathcal{P}^{\prime})(\boldsymbol{h})}\right)^{\lambda}\right]$
is convex in $\boldsymbol{p}_{i}$ for any $i\in[k-1]$.

Note that Lemma 5 is about the ternary $|\chi|^{\alpha}$-divergence, and the
required convexity about this follows from Lemma 3. So, following the proof of
[GDD+21a, Lemma $5$] and using Lemma 3, proves Lemma 5. ∎

Now, for any given $\mathcal{C}\subseteq[k-1]$, by eliminating the
distributions $\tilde{\boldsymbol{p}}_{i}$ in
$\widetilde{\mathcal{P}}_{[k-1]\setminus\mathcal{C}}=\\{\tilde{\boldsymbol{p}}_{i}:i\in\left[k-1\right]\setminus\mathcal{C}\\}$
from $\mathcal{P}_{C}$, $\mathcal{P}^{\prime}_{C}$, and
$\mathcal{P}^{\prime\prime}_{C}$ (by repeatedly applying Lemma 5), we get that

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim
F\left(\mathcal{P}^{\prime\prime}_{\mathcal{C}}\right)}$
$\displaystyle\left[\left|\frac{F\left(\mathcal{P}_{\mathcal{C}}\right)(\boldsymbol{h})-F\left(\mathcal{P}^{\prime}_{\mathcal{C}}\right)(\boldsymbol{h})}{F\left(\mathcal{P}^{\prime\prime}_{\mathcal{C}}\right)(\boldsymbol{h})}\right|^{\alpha}\right]$
$\displaystyle\hskip
56.9055pt\leq\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime(k)}_{m+1})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}^{(k)}_{m+1})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}^{\prime(k)}_{m+1})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime(k)}_{m+1})(\boldsymbol{h})}\right|^{\alpha}\right],$
(30)

where $m=|\mathcal{C}|$. By substituting from (30) into (28) completes the
proof of Theorem 5.

###  6.2 Proof of Theorem 6: Ternary $|\chi|^{\alpha}$-DP of the Special Case

First, we present the following standard inequality which is important to our
proof.

######  Lemma 6.

Let $x,y\in\mathbb{R}$ be any two real numbers. Then, for all $j\geq 1$, we
have

$|x+y|^{j}\leq 2^{j-1}\left(|x|^{j}+|y|^{j}\right).$ (31)

###### Proof.

The proof is simple from the convexity of the function $f(x)=x^{j}$ for $j\geq
1$.

$\displaystyle|x+y|^{j}$
$\displaystyle=2^{j}\left|\frac{x+y}{2}\right|^{j}\leq
2^{j}\left(\frac{|x|+|y|}{2}\right)^{j}\leq
2^{j}\left(\frac{|x|^{j}+|y|^{j}}{2}\right)=2^{j-1}\left(|x|^{j}+|y|^{j}\right),$

where the second inequality is obtained from the Jensen’s inequality and the
fact that the function $f(x)=x^{j}$ is convex on $\mathbb{R}^{+}$ for all
$j\geq 1$. ∎

From Lemma 6, we get the following corollary.

######  Corollary 1.

Fix an arbitrary $m\in\mathbb{N}$ and consider any three mutually neighboring
datasets $\mathcal{D}_{m},\ \mathcal{D}^{\prime}_{m},\
\mathcal{D}^{\prime\prime}_{m}$, where
$\mathcal{D}_{m}=(d,\ldots,d)\in\mathcal{X}^{m}$,
$\mathcal{D}^{\prime}_{m}=(d,\ldots,d,d^{\prime})\in\mathcal{X}^{m}$ and
$\mathcal{D}^{\prime\prime}_{m}=(d,\ldots,d,d^{\prime\prime})\in\mathcal{X}^{m}$.
The ternary $|\chi|^{\alpha}$-DP is bounded by

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime}_{m})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}\right|^{\alpha}\right]$
$\displaystyle\quad\leq
2^{\alpha-1}\left(\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}-1\right|^{\alpha}\right]+\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}-1\right|^{\alpha}\right]\right).$
(32)

###### Proof.

Fix any $\boldsymbol{h}\in\mathcal{A}_{B}^{m}$, and take
$x=\Big{(}\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}-1\Big{)}$,
$y=-\Big{(}\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}-1\Big{)}$.
Then applying Lemma 6 and taking expectation w.r.t.
$\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m})$ will yield Corollary 1.
∎

######  Remark 3.

Observe that the proof of Corollary 1 does not require
$\mathcal{D}_{m},\mathcal{D}_{m}^{\prime},\mathcal{D}_{m}^{\prime\prime}$ to
be special triple of neighboring datasets such that
$(\mathcal{D}_{m},\mathcal{D}_{m}^{\prime},\mathcal{D}_{m}^{\prime\prime})\in\mathcal{D}_{\text{same}}^{m}$.
In fact, Corollary 1 holds for any triple of distributions $p,q,r$ over the
same domain, for which we can show
$\mathbb{E}_{r}[\left|\frac{p-q}{r}\right|^{\alpha}]\leq
2^{\alpha-1}\left(\mathbb{E}_{r}[\left|\frac{p}{r}-1\right|^{\alpha}]+\mathbb{E}_{r}[\left|\frac{q}{r}-1\right|^{\alpha}]\right)$.

Now, in order to prove Theorem 6, it suffices to bound the expectation terms
on the RHS of (32). This is what we do in the lemma below.

######  Lemma 7 ([GDD+21a, Lemma $6$]).

For any pair of the special pair of neighboring datasets
$\mathcal{D}_{m},\mathcal{D}^{\prime}_{m}$, where
$\mathcal{D}_{m}=(d,\ldots,d)\in\mathcal{X}^{m}$ and
$\mathcal{D}^{\prime}_{m}=(d,\ldots,d,d^{\prime})\in\mathcal{X}^{m}$, we have

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}-1\right|^{\alpha}\right]\leq\left\\{\begin{array}[]{ll}\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{me^{\epsilon_{0}}}&\text{if\
}\alpha=2,\\\
\alpha\Gamma(\alpha/2)\left(\frac{\left(e^{2\epsilon_{0}}-1\right)^{2}}{2me^{2\epsilon_{0}}}\right)^{\alpha/2}&\text{otherwise}.\end{array}\right.$

Substituting the bound from Lemma 7 into Corollary 1, we get

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}^{\prime}_{m})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime}_{m})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m})(\boldsymbol{h})}\right|^{\alpha}\right]\leq\left\\{\begin{array}[]{ll}4\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{me^{\epsilon_{0}}}&\text{if
}\alpha=2,\\\
\alpha\Gamma(\alpha/2)\left(\frac{2\left(e^{2\epsilon_{0}}-1\right)^{2}}{me^{2\epsilon_{0}}}\right)^{\alpha/2}&\text{otherwise},\end{array}\right.$

which completes the proof of Theorem 6.

##  7 Proof of Theorem 2 (Lower Bound)

Consider the binary case, where each data point $d$ can take a value from
$\mathcal{X}=\\{0,1\\}$. Let the local randomizer $\mathcal{R}$ be the binary
randomized response (2RR) mechanism, where
$\Pr\left[\mathcal{R}\left(d\right)=d\right]=\frac{e^{\epsilon_{0}}}{e^{\epsilon_{0}}+1}$
for $d\in\mathcal{X}$. It is easy to verify that $\mathcal{R}$ is an
$\epsilon_{0}$-LDP mechanism. For simplicity, let
$p=\frac{1}{e^{\epsilon_{0}}+1}$. Consider two neighboring datasets
$\mathcal{D},\ \mathcal{D}^{\prime}\in\\{0,1\\}^{k}$, where
$\mathcal{D}=\left(0,\ldots,0,0\right)$ and
$\mathcal{D}^{\prime}=\left(0,\ldots,0,1\right)$. Let
$m\in\left\\{0,\ldots,k\right\\}$ denote the number of ones in the output of
the shuffler. We define two distributions

$\displaystyle\mu_{0}(m)$ $\displaystyle=\binom{k}{m}p^{m}(1-p)^{k-m},$ (33)
$\displaystyle\mu_{1}(m)$
$\displaystyle=(1-p)\binom{k-1}{m-1}p^{m-1}(1-p)^{k-m}+p\binom{k-1}{m}p^{m}(1-p)^{k-m-1}.$

As argued on page 6, since the output of the shuffled mechanism $\mathcal{M}$
can be thought of as the distribution of the number of ones in the output, we
have that $m\sim\mathcal{M}(\mathcal{D})$ is distributed as a Binomial random
variable Bin$(k,p)$. Thus, we have

$\displaystyle\mathcal{M}(\mathcal{D})(m)$ $\displaystyle=\mu_{0}(m)$
$\displaystyle\mathcal{M}(\mathcal{D}^{\prime})(m)$
$\displaystyle=(1-\gamma)\mu_{1}(m)+\gamma\mu_{0}(m)$

It will be useful to compute $\frac{\mu_{1}(m)}{\mu_{0}(m)}-1$ for the
calculations later.

$\displaystyle\frac{\mu_{1}(m)}{\mu_{0}(m)}-1$
$\displaystyle=\frac{(1-p)\binom{k-1}{m-1}p^{m-1}(1-p)^{k-m}+p\binom{k-1}{m}p^{m}(1-p)^{k-m-1}}{\binom{k}{m}p^{m}(1-p)^{k-m}}-1$
$\displaystyle=\frac{m}{k}\frac{(1-p)}{p}+\frac{(k-m)}{k}\frac{p}{(1-p)}-1$
$\displaystyle=\frac{m}{k}e^{\epsilon_{0}}+\frac{(k-m)}{k}e^{-\epsilon_{0}}-1$
$\displaystyle=\frac{m}{k}\left(e^{\epsilon_{0}}-e^{-\epsilon_{0}}\right)+e^{-\epsilon_{0}}-1$
$\displaystyle=\frac{m}{k}\left(\frac{e^{2\epsilon_{0}}-1}{e^{\epsilon_{0}}}\right)-\left(\frac{e^{\epsilon_{0}}-1}{e^{\epsilon_{0}}}\right)$
$\displaystyle=\left(\frac{e^{2\epsilon_{0}}-1}{ke^{\epsilon_{0}}}\right)\left(m-\frac{k}{e^{\epsilon_{0}}+1}\right)$
(34)

Thus, we have that

$\displaystyle\mathbb{E}_{m\sim\mathcal{M}(\mathcal{D})}$
$\displaystyle\left[\left(\frac{\mathcal{M}(\mathcal{D}^{\prime})(m)}{\mathcal{M}(\mathcal{D})(m)}\right)^{\lambda}\right]=\mathbb{E}\left[\left(1+\gamma\left(\frac{\mu_{1}(m)}{\mu_{0}(m)}-1\right)\right)^{\lambda}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{=}}1+\sum_{i=1}^{\lambda}\binom{\lambda}{i}\gamma^{i}\mathbb{E}\left[\left(\frac{\mu_{1}(m)}{\mu_{0}(m)}-1\right)^{i}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{=}}1+\sum_{i=2}^{\lambda}\binom{\lambda}{i}\gamma^{i}\mathbb{E}\left[\left(\frac{\mu_{1}(m)}{\mu_{0}(m)}-1\right)^{i}\right]$
$\displaystyle=1+\sum_{i=2}^{\lambda}\binom{\lambda}{i}\gamma^{i}\left(\frac{\left(e^{2\epsilon_{0}}-1\right)}{ke^{\epsilon_{0}}}\right)^{i}\mathbb{E}\left[\left(m-\frac{k}{e^{\epsilon_{0}}+1}\right)^{i}\right]$
(from (34))
$\displaystyle\stackrel{{\scriptstyle\text{(c)}}}{{=}}1+\binom{\lambda}{2}\gamma^{2}\frac{\left(e^{\epsilon_{0}}-1\right)^{2}}{ke^{\epsilon_{0}}}+\sum_{i=3}^{\lambda}\binom{\lambda}{i}\gamma^{i}\left(\frac{\left(e^{2\epsilon_{0}}-1\right)}{ke^{\epsilon_{0}}}\right)^{i}\mathbb{E}\left[\left(m-\frac{k}{e^{\epsilon_{0}}+1}\right)^{i}\right].$

Here, step (a) from the polynomial expansion
$(1+x)^{k}=\sum_{m=0}^{k}\binom{k}{m}x^{m}$, step (b) follows because the term
corresponding to $i=1$ is zero (i.e.,
$\mathbb{E}_{m\sim\mu_{0}}\left[\left(\frac{\mu_{1}(m)}{\mu_{0}(m)}-1\right)\right]=0$),
and step (c) from the from the fact that
$\mathbb{E}_{m\sim\mu_{0}}\left[\left(m-\frac{k}{e^{\epsilon_{0}}+1}\right)^{2}\right]=kp(1-p)=\frac{ke^{\epsilon_{0}}}{(e^{\epsilon_{0}}+1)^{2}}$,
which is equal to the variance of the Binomial random variable. This completes
the proof of Theorem 2.

##  8 Proof of Theorem 3: Privacy-Convergence Tradeoff

In this section, we prove the privacy-convergence tradeoff of Algorithm 1 and
prove Theorem 3.

The privacy part is straightforward from conversion from RDP to approximate DP
using Lemma 1 and Theorem 1. Now, we prove the convergence rate.

At iteration $t\in\left[T\right]$ of Algorithm 1, server averages the $k$
received gradients and obtains
$\overline{\mathbf{g}}_{t}=\frac{1}{k}\sum_{i\in\mathcal{U}_{t}}\mathcal{R}_{p}\left(\tilde{\mathbf{g}}_{t}\left(d_{i}\right)\right)$
and then updates the parameter vector as
$\theta_{t+1}\leftarrow\prod_{\mathcal{C}}\left(\theta_{t}-\eta_{t}\overline{\mathbf{g}}_{t}\right)$.
Observe that the mechanism $\mathcal{R}_{p}$ is unbiased and has a bounded
variance:
$\sup_{\mathbf{x}\in\mathcal{B}_{p}\left(L\right)}\mathbb{E}\|\mathcal{R}_{p}\left(\mathbf{x}\right)-\mathbf{x}\|_{2}^{2}\leq
G_{p}^{2}(L)$. As a result, the average gradient $\overline{\mathbf{g}}_{t}$
is also unbiased, i.e., we have
$\mathbb{E}\left[\overline{\mathbf{g}}_{t}\right]=\nabla_{\theta_{t}}F\left(\theta_{t}\right)$,
where expectation is taken with respect to the random subsampling of clients
as well as the randomness of the mechanism $\mathcal{R}_{p}$. Now we show that
$\overline{\mathbf{g}}_{t}$ has a bounded second moment.

######  Lemma 8.

For any $d\in\mathcal{X}$, if the function
$f\left(\theta;.\right):\mathcal{C}\times\mathcal{X}\to\mathbb{R}$ is convex
and $L$-Lipschitz continuous with respect to the $\ell_{g}$-norm, which is the
dual of the $\ell_{p}$-norm (i.e., $\frac{1}{p}+\frac{1}{g}=1$), then we have

$\displaystyle\mathbb{E}\|\overline{\mathbf{g}}_{t}\|_{2}^{2}\leq
L^{2}\max\\{d^{1-\frac{2}{p}},1\\}\left(1+\frac{cd}{qn}\left(\frac{e^{\epsilon_{0}}+1}{e^{\epsilon_{0}}-1}\right)^{2}\right),$
(35)

where $c$ is a global constant: $c=4$ if $p\in\\{1,\infty\\}$ and $c=14$ if
$p\notin\\{1,\infty\\}$.

###### Proof.

Under the conditions of the lemma, we have from [SS+12, Lemma $2.6$] that
$\|\nabla_{\theta}f\left(\theta;d\right)\|\leq L$ for all $d\in\mathcal{X}$,
which implies that $\|\nabla_{\theta}F(\theta)\|\leq L$. Thus, we have

$\displaystyle\mathbb{E}\|\overline{\mathbf{g}}_{t}\|_{2}^{2}=\|\mathbb{E}\left[\overline{\mathbf{g}}_{t}\right]\|_{2}^{2}+\mathbb{E}\|\overline{\mathbf{g}}_{t}-\mathbb{E}\left[\overline{\mathbf{g}}_{t}\right]\|_{2}^{2}$
$\displaystyle\
\stackrel{{\scriptstyle\left(a\right)}}{{\leq}}\max\\{d^{1-\frac{2}{p}},1\\}L^{2}+\mathbb{E}\|\overline{\mathbf{g}}_{t}-\mathbb{E}\left[\overline{\mathbf{g}}_{t}\right]\|_{2}^{2}$
$\displaystyle\
\stackrel{{\scriptstyle\left(b\right)}}{{\leq}}\max\\{d^{1-\frac{2}{p}},1\\}L^{2}+\frac{G_{p}(L)^{2}}{k}$
$\displaystyle\
\stackrel{{\scriptstyle\left(c\right)}}{{=}}\max\\{d^{1-\frac{2}{p}},1\\}L^{2}+\frac{G_{p}^{2}(L)}{\gamma
n},$

Step $\left(a\right)$ follows from the fact that
$\|\nabla_{\theta_{t}}F\left(\theta_{t}\right)\|\leq L$ together with the norm
inequality $\|\boldsymbol{u}\|_{q}\leq\|\boldsymbol{u}\|_{p}\leq
d^{\frac{1}{p}-\frac{1}{q}}\|\boldsymbol{u}\|_{q}$ for $1\leq p\leq
q\leq\infty$. Step $\left(b\right)$ follows from the assumption that
$\mathcal{R}_{p}$ has bounded variance. Step (c) uses $\gamma=\frac{k}{n}$. ∎

Now, we can use standard SGD convergence results for convex functions. In
particular, we use the following result from [SZ13].

######  Lemma 9 (SGD Convergence [SZ13]).

Let $F\left(\theta\right)$ be a convex function, and the set $\mathcal{C}$ has
diameter $D$. Consider a stochastic gradient descent algorithm
$\theta_{t+1}\leftarrow\prod_{\mathcal{C}}\left(\theta_{t}-\eta_{t}\mathbf{g}_{t}\right)$,
where $\mathbf{g}_{t}$ satisfies
$\mathbb{E}\left[\mathbf{g}_{t}\right]=\nabla_{\theta_{t}}F\left(\theta_{t}\right)$
and $\mathbb{E}\|\mathbf{g}_{t}\|_{2}^{2}\leq G^{2}$. By setting
$\eta_{t}=\frac{D}{G\sqrt{t}}$, we get

$\mathbb{E}\left[F\left(\theta_{T}\right)\right]-F\left(\theta^{*}\right)\leq
2DG\frac{2+\log\left(T\right)}{\sqrt{T}}=\mathcal{O}\left(DG\frac{\log\left(T\right)}{\sqrt{T}}\right).$
(36)

As shown in Lemma 8 and above that Algorithm 1 satisfies the premise of Lemma
9. Now, using the bound on $G^{2}$ from Lemma 8, we have that the output
$\theta_{T}$ of Algorithm 1 satisfies

$\displaystyle\mathbb{E}\left[F\left(\theta_{T}\right)\right]-F\left(\theta^{*}\right)\leq\mathcal{O}\left(DG\frac{\log\left(T\right)}{\sqrt{T}}\right),$
(37)

where $G^{2}=\max\\{d^{1-\frac{2}{p}},1\\}L^{2}+\frac{G_{p}^{2}(L)}{\gamma
n}$. This completes the proof of the second part of Theorem 3.

## References

  * [ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [ALC+21] Shahab Asoodeh, Jiachun Liao, Flavio P Calmon, Oliver Kosut, and Lalitha Sankar.  Three variants of differential privacy: Lossless conversion and applications.  IEEE Journal on Selected Areas in Information Theory, 2(1):208–222, 2021.
  * [ASY+18] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan.  cpsgd: Communication-efficient and differentially-private distributed sgd.  In Advances in Neural Information Processing Systems, pages 7564–7575, 2018.
  * [BBG+20] Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato.  Hypothesis testing interpretations and renyi differential privacy.  In Silvia Chiappa and Roberto Calandra, editors, International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 2496–2506. PMLR, 2020\.
  * [BBGN19a] Borja Balle, James Bell, Adria Gascon, and Kobbi Nissim.  Differentially private summation with multi-message shuffling.  arXiv preprint arXiv:1906.09116, 2019.
  * [BBGN19b] Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim.  Improved summation from shuffling.  arXiv preprint arXiv:1909.11225, 2019.
  * [BBGN19c] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim.  The privacy blanket of the shuffle model.  In Annual International Cryptology Conference, pages 638–667. Springer, 2019.
  * [BBGN20] Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim.  Private summation in the multi-message shuffle model.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 657–676, 2020.
  * [BDF+18] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers.  Protection against reconstruction and its applications in private federated learning.  arXiv preprint arXiv:1812.00984, 2018.
  * [Bot10] Léon Bottou.  Large-scale machine learning with stochastic gradient descent.  In Proceedings of COMPSTAT’2010, pages 177–186. Springer, 2010\.
  * [BST14] Raef Bassily, Adam Smith, and Abhradeep 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.
  * [CKS20] Clément L. Canonne, Gautam Kamath, and Thomas Steinke.  The discrete gaussian for differential privacy.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  Journal of Machine Learning Research, 12(3), 2011.
  * [CSU+19] Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev.  Distributed differential privacy via shuffling.  In Advances in Cryptology - EUROCRYPT 2019, volume 11476, pages 375–403. Springer, 2019.
  * [DJW13] John C Duchi, Michael I Jordan, and Martin J Wainwright.  Local privacy and statistical minimax rates.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438. IEEE, 2013.
  * [DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin.  Collecting telemetry data privately.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 3574–3583, Red Hook, NY, USA, 2017. Curran Associates Inc.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography Conference (TCC), pages 265–284, 2006\.
  * [DR14] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Foundations and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014.
  * [DRV10] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan.  Boosting and differential privacy.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010.
  * [EFM+19] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta.  Amplification by shuffling: From local to central differential privacy via anonymity.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468–2479. SIAM, 2019.
  * [EFM+20] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta.  Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation.  CoRR, abs/2001.03618, 2020.
  * [EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054–1067, 2014.
  * [FMT20] Vitaly Feldman, Audra McMillan, and Kunal Talwar.  Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling.  arXiv preprint arXiv:2012.12803, 2020.  Open source implementation of privacy https://github.com/apple/ml-shuffling-amplification.
  * [GDD+21a] Antonious M Girgis, Deepesh Data, Suhas Diggavi, Ananda Theertha Suresh, and Peter Kairouz.  On the renyi differential privacy of the shuffle model.  arXiv preprint arXiv:2105.05180, 2021.
  * [GDD+21b] Antonious M. Girgis, Deepesh Data, Suhas N. Diggavi, Peter Kairouz, and Ananda Theertha Suresh.  Shuffled model of differential privacy in federated learning.  In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS, volume 130 of Proceedings of Machine Learning Research, pages 2521–2529. PMLR, 2021.
  * [GGK+19] Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker.  On the power of multiple anonymous messages.  IACR Cryptol. ePrint Arch., 2019:1382, 2019.
  * [GPV19] Badih Ghazi, Rasmus Pagh, and Ameya Velingker.  Scalable and differentially private distributed aggregation in the shuffled model.  arXiv preprint arXiv:1906.08320, 2019.
  * [Gre16] Andy Greenberg.  Apple’s ‘differential privacy’is about collecting your data—but not your data.  Wired, June, 13, 2016.
  * [KBR16] Peter Kairouz, Keith Bonawitz, and Daniel Ramage.  Discrete distribution estimation under local privacy.  In International Conference on Machine Learning, ICML, pages 2436–2444, 2016.
  * [KLN+11] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826, 2011.
  * [KMA+19] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  arXiv preprint arXiv:1912.04977, 2019.
  * [KMY+16] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  In NIPS Workshop on Private Multi-Party Machine Learning, 2016.
  * [KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  In International conference on machine learning, pages 1376–1385. PMLR, 2015.
  * [Mir17] Ilya Mironov.  Rényi differential privacy.  In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017.
  * [MTZ19] Ilya Mironov, Kunal Talwar, and Li Zhang.  R$\backslash$’enyi differential privacy of the sampled gaussian mechanism.  arXiv preprint arXiv:1908.10530, 2019.
  * [PTS+20] Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson.  Tempered sigmoid activations for deep learning with differential privacy.  arXiv preprint arXiv:2007.14191, 2020.
  * [SS+12] Shai Shalev-Shwartz et al.  Online learning and online convex optimization.  Foundations and Trends® in Machine Learning, 4(2):107–194, 2012.
  * [SZ13] Ohad Shamir and Tong Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  In International conference on machine learning, pages 71–79, 2013\.
  * [Ull17] Jonathan Ullman.  Cs7880. rigorous approaches to data privacy.  2017\.
  * [WBK19] Yu-Xiang Wang, Borja Balle, and Shiva Prasad 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.
  * [YLCT19] Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong.  Federated machine learning: Concept and applications.  ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1–19, 2019.
  * [ZW19] Yuqing Zhu and Yu-Xiang Wang.  Poission subsampled rényi differential privacy.  In International Conference on Machine Learning, pages 7634–7642. PMLR, 2019.

##  Appendix A Literature Review

We give the most relevant work related to the paper and review some of the
main developments in differentially private learning below.

#### Private Optimization:

In [CMS11], Chaudhuri et al. studied _centralized_ privacy-preserving machine
learning algorithms for convex optimization problem. In [BST14], Bassily et
al. derived lower bounds on the empirical risk minimization under _central_
differential privacy constraints. Furthermore, they proposed a differential
privacy SGD algorithm that matches the lower bound for convex functions. In
[ACG+16], the authors have generalized the private SGD algorithm proposed in
[BST14] for non-convex optimization framework. In addition, the authors have
proposed a new analysis technique, called moment accounting, to improve on the
strong composition theorems to compute the central differential privacy
guarantee for iterative algorithms. However, the works mentioned, [CMS11,
BST14, ACG+16], assume that there exists a trusted server that collects the
clients’ data. This motivates other works to design a distributed SGD
algorithms, where each client perturbs her own data without needing a trusted
server.

Distributed learning under local differential privacy (LDP) has studied in
[ASY+18, EFM+20, GDD+21b]. In [ASY+18] the authors proposed a communication-
efficient algorithm for learning models under local differential privacy. In
[EFM+20], the authors have proposed a distributed local-differential-privacy
gradient descent algorithm, a newly proposed anonymization/shuffling framework
[BBGN19c] is used to amplify the privacy. In [GDD+21b], the authors proposed
communication efficient algorithms for general $\ell_{p}$-norm stetting under
local differential privacy constraints, where they use recent results on
amplification by shuffling to boost the privacy-utility trade-offs of the
distributed learning algorithms.

#### Shuffled privacy model:

The shuffled model of privacy has been of significant recent interest [EFM+19,
GGK+19, BBGN19b, GPV19, BBGN19a, CSU+19, BBGN19c, BBGN20]. However, most of
the existing works in literature [EFM+19, BBGN19c, FMT20] only characterize
the approximate DP of the shuffled model. Recently, the authors in [GDD+21a]
proposed a novel bound on the RDP of the shuffled model, where they show that
the RDP provides a significant saving in computing the total privacy budget
for a composition of a sequence of shuffled mechanisms. However, the work
[GDD+21a] does not characterize the RDP of the subsampled shuffle mechanism.
We can compute a bound on the RDP of the subsampled shuffle mechanism by
combining the bound of the RDP of the shuffle mechanism in [GDD+21a] with the
bound of the subsampled RDP mechanism in [WBK19]. However, we show numerically
that our new bound on the subsampled shuffle mechanism outperforms this bound.

#### Renyi differential privacy:

The work of Abadi _et al._ [ACG+16] provided a new analysis technique to
improve on the strong composition theorems. Inherently, this used Renyi
divergence, and was later formalized in [Mir17] which defined Renyi
differential privacy (RDP). Several works [MTZ19, WBK19, ZW19] have shown that
analyzing the RDP of subsampled mechanisms provides a tighter bound on the
total privacy loss than the bound that can be obtained using the standard
strong composition theorems. In this paper, we analyze the RDP of the
subsampled shuffle model, where we can bound the approximate DP of a sequence
of subsampled shuffle models using the transformation from RDP to approximate
DP [ACG+16, WBK19, CKS20, ALC+21]. We show that our RDP analysis provides a
better bound on the total privacy loss of composition than the bound that can
be obtained using the standard strong composition theorems and the bound that
can be obtained by combining the RDP bound of the shuffle model in [GDD+21a]
with the subsampled RDP mechanism in [WBK19].

##  Appendix B Completing the Proof of Theorem 4

For simplicity of notation, for any $m\in\\{0,1,\ldots,n-1\\}$, define

$\displaystyle q_{m}$ $\displaystyle:=\binom{k-1}{m}q^{m}(1-q)^{k-m-1}$
$\displaystyle E_{m}$
$\displaystyle:=\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{(k)})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime(k)})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})(\boldsymbol{h})}\right|^{\alpha}\right].$

First we show an important property of $E_{m}$ that we will use in the proof.

######  Lemma 10.

$E_{m}$ is a non-increasing function of $m$, i.e.,

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{(k)})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m+1}^{\prime\prime(k)})(\boldsymbol{h})}\right|^{\alpha}\right]$
$\displaystyle\hskip
113.81102pt\leq\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}_{m}^{\prime\prime(k)})}\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D}_{m}^{(k)})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}_{m}^{\prime(k)})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}_{m}^{\prime\prime(k)})(\boldsymbol{h})}\right|^{\alpha}\right],$
(38)

where, for any $l\in\\{m,m+1\\}$,
$\mathcal{D}_{l}^{(k)}=(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d_{k})$,
$\mathcal{D}_{l}^{\prime(k)}=(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d^{\prime}_{k})$,
and
$\mathcal{D}_{l}^{\prime\prime(k)}=(d^{\prime\prime}_{k},\ldots,d^{\prime\prime}_{k},d^{\prime\prime}_{k})$,
each having $l$ elements.

###### Proof.

Lemma 10 follows from Lemma 5 in a straightforward manner, as Lemma 5 is for
arbitrary triples of adjacent datasets, whereas, Lemma 10 is for triples of
adjacent datasets having special structures. ∎

Thus, we get

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime})}$
$\displaystyle\left[\left|\frac{\mathcal{M}_{sh}(\mathcal{D})(\boldsymbol{h})-\mathcal{M}_{sh}(\mathcal{D}^{\prime})(\boldsymbol{h})}{\mathcal{M}_{sh}(\mathcal{D}^{\prime\prime})(\boldsymbol{h})}\right|^{\alpha}\right]$
$\displaystyle\hskip 85.35826pt\leq\sum_{m=0}^{k-1}q_{m}E_{m}$
$\displaystyle\hskip
85.35826pt=\sum_{m<\lfloor(1-\gamma)q(k-1)\rfloor}q_{m}E_{m}+\sum_{m\geq\lfloor(1-\gamma)q(k-1)\rfloor}q_{m}E_{m}$
$\displaystyle\hskip
85.35826pt\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}E_{0}\sum_{m<\lfloor(1-\gamma)q(k-1)\rfloor}q_{m}+\sum_{m\geq\lfloor(1-\gamma)q(k-1)\rfloor}q_{m}E_{m}$
$\displaystyle\hskip
85.35826pt\stackrel{{\scriptstyle\text{(b)}}}{{\leq}}E_{0}e^{-\frac{q(k-1)\gamma^{2}}{2}}+\sum_{m\geq\lfloor(1-\gamma)q(k-1)\rfloor}q_{m}E_{m}$
$\displaystyle\hskip
85.35826pt\stackrel{{\scriptstyle\text{(c)}}}{{\leq}}e^{\epsilon_{0}\alpha}e^{-\frac{q(k-1)\gamma^{2}}{2}}+\sum_{m\geq\lfloor(1-\gamma)q(k-1)\rfloor}q_{m}E_{m}$
$\displaystyle\hskip
85.35826pt\stackrel{{\scriptstyle\text{(d)}}}{{\leq}}(e^{\epsilon_{0}}-e^{-\epsilon_{0}})^{\alpha}e^{-\frac{q(k-1)\gamma^{2}}{2}}+E_{(1-\gamma)q(k-1)}.$
(39)

Here, steps (a) and (d) follow from the fact that $E_{m}$ is a non-increasing
function of $m$ (see Lemma 10). Step (b) follows from the Chernoff bound. In
step (c), we used that $\mathcal{M}_{sh}(d_{k})=\mathcal{R}(d_{k})$,
$\mathcal{M}_{sh}(d^{\prime}_{k})=\mathcal{R}(d^{\prime}_{k})$, and
$\mathcal{M}_{sh}(d^{\prime\prime}_{k})=\mathcal{R}(d^{\prime\prime}_{k})$
which together imply that
$E_{0}=(e^{\epsilon_{0}}-e^{-\epsilon_{0}})^{\alpha}$, where the inequality
follows because $\mathcal{R}$ is an $\epsilon_{0}$-LDP mechanism. By choosing
$\gamma=0.5$ completes the proof of Theorem 4.

##  Appendix C Proof of Lemma 2

Consider arbitrary neighboring datasets
$\mathcal{D}=\left(d_{1},\ldots,d_{n}\right)\in\mathcal{X}^{n}$ and
$\mathcal{D}^{\prime}=\left(d_{1},\ldots,d_{n-1},d_{n}^{\prime}\right)\in\mathcal{X}^{n}$.
Recall that the LDP mechanism $\mathcal{R}:\mathcal{X}\to\mathcal{Y}$ has a
discrete range $\mathcal{Y}=\left[B\right]$ for some $B\in\mathbb{N}$. Let
$\boldsymbol{p}_{i}:=(p_{i1},\ldots,p_{iB})$ and
$\boldsymbol{p}^{\prime}_{n}:=(p^{\prime}_{n1},\ldots,p^{\prime}_{nB})$ denote
the probability distributions over $\mathcal{Y}$ when the input to
$\mathcal{R}$ is $d_{i}$ and $d^{\prime}_{n}$, respectively, where
$p_{ij}=\Pr[\mathcal{R}(d_{i})=j]$ and
$p_{nj}^{\prime}=\Pr[\mathcal{R}(d^{\prime}_{n})=j]$ for all $j\in[B]$ and
$i\in\left[n\right]$.

Let $\mathcal{P}=\\{\boldsymbol{p}_{i}:i\in\left[n\right]\\}$ and
$\mathcal{P}^{\prime}=\\{\boldsymbol{p}_{i}:i\in\left[n-1\right]\\}\bigcup\\{\boldsymbol{p}^{\prime}_{n}\\}$.
For $i\in[n-1]$, let
$\mathcal{P}_{-i}=\mathcal{P}\setminus\\{\boldsymbol{p}_{i}\\}$,
$\mathcal{P}^{\prime}_{-i}=\mathcal{P}^{\prime}\setminus\\{\boldsymbol{p}_{i}\\}$,
and also $\mathcal{P}_{-n}=\mathcal{P}\setminus\\{\boldsymbol{p}_{n}\\}$,
$\mathcal{P}^{\prime}_{-n}=\mathcal{P}^{\prime}\setminus\\{\boldsymbol{p}_{n}^{\prime}\\}$.

Here, $\mathcal{P},\mathcal{P}^{\prime}$ correspond to the datasets
$\mathcal{D}=\\{d_{1},\ldots,d_{n}\\},\mathcal{D}^{\prime}=\\{d_{1},\ldots,d_{n-1},d^{\prime}_{n}\\}$,
respectively, and for any $i\in[n]$, $\mathcal{P}_{-i}$ and
$\mathcal{P}^{\prime}_{-i}$ correspond to the datasets
$\mathcal{D}_{-i}=\\{d_{1},\ldots,d_{i-1},d_{i+1},\ldots,d_{n}\\}$ and
$\mathcal{D}^{\prime}_{-i}=\\{d_{1},\ldots,d_{i-1},d_{i+1},\ldots,d_{n-1},d^{\prime}_{n}\\}$,
respectively. Thus, without loss of generality, we deal with sets
$\mathcal{P}$ and $\mathcal{P}^{\prime}$ throughout this section instead of
dealing with $\mathcal{D}$ and $\mathcal{D}^{\prime}$. Thus, we write
$\mathcal{M}\left(\mathcal{P}\right)\triangleq\mathcal{M}\left(\mathcal{D}\right)$
and
$\mathcal{M}\left(\mathcal{P}^{\prime}\right)\triangleq\mathcal{M}\left(\mathcal{D}^{\prime}\right)$.

We bound the Renyi divergence between $\mathcal{M}(\mathcal{P})$ and
$\mathcal{M}(\mathcal{P}^{\prime})$. For given a set $\mathcal{S}\subset[n]$
with $|\mathcal{S}|=\gamma n=k$, we define two sets
$\mathcal{P}^{\mathcal{S}},\mathcal{P}^{{}^{\prime}\mathcal{S}}$, having $k$
distributions each, as follows:

$\displaystyle\mathcal{P}^{\mathcal{S}}$
$\displaystyle=\\{\boldsymbol{p}_{i}:i\in\mathcal{S}\\},$ (40)
$\displaystyle\mathcal{P}^{{}^{\prime}\mathcal{S}}$
$\displaystyle=\\{\boldsymbol{p}_{i}:i\in\mathcal{S}\\},$ (41)

Observe that when $n\not\in\mathcal{S}$, we have that
$\mathcal{P}^{\mathcal{S}}=\mathcal{P}^{{}^{\prime}\mathcal{S}}$. For given
$k$ distributions
$\mathcal{P}=\left(\boldsymbol{p}_{1},\ldots,\boldsymbol{p}_{k}\right)$, we
define a shuffle mechanism $\mathcal{M}_{sh}\left(\mathcal{P}\right)$ as
follows:

$\mathcal{M}_{sh}\left(\mathcal{P}\right)=\mathcal{H}_{k}\left(\boldsymbol{p}_{1},\ldots,\boldsymbol{p}_{k}\right).$
(42)

Thus, the mechanisms $\mathcal{M}(\mathcal{P})$ and
$\mathcal{M}(\mathcal{P}^{\prime})$ can be defined by:

$\displaystyle\mathcal{M}(\mathcal{P})$
$\displaystyle=\frac{1}{\binom{n}{k}}\sum_{\mathcal{S}\subset[n]}\mathcal{M}_{sh}\left(\mathcal{P}^{\mathcal{S}}\right)$
$\displaystyle=\gamma P_{E}+(1-\gamma)P_{E^{c}}$ (43)
$\displaystyle\mathcal{M}(\mathcal{P}^{\prime})$
$\displaystyle=\frac{1}{\binom{n}{k}}\sum_{\mathcal{S}\subset[n]}\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}}\right)$
$\displaystyle=\gamma Q_{E}+(1-\gamma)P_{E^{c}},$ (44)

where
$P_{E}=\frac{1}{\binom{n-1}{k-1}}\sum_{\begin{subarray}{c}\mathcal{S}\subset[n]\\\
n\in\mathcal{S}\end{subarray}}\mathcal{M}_{sh}\left(\mathcal{P}^{\mathcal{S}}\right)$,
$P_{E^{c}}=\frac{1}{\binom{n-1}{k}}\sum_{\begin{subarray}{c}\mathcal{S}\subset[n]\\\
n\not\in\mathcal{S}\end{subarray}}\mathcal{M}_{sh}\left(\mathcal{P}^{\mathcal{S}}\right)$,
and
$Q_{E}=\frac{1}{\binom{n-1}{k-1}}\sum_{\begin{subarray}{c}\mathcal{S}\subset[n]\\\
n\in\mathcal{S}\end{subarray}}\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}}\right)$.
Hence, from the polynomial expansion, we get:

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}\left(\mathcal{P}^{\prime}\right)}\left[\left(\frac{\mathcal{M}\left(\mathcal{P}\right)\left(\boldsymbol{h}\right)}{\mathcal{M}\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)}\right)^{\lambda}\right]$
$\displaystyle=\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}\left(\mathcal{P}^{\prime}\right)}\left[\left(1+\frac{\mathcal{M}\left(\mathcal{P}\right)\left(\boldsymbol{h}\right)}{\mathcal{M}\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)}-1\right)^{\lambda}\right]$
(45)
$\displaystyle=1+\sum_{j=2}^{\lambda}\binom{\lambda}{j}\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}\left(\mathcal{P}^{\prime}\right)}\left[\left(\frac{\mathcal{M}\left(\mathcal{P}\right)\left(\boldsymbol{h}\right)-\mathcal{M}\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)}{\mathcal{M}\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)}\right)^{j}\right]$
$\displaystyle=1+\sum_{j=2}^{\lambda}\binom{\lambda}{j}\gamma^{j}\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}\left(\mathcal{P}^{\prime}\right)}\left[\left(\frac{P_{E}\left(\boldsymbol{h}\right)-Q_{E}\left(\boldsymbol{h}\right)}{\mathcal{M}\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)}\right)^{j}\right]~{}$

Now, we borrow the trick used in [WBK19] to bound each term in the right hand
side in (45). For completeness, we repeat their definitions and proofs here.
We define an auxiliary dummy variable
$i\sim\text{Unif}\left(1,\ldots,k\right)$ that is independent to everything
else. Furthermore, we define two functions $g(\mathcal{S},i)$ and
$g^{\prime}(\mathcal{S},i)$ as follows:

$\displaystyle
g(\mathcal{S},i)=\left\\{\begin{array}[]{ll}\mathcal{M}_{sh}\left(\mathcal{P}^{\mathcal{S}}\right)&\text{if}\
n\in\mathcal{S}\\\
\mathcal{M}_{sh}\left(\mathcal{P}^{\mathcal{S}\cup\\{n\\}\setminus\mathcal{S}(i)}\right)&\text{otherwise}\end{array}\right.$
(48) $\displaystyle
g^{\prime}(\mathcal{S},i)=\left\\{\begin{array}[]{ll}\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}}\right)&\text{if}\
n\in\mathcal{S}\\\
\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}\cup\\{n\\}\setminus\mathcal{S}(i)}\right)&\text{otherwise}\end{array}\right.$
(51)

Observe that $\mathbb{E}_{\mathcal{S},i}\left[g(\mathcal{S},i)\right]=P_{E}$,
$\mathbb{E}_{\mathcal{S},i}\left[g^{\prime}(\mathcal{S},i)\right]=Q_{E}$, and
$\mathbb{E}_{\mathcal{S},i}\left[\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}}\right)\right]=\mathcal{M}\left(\mathcal{P}\right)$.
As a result, we get that

$\displaystyle\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}\left(\mathcal{P}^{\prime}\right)}\left[\left(\frac{P_{E}\left(\boldsymbol{h}\right)-Q_{E}\left(\boldsymbol{h}\right)}{\mathcal{M}\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)}\right)^{j}\right]$
$\displaystyle\leq\sum_{\boldsymbol{h}}\frac{|P_{E}\left(\boldsymbol{h}\right)-Q_{E}\left(\boldsymbol{h}\right)|^{j}}{\left(\mathcal{M}\left(\mathcal{P}^{\prime}\right)\left(\boldsymbol{h}\right)\right)^{j-1}}$
$\displaystyle\leq\sum_{\boldsymbol{h}}\mathbb{E}_{\mathcal{S},i}\left[\frac{|g(\mathcal{S},i)\left(\boldsymbol{h}\right)-g^{\prime}(\mathcal{S},i)\left(\boldsymbol{h}\right)|^{j}}{\left(\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}}\right)\left(\boldsymbol{h}\right)\right)^{j-1}}\right]$
$\displaystyle=\mathbb{E}_{\mathcal{S},i}\mathbb{E}_{\boldsymbol{h}\sim\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}}\right)}\left[\left(\frac{|g(\mathcal{S},i)\left(\boldsymbol{h}\right)-g^{\prime}(\mathcal{S},i)\left(\boldsymbol{h}\right)|}{\mathcal{M}_{sh}\left(\mathcal{P}^{{}^{\prime}\mathcal{S}}\right)\left(\boldsymbol{h}\right)}\right)^{j}\right]$
$\displaystyle\leq(\zeta(j))^{j}.$

Here, step (a) follows from Jensen’s inequality and the convexity of the
function $x^{j}/y^{j-1}$ (see [WBK19, Lemma $20$]). Step (b) follows from
Fubini’s theorem. The last inequality is obtained by taking the supremum over
all possible neighboring datasets $\mathcal{D}$, $\mathcal{D}^{\prime}$. This
completes the proof of Lemma 2.