# Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
## 6 Privacy Loss Distribution of Generalized Dominating Pairs
By applying [PERSON]'s inequality to both \(C\) and \(A\), we focus on subsets \(S_{n}\) and \(\widehat{S}_{c}\) containing most of the mass, reducing the terms to \(\mathcal{O}(n\log(1/\tau))\), where \(\tau\) is a small tolerance. Theorem 2: _Given a dominating pair \(P^{\prime,n}_{p,\beta}\), \(\mathcal{C}^{\prime,n}_{p,\beta}\) (shorted as \(P\), \(\mathcal{O}\)), \(\tau\in(0,1]\) and define the set_  
\[S_{n}=\bigg{[}\max\bigg{(}0,(\frac{2\beta p}{(p-1)q}-v_{n})(n-1-m)\bigg{)},\, \min\bigg{(}n-1,(\frac{2\beta p}{(p-1)q}+v_{n})(n-1-m)\bigg{)}\bigg{]},\]  
_where \(v_{n}=\sqrt{\frac{\log(4/\tau)}{2(n-1)}}\). For each \(c\in S_{n}\), define_  
\[S_{c}=[\max(0,(t-\widehat{v}_{c})c),\,\min(c,(t+\widehat{v}_{c})c)],\]  
_with \(\widehat{v}_{c}=\sqrt{\frac{\log(4/\tau)}{2c}}\). Then, the approximated PLD \(\widetilde{\omega}_{P/Q}\) defined by_  
\[\widetilde{\omega}_{P/Q}(u)=\sum_{c\in S_{n}}\sum_{a\in S_{c}}\mathbb{P}(P=(a+ \Delta_{1},c-a+\Delta_{2}))\cdot\delta_{s_{a,b}}(u), \tag{7}\]  
_where \(s_{a,b}=\log(R_{a,b})=\log(\frac{\mathbb{P}[P^{\prime,n}_{p,\beta}=(a,b)]}{ \mathbb{P}[(Q^{\prime,n}_{p,\beta}=(a,b)]})\), differs from the true PLD \(\omega_{P/Q}\) by at most mass \(\tau\) and contains \(\mathcal{O}(n\log(1/\tau))\) terms._  
Proof. : We apply [PERSON]'s inequality to the binomial random variable \(C\sim\text{Binomial}(n-1,\frac{2\beta p}{(p-1)q})\). For any \(v>0\), the inequality provides the following bounds:  
\[\mathbb{P}\bigg{(}C\leq m+(\frac{2\beta p}{(p-1)q}-v)(n-1)\bigg{)}\leq\exp \Big{(}-2(n-1)v^{2}\Big{)},\]  
\[\mathbb{P}\bigg{(}C\geq(\frac{2\beta p}{(p-1)q}+v)(n-1)\bigg{)}\leq\exp\Big{(} -2(n-1)v^{2}\Big{)}.\]To ensure that the total probability does not exceed \(\tau/2\), we impose the condition: \(2\exp\bigl{(}-2(n-1)v^{2}\bigr{)}\leq\frac{\tau}{2}\). Solving for \(v\), we obtain  
\[= \frac{n-a-b}{2a}\cdot\frac{s}{1-s},\]0  
This yields expressions for \(v_{n}\) and \(S_{n}\). Similarly, we apply [PERSON]'s inequality to \(A\sim\mathrm{Binomial}(C,1/2)\) to derive expressions for \(\widehat{v}_{i}\) and \(\widehat{S}_{i}\). The total neglected mass is bounded by \(\tau/2+\tau/2=\tau\). Next, we estimate the number of terms in \(S_{n}\). The set \(S_{n}\) contains at most \(2v_{n}(n-1)=\sqrt{n-1}\cdot\sqrt{2\log(4/\tau)}\) terms. For each \(i\), the set \(\widehat{S}_{i}\) contains at most  
\[= \frac{n-a-b}{2a}\cdot\frac{s}{1-s},\]1  
terms. Hence, the number of terms in \(\widetilde{\omega}_{P/Q}\) is at most \(\mathcal{O}(n\log(4/\tau))\). Finally, we derive the conclusion by performing the change of variables \(a=j+1\) and \(b=i-j\). In practice, when computing the PLD of \((p^{q,n}_{p,\beta},Q^{q,n}_{p,\beta})\), we finitely grid the domain of the PLD (i.e., the values of \(u\)) and ensure the neglected mass is below a prescribed tolerance \(\tau\) (e.g., \(\tau=2^{-30}\)) and add it to \(\delta_{P/Q}(\infty)\). The overall procedure is summarized in Algorithm 1. This approximation significantly reduces computational complexity, and when composing privacy losses, the FFT computation in Lemma 2--dependent only on the number \(n_{u}\) of grid points--becomes the dominant factor. **Comparison with existing accounting approaches. ** Several works employ the Renyi differential privacy for composition, such as in [8]. However, the Renyi differential privacy is far from tight for the random noises in the shuffle model. The work of [13] proposes numerical composition for LDP randomizers in the shuffle model, though it is applicable to only single-message protocols (corresponding to \(q\equiv p\) and \(\beta\equiv(p-1)/(p+1)\) in our dominating pair). Commonly used local randomizers (e.g., the vector binary randomized response in [19], see Theorem 1) often have much lower values of total variation bound \(\beta\). Moreover, the single-message protocols are known to have limited utility [12] for common statistical queries (e.g., histogram estimation, numerical vector aggregation), when compared to multi-message shuffle protocols (e.g., in [14; 16]).