# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 3 Preliminaries
### Privacy Loss Variables for Sequential Composition  
This part retrospects instrumental tools (i.e., dominating pairs, privacy loss variables [26]) for numerical privacy composition, which aims to tightly derive the overall privacy guarantees of multiple sequential invokes of DP mechanisms.  
**Dominating pair [11].** We call variables \((P,Q)\) as the dominating pair of a mechanism \(\mathcal{M}:\mathbb{X}^{n}\mapsto\mathbb{R}^{*}\) if for any distance measure \(D\) that satisfies the data processing inequality, \(D(\mathcal{M}(X)\|\mathcal{M}(X^{\prime}))\leq D(P\|Q)\) holds for any neighboring datasets \(X,X^{\prime}\in\mathbb{X}^{n}\).  
The notion of _privacy loss random variables_ (PRVs) is a unique way to assign a pair \((X,Y)\) for a dominating pair such that \(D(P\|Q)=D(X\|Y)\). PRVs allow us to compute the composition of two or more mechanisms via summing random variables (see Lemma 1). Equivalently, convolving their distributions via Fourier transformation (see Lemma 2 from [11; 13]). Thus, PRVs can be thought of as a _reparametrization of Hockey-stick divergence curves_ where composition becomes convolution.  
Let \(\overline{\mathbb{R}}=\mathbb{R}\cup\{-\infty,\infty\}\) be the extended real line where we define \(\infty+x=\infty\) and \(-\infty+x=-\infty\) for \(x\in\mathbb{R}\).  
**Definition 6** (Privacy loss random variables (PRVs) [26]).: _Given a dominating pair \((P,Q)\), we say that \((X,Y)\) are privacy loss random variables for \((P,Q)\), if they satisfy the following conditions:_  
* \(X,Y\) _are supported on_ \(\overline{\mathbb{R}}\)_,_
* \(D_{e^{c}}(X\|Y)\equiv D_{e^{c}}(P\|Q)\) _for all_ \(\epsilon\in\mathbb{R}\)_,_
* \(Y(t)=e^{t}X(t)\) _for every_ \(t\in\mathbb{R}\) _and_
* \(Y(-\infty)=0\) _and_ \(X(\infty)=0\)_,_  
_where \(X(t),Y(t)\) are probability density functions of \(X,Y\), respectively._  
We analyze discrete-valued distributions, which means that a dominating pair of distributions \((P,Q)\) can be described by generalized probability mass functions as  
\[\begin{split} P(v)&=\sum_{c}\mathbb{P}[P=z]\cdot \delta_{z}(v),\\ Q(v)&=\sum_{c}\mathbb{P}[Q=z]\cdot\delta_{z}(v), \end{split} \tag{1}\]  
where \(z,v\in\mathbb{R}^{*}\), and \(\delta_{z}(\cdot)\) denotes the Dirac delta function centered at \(z\), and \(\mathbb{P}[P=z],\mathbb{P}[Q=z]\geq 0\) denotes the probability masses at \(z\) of \(P\) and \(Q\), respectively. The PLD determined by a dominating pair \((P,Q)\) is defined as follows:  
**Definition 7** (Pld).: _Let \(P\) and \(Q\) be generalized probability mass functions as defined by (1). We define the generalized privacy loss distribution (PLD) \(\omega_{P/Q}\) as:_  
\[\omega_{P/Q}(u)=\sum_{z\in\overline{\mathbb{R}}}\mathbb{P}[P=z]\cdot\delta s _{z}(u),\]  
_where \(s_{z}=\log\Bigl{(}\frac{\mathbb{P}[P=z]}{\mathbb{P}[Q=z]}\Bigr{)}\)._  
**Lemma 1** (Composite PRVs [27]).: _Let \((P_{1},Q_{1}),(P_{2},Q_{2})\) be two dominating pairs with PRVs \((X_{1},Y_{1})\) and \((X_{2},Y_{2})\), respectively. Then the PRVs for the joint dominating pair \(((P_{1},P_{2}),(Q_{1},Q_{2}))\) are given by \((X_{1}+X_{2},Y_{1}+Y_{2})\). In particular,_  
\[D_{e^{c}}(P_{1},P_{2}\|Q_{1},Q_{2})=D_{e^{c}}(X_{1}+X_{2}\|Y_{1}+Y_{2})\]  
_holds for all \(\epsilon\in\mathbb{R}\)._  
**Lemma 2** (Composition via Convolution [11; 13]).: _Consider a \(K\)-fold adaptive composition with corresponding dominating pairs \((P_{1},Q_{2}),\ldots,(P_{K},Q_{K})\), then for \(\epsilon>0\):_  
\[\begin{split}& D_{\epsilon^{c}}(P_{1},\ldots,P_{K}\|Q_{1},\ldots,Q_ {K})\\ \leq& 1-\Pi_{k\in[K]}\big{(}1-\omega_{P_{k}/Q_{k}}( \infty)\big{)}+\int_{\epsilon}^{\infty}(1-\epsilon^{\epsilon-s})\big{(}\omega_ {P_{1}/Q_{1}}*\ldots*\omega_{P_{K}/Q_{K}}\big{)}(s)\,\mathrm{d}s,\end{split} \tag{2}\]  
_where \(\omega_{P/Q}(\infty)=\sum_{[z:\,P(Q=z)=0]}\mathbb{P}(P=z)\), and \(\omega_{P_{k}/Q_{k}}*\omega_{P_{k}/Q_{k}}\) denotes the convolution of the generalized mass functions._