Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling

Introduction

We consider privacy-preserving data analysis in the local model of differential privacy augmented with a shuffler. In this model, each user sends a locally differentially private report and these reports are then anonymized and randomly shuffled. Systems based on this model were first proposed in [BEMMRLRKTS17]. The authors of [EFMRTT19] showed that random shuffling of inputs to locally private protocols amplifies the privacy guarantee. Thus, when the collection of anonymized reports is viewed in the central model, the privacy guarantees are substantially stronger than the original local privacy guarantees. A similar result was shown for the binary randomized response by \AtNextCite\AtEachCitekey\@nocounterrmaxnames [CSUZZ19] who also formalized a related shuffle model of privacy.

The analysis in [EFMRTT19] relies on a more general result referred to as privacy amplification by shuffling. This result shows that privacy is amplified when the inputs are shuffled before applying local randomizers and holds even when local randomizers are chosen sequentially and adaptively. Allowing adaptive choice of local randomizers is necessary for analyzing iterative optimization algorithms such as stochastic gradient descent.

In this paper we give a new analysis of privacy amplification by shuffling. Specifically, we show that running an adaptive sequence of arbitrary ${\varepsilon}_{0}$-DP local randomizers on a uniformly random permutation of $n$ data items, yields an $({\varepsilon},\delta)$-DP algorithm, where

When ${\varepsilon}_{0}>1$, this improves the dependence on ${\varepsilon}_{0}$ from $e^{2.5{\varepsilon}_{0}}$ to asymptotically correct dependence of $e^{{\varepsilon}_{0}/2}$ which was previously known only for the binary randomized response [CSUZZ19]. The bound matches the existing bounds in the regime when ${\varepsilon}_{0}<1$ and is asymptotically optimal in both regimes. We then extend this analysis to approximately differentially private local randomizers with essentially the same guarantees. The best previous guarantee in this case has dependence of $e^{20{\varepsilon}_{0}}$ given in [BKMTT20].

Importantly, our proof is also simpler than the rather delicate approaches in prior work [EFMRTT19, BBGN19]. The proof reduces the problem of analyzing the shuffling privacy guarantee of an adaptive series of local algorithms to analyzing the shuffling privacy guarantee of a simple non-adaptive local algorithm with three outputs. Intuitively, we argue that for any local randomizer $\mathcal{A}$ and two data points $x,y$, $\mathcal{A}(y)$ can be seen as sampling from the same distribution as $\mathcal{A}(x)$ with some positive probability. That is, each data point can create a clone of the output of $\mathcal{A}(x)$ with some probability. For the ${\varepsilon}_{0}>1$ regime, the desired privacy guarantees then follow easily from the number of clones that $x$ has to hide among being distributed as a binomial random variable. In the small ${\varepsilon}_{0}$-regime we also rely on the fact that a local randomizer on two inputs can be seen as the composition of binary randomized response with a post-processing step [KOV16]. Another important property of our proof is that it provides a simple and efficient method for numerically computing an amplification bound that is tighter than our closed-form bounds The resulting code is available at https://github.com/apple/ml-shuffling-amplification.. Specifically, we show that it is sufficient to analyze the appropriate notion of divergence between two specific distributions over 3 values. As in the case of binary randomised response, the constant 1/2 in the exponent arises naturally from analysing the divergence between binomial distributions. In Section 6 we show that this approach leads to numerical bounds that significantly improve on the state of the art. Our approach can be similarly used to numerically compute the privacy amplification guarantee in terms of other notions of privacy. In particular, we use it to compute the privacy amplification guarantee in terms of Rényi differential privacy. As we demonstrate in Section 6.1, this results in tighter privacy guarantees when composing shuffled mechanisms.

Our proof extends naturally to approximate differential privacy. The extension to approximate DP involves an additional technical lemma (Lemma 3.7) that states that any deletion (as opposed to replacement) $({\varepsilon}_{0},\delta_{0})$-DP local randomizer $\mathcal{A}$ can be converted to a deletion ${\varepsilon}_{0}$-DP local randomizer $\mathcal{A}^{\prime}$ such that ${\rm TV}(\mathcal{A}(x),\mathcal{A}^{\prime}(x))\leq\delta_{0}$ for all $x$.

Our privacy amplification result with the optimal dependence on ${\varepsilon}_{0}$ has some surprising consequences. In certain important settings, it allows us to take existing and existing LDP and immediately obtain an algorithm that achieves (nearly) optimal trade-offs between privacy and utility simultaneously in the central and the local models of privacy. While the local ${\varepsilon}_{0}$ may sometimes be large (we’ll often need ${\varepsilon}_{0}$ to grow logarithmically with $n$ to achieve a desired constant central ${\varepsilon}$ guarantee), it provides an additional layer of protection that does not exist in the central model. Moreover, this shuffling result implies that a secure implementation of shuffling, or any function that is a post-processing of shuffling (e.g. vector summation), suffices to ensure the strong central privacy guarantee without having to assume a trusted curator. This is a considerably simpler task than using secure multiparty computation for computing the output of the central DP algorithm [DKMMN06]. Additionally, the fact that the privacy depends only on the LDP property of the local randomizer, and not on the specific noise distribution, allows us to do arbitrary post-processing (e.g. rounding, lossy compression) to the LDP responses before they are shuffled. The privacy of the aggregate relies only on the shuffling result, and we do not need to analyze the effect of the rounding/truncation as in several previous works that use distributed noise addition for a similar goal.

In Section 5.1, we show an example of such an application for the problem of building a histogram (or estimating the frequency distribution) over an alphabet of size $k$. For a given level of accuracy, this algorithm simultaneously achieves nearly optimal central as well as local differential privacy bounds. The algorithm is based on applying our results to the algorithm from [ASZ19] and has low communication and server-side decoding time. We remark that getting the correct bound here requires taking ${\varepsilon}_{0}$ up to $\ln k$. Thus using the $e^{{\varepsilon}_{0}}/\sqrt{n}$ amplification bound from [BBGN19] would give a result that is off by a factor of $\sqrt{k}$ in terms of the central privacy-utility tradeoff. In particular, the correct dependence on ${\varepsilon}_{0}$ in the exponent is crucial to get this bound.

A second example in Section 5.2 relies on the fact the our results holds for an adaptive sequence of local queries. We analyze the privacy of noisy stochastic gradient descent when run on a random permutation of the data. This bridges a disconnect between the prior theoretical analyses that assumed random sampling with replacement, and the practical implementations that use permutations.

Finally, we give an alternative analysis of privacy amplification by shuffling that can be tighter for specific LDP randomizers. In particular, we can use this to give a tighter analysis of $k$-ary randomized response. A closed form amplification bound tailored to $k$-ary randomised response was also given in [BBGN19]. Their bound matches the bound presented in this work when $k=O(e^{{\varepsilon}_{0}})$ and ${\varepsilon}_{0}>1$, but is worse than our bound when $k=\Omega(e^{{\varepsilon}_{0}})$. To the best of our knowledge, the bound presented in this work is the first closed form result that shows that the privacy amplification, for a fixed ${\varepsilon}_{0}$, improves with $k$. This corroborates empirical results from [BBGN19].

A natural direction for future work is to analyze privacy amplification by shuffling in terms of other notions of differential privacy, such as Rényi differential privacy (RDP) [Mir17]. RDP guarantees are particularly useful in multi-step algorithms where the composition properties of differential privacy need to be used. A bound on RDP guarantees is implied by the proof technique in [EFMRTT19] but, just as in the case of approximate DP, this bound is asymptotically suboptimal when ${\varepsilon}_{0}>1$. Specifically, for sufficiently small order $\alpha$, the $\alpha$-RDP divergence is $O(\alpha e^{6{\varepsilon}_{0}})$ in this regime.

Subsequent work of [GDDSK21], (implicitly) relies on the idea proposed in this work: it views each data point as creating a clone of the first element of the first dataset (in the given pair of datasets) and thereby reduces the problem to analysis of divergence between a pair of datasets that have just two different elements. The divergence is then analyzed using both analytic and numerical tools. Their resulting bound on the order $\alpha$ RDP is $O(\alpha e^{2{\varepsilon}_{0}})$ (when ${\varepsilon}_{0}>1$). This is a significant improvement on the results in [EFMRTT19] but is still asymptotically suboptimal.

In Section 6.1 we evaluate numerically the Rényi divergence between the pair of distributions given in our reduction and demonstrate that our approach leads to significantly better bounds The numerical evaluation has not been included in the earlier version of this work and thus not available to the authors of [GDDSK21].. We leave the computation of a closed-form bound on the Rényi divergence between the pair of distributions over three values that emerge from our reduction for future work.

Another subsequent work [KHH21] motivated by the problem of obtaining better guarantees for the composition of multiple shuffled protocols relies on a different approach to composition referred to as Fourier accountant [KJH20]. The approach requires computation of the Fast Fourier Transform of the entire privacy loss variable and [KHH21] use the pair of distributions given in our work as the input to their analysis.

Background and Preliminaries

Differential privacy (DP) is a measure of stability of a randomized algorithm. It bounds the change in the distribution on the outputs when one of the inputs is replaced with an arbitrary other element. The most common way to measure the change in the output distribution is $({\varepsilon},\delta)$-indistinguishability. Two random variables $P$ and $Q$ over some probability space are $({\varepsilon},\delta)$-indistinguishable if for all events $E$ over that probability space,

The following hockey-stick divergence can be used to characterize $({\varepsilon},\delta)$-indistinguishability:

where we use the notation $P$ and $Q$ to refer to both the random variables and their probability density functions. So $P$ and $Q$ are $({\varepsilon},\delta)$-indistinguishable if $\max\{D_{e^{{\varepsilon}}}(P\|Q),D_{e^{{\varepsilon}}}(Q\|P)\}\leq\delta$. We will rely on several standard properties of the hockey-stick divergence such as convexity and preservation under post-processing [DR14].

We will consider several models of differentially private data analysis. In the central model, introduced in [DMNS06], the data of the individuals is held by the curator. The curator is then trusted to perform data analysis whose output does not disclose too much about any particular individual’s data. While this model requires a higher level of trust than the local model, it is possible to design significantly more accurate algorithms. We say that two databases are neighboring if they differ on the data of a single individual.

An algorithm $\mathcal{A}:\mathcal{D}^{n}\to\mathcal{S}$ is $({\varepsilon},\delta)$-differentially private if for all neighboring databases $X$ and $X^{\prime}$, $\mathcal{A}(X)$ and $\mathcal{A}(X^{\prime})$ are $({\varepsilon},\delta)$-indistinguishable.

In the local model, formally introduced in [KLNRS08], each individual (or client) randomizes their data before sending it to data curator (or server). This means that individuals are not required to trust the curator. Due to this minimal trust model, most current industrial deployments of differential privacy rely on local differential privacy [EPK14, App17, DKY17, EFMRSTT20]. More formally, in the general model of local DP clients holding their data can communicate with the server in an arbitrary order with multiple rounds of interaction. The protocol is said to satisfy local $({\varepsilon},\delta)$-differential privacy if the transcripts of the protocol on any pair of neighboring datasets are $({\varepsilon},\delta)$-indistinguishable. We will not require this general definition as we will only be considering protocols in which each client receives at most one message from the server and sends a single message to the server (which may depend on the message from the server). In this setting, the condition reduces to requiring that the algorithm the client uses to respond to the server satisfies differential privacy with respect to the input of the client, such an algorithm is often referred to as a local randomizer.

An algorithm $\mathcal{R}\colon\mathcal{D}\to\mathcal{S}$ is $({\varepsilon},\delta)$-DP local randomizer if for all pairs $x,x^{\prime}\in\mathcal{D}$, $\mathcal{R}(x)$ and $\mathcal{R}(x^{\prime})$ are $({\varepsilon},\delta)$-indistinguishable.

Let $\mathcal{D}$ denote the domain. A single pass ${\varepsilon}_{0}$-DP local protocol can be equivalently described as a sequence of algorithms $\mathcal{R}^{(i)}:\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}\times\mathcal{D}\to\mathcal{S}^{(i)}$ for $i\in[n]$ (where $\mathcal{S}^{(i)}$ is the range space of $\mathcal{R}^{(i)}$) where the $i$-th client returns $z_{i}=\mathcal{R}^{(i)}(z_{1:i-1},x_{i})$, and $\mathcal{R}^{(i)}(z_{1:i-1},\cdot)$ is an $({\varepsilon},\delta)$-DP local randomizer for all values of auxiliary inputs $z_{1:i-1}\in\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$. The dependence on $z_{1:i-1}$ models the fact that the server can communicate to the client $i$ any information based on the messages from clients $1,\ldots,i-1$.

The shuffle model of privacy is a distributed model of computation in which, as in the local model, clients hold their data and a server communicates with the clients to perform data analysis. In addition, the model includes a shuffler (also referred to as a mixnet). The shuffler collects all the reports sent by clients and anonymizes them by applying a random permutation to all the reports. The shuffled reports are then released to the server. Note that the reports are typically encrypted in a way that they can be decrypted by the server but not by the shuffler (a more detailed discussion of the trust assumptions can be found in [EFMRSTT20]). A server can also communicate back to the clients and the protocol may consist of multiple rounds of communication via a shuffler. Such a protocol is said to satisfy $({\varepsilon},\delta)$-differential privacy in the shuffle model if the outputs of the shuffler on any pair of neighboring datasets are $({\varepsilon},\delta)$-indistinguishable. We remark, that such protocols do not necessarily satisfy local differential privacy.

The anonymization of local reports to improve differential privacy was proposed in [BEMMRLRKTS17], who designed and implemented a principled systems architecture for shuffling. The intuition was formalized in [EFMRTT19, CSUZZ19]. [EFMRTT19] showed that for arbitrary ${\varepsilon}_{0}$-DP local randomizers random shuffling of reports amplifies the privacy guarantees. [CSUZZ19] formally defined the shuffle model of computation and analyzed the privacy guarantees of the binary randomized response in this model. It is important to note that, as in [EFMRTT19], we analyze privacy amplification that results from shuffling of the data before applying local randomizers. In contrast, in the shuffle model the shuffler is applied to reports from the clients. To apply our analysis to the shuffle model, it suffices to observe that for a fixed local randomizer, shuffling of the randomized responses is distributed in the same way as randomized reports on shuffled data. In particular, it enjoys the privacy guarantees that we establish.

In all models, if $\delta=0$ then we will refer to an algorithm as ${\varepsilon}$-differentially private. Further, we will occasionally refer to $\delta=0$ as pure differentially private and $\delta>0$ as approximate differential privacy.

Subsampling is a well known technique for amplifying privacy guarantees [KLNRS08]. That is, suppose that $\mathcal{A}$ is an $({\varepsilon},\delta)$-DP algorithm over datasets of size $m$ and define an algorithm $\mathcal{A}^{\prime}$ over a dataset $X$ of size $n>m$ by picking a random and uniform subset of $m$ elements from $X$ and running $\mathcal{A}$ on the resulting dataset. Privacy amplification by subsampling states that $\mathcal{A}^{\prime}$ is \mathopen{}\mathclose{{}\left(\log(1+\frac{m}{n}(e^{{\varepsilon}}-1)),\frac{m}{n}\delta}\right)-DP [KLNRS08, BBG20]. The following lemma is a slightly more general and abstract version of this result.

Let $P$ and $Q$ be distributions satisfying $P=(1-q)P_{0}+qP_{1}$ and $Q=(1-q)P_{0}+qQ_{1}$ for some $q\in$ and distributions $P_{0},P_{1}$ and $Q_{1}$. Given $\alpha\geq 1$, let $\alpha^{\prime}=1+q(\alpha-1)$ and $\theta=\alpha^{\prime}/\alpha$. Then the following holds

In particular, for any ${\varepsilon}>0$, if ${\varepsilon}^{\prime}=\log(1+q(e^{{\varepsilon}}-1))$ then

Improved Guarantees for Privacy Amplification by Shuffling

In this section we present our main theorem, an improved upper bound for privacy amplification via shuffling for adaptive ${\varepsilon}_{0}$-DP randomizers. Theorem 3.1 provides a clean statement of our improved privacy amplification guarantee, improving on previous bounds in the high ${\varepsilon}_{0}$ regime. The main technical statement is contained in Theorem 3.1.

For any domain $\mathcal{D}$, let $\mathcal{R}^{(i)}:\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}\times\mathcal{D}\to\mathcal{S}^{(i)}$ for $i\in[n]$ (where $\mathcal{S}^{(i)}$ is the range space of $\mathcal{R}^{(i)}$) be a sequence of algorithms such that $\mathcal{R}^{(i)}(z_{1:i-1},\cdot)$ is an ${\varepsilon}_{0}$-DP local randomizer for all values of auxiliary inputs $z_{1:i-1}\in\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$. Let $\mathcal{A}_{\rm s}:\mathcal{D}^{n}\to\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(n)}$ be the algorithm that given a dataset $x_{1:n}\in\mathcal{D}^{n}$, samples a uniform random permutation $\pi$ over $[n]$, then sequentially computes $z_{i}=\mathcal{R}^{(i)}(z_{1:i-1},x_{\pi(i)})$ for $i\in[n]$ and outputs $z_{1:n}$. Then for any $\delta\in$ such that ${\varepsilon}_{0}\leq\log(\frac{n}{16\log(2/\delta)})$, $\mathcal{A}_{\rm s}$ is $({\varepsilon},\delta)$-DP, where

Note that when ${\varepsilon}_{0}>1$, {\varepsilon}=O\mathopen{}\mathclose{{}\left(\frac{\sqrt{e^{{\varepsilon}_{0}}\log(1/\delta)}}{\sqrt{n}}}\right) and when ${\varepsilon}_{0}\leq 1$, {\varepsilon}=O\mathopen{}\mathclose{{}\left({\varepsilon}_{0}\frac{\sqrt{\log(1/\delta)}}{\sqrt{n}}}\right).

A natural question is whether the given bound also holds when ${\varepsilon}_{0}>\log(\frac{n}{16\log(2/\delta)})$ or, equivalently, $\log(2/\delta)\leq\frac{ne^{\epsilon_{0}}}{16}$. In Appendix B we give numerical evidence that there is no privacy amplification when $\log(1/\delta)=\Omega(ne^{-\epsilon_{0}})$.

Our proof relies on a more general result showing that in order to analyze the privacy amplification by shuffling it suffices to upper bound divergence between a specific pair of distributions.

In addition to giving our closed-form upper bound, Theorem 3.2, provides an efficient method for numerically computing a tighter upper bound. We describe this numerical approach in Section 6.

Now let us turn to the proof of Theorems 3.1 and 3.2. As mentioned earlier, our proof involves reducing the problem of analyzing the privacy guarantee of an adaptive series of local randomizers applied to shuffled data to analyzing the privacy guarantee of a simple non-adaptive local algorithm with three outputs. Suppose that $X_{0}$ and $X_{1}$ are neighbouring databases that differ on the first datapoint, $x_{1}^{0}\neq x_{1}^{1}$. The reduction is outlined in Figure 1, which shows the behavior of the simpler algorithm on data set $X_{0}$. The key observation is that for any ${\varepsilon}_{0}$-DP local randomizer $\mathcal{R}$ and data point $x$, $\mathcal{R}(x)$ can be seen as sampling from the same distribution as $\mathcal{R}(x_{1}^{0})$ with probability at least $e^{-{\varepsilon}_{0}}/2$ and sampling from the same distribution as $\mathcal{R}(x_{1}^{1})$ with probability at least $e^{-{\varepsilon}_{0}}/2$. That is, with probability $e^{-{\varepsilon}_{0}}$ each data point can create a clone of the output of $\mathcal{R}(x_{1}^{0})$ or a clone of $\mathcal{R}(x_{1}^{1})$ with equal probability. Thus $n-1$ data elements effectively produce a random number of clones of both $x_{1}^{0}$ and $x_{1}^{1}$. These clones make distinguishing whether the original data set contains $x_{1}^{0}$ or $x_{1}^{1}$ as its first element much harder.

The proof of Theorem 3.1 will require an additional step where we observe that if $\mathcal{R}$ is ${\varepsilon}_{0}$-DP then $\mathcal{R}(x_{1}^{0})$ and $\mathcal{R}(x_{1}^{1})$ are similar, and thus privacy is further amplified. Let us start by proving Lemma 3.3, which captures just the privacy amplification due to the generation of clones. The following lemma analyses the divergence between the distributions on the number of clones that result from this reduction.

For notational brevity, we will frequently use the same symbol to refer to both a random variable and it’s probability density function. In particular, if $X$ and $Y$ are random variables and $\alpha\in$ then $Z=\alpha X+(1-\alpha)Y$ denotes the random variable that samples from $X$ with probability $\alpha$ and $Y$ with probability $1-\alpha$. Consequently, for a randomized algorithm $\mathcal{A}$ and input $x$, we treat the output $\mathcal{A}(x)$ as a random variable and also use $\mathcal{A}(x)$ to refer to the probability density function of this random variable.

Lemma 3.3 describes our reduction from the original problem to analysis of shuffling for a simple non-adaptive protocol. Specifically, it shows that if each local randomizer $\mathcal{R}$ we apply can be decomposed into a mixture of $\mathcal{R}(x_{1}^{0})$, $\mathcal{R}(x_{1}^{1})$ and some “left-over” distribution $\textup{{LO}}(x)$ then we can apply our reduction. We will then conclude the proof of Theorem 3.1 by observing that that every differentially private randomizer has this property.

For a domain $\mathcal{D}$, let $\mathcal{R}^{(i)}:\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}\times\mathcal{D}\to\mathcal{S}^{(i)}$ for $i\in[n]$ (where $\mathcal{S}^{(i)}$ is the range space of $\mathcal{R}^{(i)}$) be a sequence of algorithms such that $\mathcal{R}^{(i)}(z_{1:i-1},\cdot)$ is an ${\varepsilon}_{0}$-DP local randomizer for all values of auxiliary inputs $z_{1:i-1}\in\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$. Let $\mathcal{A}_{\rm s}:\mathcal{D}^{n}\to\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(n)}$ be the algorithm that given a dataset $x_{1:n}\in\mathcal{D}^{n}$, samples a permutation $\pi$ uniformly at random, then sequentially computes $z_{i}=\mathcal{R}^{(i)}(z_{1:i-1},x_{\pi(i)})$ for $i\in[n]$ and outputs $z_{1:n}$. Let $X_{0}=(x^{0}_{1},x_{2},\ldots,x_{n})$ and $X_{1}=(x^{1}_{1},x_{2},\ldots,x_{n})$ be two neighboring datasets such that for all $j\neq 1$, $x_{j}\notin\{x_{1}^{0},x_{1}^{1}\}$. Suppose that there exists a positive value $p\in(0,1]$ such that for all $i\in[n]$, $x\in\mathcal{D}\setminus\{x_{1}^{0},x_{1}^{1}\}$ and $z_{1:i-1}\in\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$, there exists a distribution $\textup{{LO}}^{(i)}(z_{1:i-1},x)$ such that

Then there exists a randomized postprocessing algorithm $f$ such that $\mathcal{A}_{\rm s}(X_{0})$ is distributed identically to $f(A+1,C-A)$ and $\mathcal{A}_{\rm s}(X_{1})$ is distributed identically to $f(A,C-A+1)$, where $C\sim{\rm Bin}(n-1,p)$, $A\sim{\rm Bin}(C,1/2)$.

The proof of the above lemma relies on a decomposition of the algorithm that shuffles the data and then applies the local randomizers, to an algorithm in which each client first reports which component of the mixture it will sample from, then applies shuffling to these reports and finally applies a post-processing step in which randomizers are applied according to the shuffled mixture component indices.

Formally, define a random variable $Y$ as follows

Given a dataset $X_{b}$ for $b\in\{0,1\}$ we generate $n$ samples from $\{0,1,2\}$ in the following way. Client number one (holding the first element of the dataset) reports $b$. Clients $2,\ldots,n$ each report an independent sample from $Y$. We then shuffle the reports randomly. Let $\rho_{b}$ denote the resulting distribution over $\{0,1,2\}^{n}$.

We claim that there exists a post-processing function $f$ (that depends on $x^{0}_{1},x^{1}_{1},x_{2},\ldots,x_{n}$) such that for $y$ sampled from $\rho_{b}$, $f(y)$ is distributed identically to $\mathcal{A}_{\rm s}(X_{b})$. To see this, consider the following process that takes a $b\in\{0,1\}$ as an input and defines a jointly distributed pair of random variables $(z,y)$ over $\mathcal{S}\times\{0,1,2\}^{n}$, where $\mathcal{S}=\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(n)}$ is the output space of $\mathcal{A}_{\rm s}$. Let $\pi$ be a randomly and uniformly chosen permutation of $[n]$. For every $i\in[n]$, if $\pi(i)\neq 1$ then we first sample $y_{i}$ according to $Y$, and if $i=1$, we set $y_{i}=b$. We then use the $y_{i}$’s to generate $z_{i}$’s. Specifically,

By our assumption, this produces a sample $z_{i}$ from $\mathcal{R}^{(i)}(z_{1:i-1},x_{\pi(i)})$. It is easy to see that the resulting random variable $(z,y)$ has the property that for input $b\in\{0,1\}$ its marginal distribution over $\mathcal{S}$ is the same as $\mathcal{A}_{\rm s}(X_{b})$ and marginal distribution over $\{0,1,2\}^{n}$ is $\rho_{b}$.

We can now show that for every fixed value $v\in\{0,1,2\}^{n}$ and $b\in\{0,1\}$, one can generate a sample from the distribution of $z$ conditioned on $y=v$ without knowing $b$ from which the pair $(z,y)$ was generated. First observe that the above construction of $(y,z,\pi)$ has the property that for any permutation $\sigma$, conditioned on $(y=v,\pi=\sigma)$, the random variable $z$ does not depend on $b$. A natural approach to sample from $z|_{y=v}$ would be to sample a permutation $\sigma$ from the distribution of $\pi$ conditioned on $y=v$, and then sample $z|_{(y,\pi)=(v,\sigma)}$. The conditional distribution of $\pi|_{y=v}$ however is not independent of $b$. Let $T=\pi(\{i:y_{i}=2\})$ be the indices corresponding to $v_{i}=2$. First observe that $T|_{y=v}$ is independent of $b$, since this distribution is uniform over subsets of $\{2,\ldots,n\}$ of the appropriate size. Finally, note that the sampling of $z$ given $y$ only needs $T$. Thus we can sample from $z|_{(y,T)=(v,J)}$ without knowing $b$. This conditional sampling is exactly the post-processing step that we claimed. We include a formal description of the post-processing step in Algorithm 1.

We now analyze the divergence between $\rho_{0}$ and $\rho_{1}$. First, the shuffling step implies that $\rho_{0}$ and $\rho_{1}$ are symmetric. That is, the probability of any sequence $y\in\{0,1,2\}^{n}$ depends only on the total number of 0s and 1s in the sequence. This implies that the divergence between $\rho_{0}$ and $\rho_{1}$ is equal to the divergence between the distribution of the counts of 0’s and 1’s. Let $(c_{0},c_{1})=(\sum_{i\in[n]}\mathds{1}_{y_{i}=0},\sum_{i\in[n]}\mathds{1}_{y_{i}=1}$). It now suffices to observe that, if $C\sim{\rm Bin}(n-1,p)$ and $A\sim{\rm Bin}(C,1/2)$, then the counts for $y\sim\rho_{0}$ are distributed as $(1+A,C-A)$ and the count for $y\sim\rho_{1}$ is distributed as $(A,C-A+1)$.

We can now complete the proof of Theorem 3.1. To do this we will use privacy amplification provided by the clones (Lemma 3.3) together with the observation that for any ${\varepsilon}_{0}$-DP randomizer $\mathcal{R}$, $\mathcal{R}(x^{0}_{1})$ and $\mathcal{R}(x^{1}_{1})$ are ${\varepsilon}_{0}$-indistinguishable. To fit this into our analysis we will use the fact that $\mathcal{R}(x^{0}_{1})$ and $\mathcal{R}(x^{1}_{1})$ can be viewed as post-processing of a binary randomized response with parameter ${\varepsilon}_{0}$ [KOV15] (see also [MV16]).

Let $\mathcal{R}\colon\mathcal{D}\to\mathcal{S}$ be an ${\varepsilon}_{0}$-DP local randomizer and $x_{0},x_{1}\in\mathcal{D}$. Then there exists a randomized algorithm $\mathcal{Q}\colon\{0,1\}\to\mathcal{S}$ such that $\mathcal{R}(x_{0})=\frac{e^{{\varepsilon}_{0}}}{e^{{\varepsilon}_{0}}+1}\mathcal{Q}(0)+\frac{1}{e^{{\varepsilon}_{0}}+1}\mathcal{Q}(1)$ and $\mathcal{R}(x_{1})=\frac{1}{e^{{\varepsilon}_{0}}+1}\mathcal{Q}(0)+\frac{e^{{\varepsilon}_{0}}}{e^{{\varepsilon}_{0}}+1}\mathcal{Q}(1)$.

Binary randomized response can be seen as an algorithm that outputs its input with probability $\frac{e^{{\varepsilon}_{0}}-1}{e^{{\varepsilon}_{0}}+1}$ and outputs an unbiased coin flip with probability $\frac{2}{e^{{\varepsilon}_{0}}+1}$. Thus it can be seen as providing privacy amplification by subsampling with probability $\frac{e^{{\varepsilon}_{0}}-1}{e^{{\varepsilon}_{0}}+1}$. Note that for ${\varepsilon}_{0}<1$ this probability is $O({\varepsilon}_{0})$. This will ensure that our bound is accurate in the regime ${\varepsilon}_{0}<1$.

Let $X_{0}$ and $X_{1}$ be neighboring datasets. We can assume without loss of generality that $X_{0}=(x^{0}_{1},x_{2},\ldots,x_{n})$ and $X_{1}=(x^{1}_{1},x_{2},\ldots,x_{n})$ for $x_{1}^{0}\neq x_{1}^{1}$ (since the shuffler applies a random permutation). Further, we can assume without loss of generality that for all $j\neq 1$, $x_{j}\notin\{x_{1}^{0},x_{1}^{1}\}$. This true since we can add elements ${x^{\prime}}_{1}^{0}$ and ${x^{\prime}}_{1}^{1}$ to the domain $\mathcal{D}$ and define $\mathcal{R}^{(i)}$ on them in the same way as on $x_{1}^{0}$ and $x_{1}^{1}$, respectively. With this definition, for $b\in\{0,1\}$, the output distribution of $\mathcal{A}_{\rm s}({x^{\prime}}_{1}^{b},x_{2},\ldots,x_{n})$ is identical to that of $\mathcal{A}_{\rm s}(X_{b})$.

By Lemma 3.4 we have that for every $i$ and value of auxiliary input $z_{1:i-1}$ there exists a randomized algorithm $\mathcal{Q}^{(i)}(z_{1:i-1},\cdot)\colon\{x_{1}^{0},x_{1}^{1}\}\to\mathcal{S}^{(i)}$ such that

where again for notational brevity we use the same notation for a random variable and its probability density function.

Next we observe that the definition of ${\varepsilon}_{0}$-DP directly implies that for an ${\varepsilon}_{0}$-DP randomizer $\mathcal{R}\colon\mathcal{D}\to\mathcal{S}$ and any input $x_{0}\in\mathcal{D}$, there exists a randomized algorithm $\textup{{LO}}\colon\mathcal{D}\to\mathcal{S}$ such that $\mathcal{R}(x)$ can be decomposed as

Applying this argument twice we obtain that, for any pair of inputs $x_{0},x_{1}\in\mathcal{D}$ there exists a decomposition

Applying this observation to $\mathcal{R}^{(i)}(z_{1:i-1},\cdot)$, for all $i\in[n]$ and values of $z_{1:i-1}$, we have that there exists a randomized algorithm $\textup{{LO}}^{(i)}$ such that for $p=e^{-{\varepsilon}_{0}}$ we have:

Next we consider the algorithm $\mathcal{A}_{\mathcal{Q}}$ which is defined in the same way as $\mathcal{A}_{\rm s}$, except $\mathcal{R}^{(i)}(z_{1:i-1},x_{1}^{b})$ is replaced with $\mathcal{Q}^{(i)}(z_{1:i-1},x_{1}^{b})$. Formally, we define a randomizer $\mathcal{R}_{\mathcal{Q}}^{(i)}$ as follows: For all $x\in\mathcal{D}$, $i\in[n]$ and values of $z_{1:i-1}$ we let

Let $\mathcal{A}_{\mathcal{Q}}$ be defined in the same way as $\mathcal{A}_{\rm s}$, except $\mathcal{R}^{(i)}$ is replaced with $\mathcal{R}_{\mathcal{Q}}^{(i)}$.

Equations (3) and (4), allow us to decompose $\mathcal{A}_{\rm s}(X_{0})$ and $\mathcal{A}_{\rm s}(X_{1})$ into the mixture of two components as follows:

Note that by eq. (5), for all $x\notin\{x_{1}^{0},x_{1}^{1}\}$,

To complete the proof of Theorem 3.1, all we need is the following lemma on the hockey-stick divergence between the distributions resulting from Theorem 3.2 and the post-processing inequality for the hockey-stick divergence.

Our bound is based on a simpler and stronger reduction of this type that was also independently shown in [CU20]. Its tightest form is best stated in the add/delete variant of differential privacy which was defined for local randomizers in [EFMRSTT20].

An algorithm $\mathcal{R}\colon\mathcal{D}\to\mathcal{S}$ is a deletion $({\varepsilon},\delta)$-DP local randomizer if there exists a reference distribution $\rho$ such that for all data points $x\in\mathcal{D}$, $\mathcal{R}(x)$ and $\rho$ are $({\varepsilon},\delta)$-indistinguishable.

We will occasionally refer to a function that satisfies Definition 2.2 as a replacement $({\varepsilon},\delta)$-DP local randomizer. It is easy to show that a replacement $({\varepsilon},\delta)$-DP algorithm is also a deletion $({\varepsilon},\delta)$-DP algorithm, and that a deletion $({\varepsilon},\delta)$-DP algorithm is also a replacement $(2{\varepsilon},2\delta)$-DP algorithm. The following Lemma allows us to convert $({\varepsilon},\delta)$-DP local randomizers to ${\varepsilon}$-DP local randomizers that are within $\delta$ in total variation distance.

Suppose $\mathcal{R}$ is a deletion $({\varepsilon},\delta)$-DP local randomizer with reference distribution $\rho$. Then there exists a randomizer $\mathcal{R}^{\prime}$ that is a deletion ${\varepsilon}$-DP local randomizer with reference distribution $\rho$, and for all inputs $x$, ${\rm TV}(\mathcal{R}(x),\mathcal{R}^{\prime}(x))\leq\delta$. In particular, $\mathcal{R}^{\prime}$ is a (replacement) $2{\varepsilon}$-DP local randomizer.

The proof can be found in Appendix C. We note that when this transformation is applied to an $({\varepsilon},\delta)$-DP local randomizer that is also deletion $({\varepsilon}/2,\delta)$-DP (such as, for example, addition of isotropic Gaussian noise to a vector from a Euclidean ball of bounded radius) then the extra factor $2$ can be avoided. To avoid incurring this factor of $2$ in our amplification by shuffling bound, we apply the core observation from the proof of Lemma 3.7 directly in our proof of the amplification bound. This leads to the following resulting bound which we prove in Appendix C.

For a domain $\mathcal{D}$, let $\mathcal{R}^{(i)}\colon f\times\mathcal{D}\to\mathcal{S}^{(i)}$ for $i\in[n]$ (where $\mathcal{S}^{(i)}$ is the range space of $\mathcal{R}^{(i)}$) be a sequence of algorithms such that $\mathcal{R}^{(i)}(z_{1:i-1},\cdot)$ is a $({\varepsilon}_{0},\delta_{0})$-DP local randomizer for all values of auxiliary inputs $z_{1:i-1}\in\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$. Let $\mathcal{A}_{\rm s}\colon\mathcal{D}^{n}\to\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(n)}$ be the algorithm that given a dataset $x_{1:n}\in\mathcal{D}^{n}$, samples a uniformly random permutation $\pi$, then sequentially computes $z_{i}=\mathcal{R}^{(i)}(z_{1:i-1},x_{\pi(i)})$ for $i\in[n]$ and outputs $z_{1:n}$. Then for any $\delta\in$ such that ${\varepsilon}_{0}\leq\log(\frac{n}{16\log(2/\delta)})$, $\mathcal{A}_{\rm s}$ is $({\varepsilon},\delta+(e^{{\varepsilon}}+1)(1+e^{-{\varepsilon}_{0}}/2)n\delta_{0})$-DP, where ${\varepsilon}$ is as in Equation (1).

Notice that the bound on ${\varepsilon}$ in Theorem 3.8 matches the bound in Theorem 3.1. A natural question is if the dependence of $\delta$ on $n$ and ${\varepsilon}_{0}$ is optimal. We leave this question for future work.

A Tighter Analysis for Specific Randomizers

In this section we give a more refined analysis of the amplification by shuffling that can exploit additional properties of the local randomizer and lead to improved privacy amplification results for specific randomizers. In particular, Theorem 4.1 will immediately imply a privacy amplification by shuffling result for $k$ randomized response (kRR). To our knowledge, this is the first theoretical result that shows that privacy amplification improves as $k$ increases, corroborating empirical results from [BBGN19]. As with Theorem 3.1, Theorem 4.1 also gives us a method for empirically computing the privacy guarantee.

We will show the amplification bound is stronger if, in addition, $\mathcal{R}^{(i)}(z_{1:i-1},x_{1}^{0})$ and $\mathcal{R}^{(i)}(z_{1:i-1},x_{1}^{1})$ are close in total variation distance, specifically when the total variation distance is less than $2/(e^{{\varepsilon}_{0}}+1)$ (which is implied by $\mathcal{R}^{(i)}$ being ${\varepsilon}_{0}$-DP).

We first state the most general form of this amplification theorem. We will use ${\rm MultNom}(n;p_{1},\ldots,p_{k})$ to denote the multinomial distribution over $k$-tuples with $n$ samples and probabilities of each of the outcomes being $p_{1},\ldots,p_{k}$ (where $\sum_{i\in[k]}p_{k}=1)$.

For a domain $\mathcal{D}$, let $\mathcal{R}^{(i)}:\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}\times\mathcal{D}\to\mathcal{S}^{(i)}$ for $i\in[n]$ (where $\mathcal{S}^{(i)}$ is the range space of $\mathcal{R}^{(i)}$) be a sequence of algorithms such that $\mathcal{R}^{(i)}(z_{1:i-1},\cdot)$ is a ${\varepsilon}_{0}$-DP local randomizer for all values of auxiliary inputs $z_{1,i-1}\in\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$. Let $\mathcal{A}_{\rm s}:\mathcal{D}^{n}\to\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(n)}$ be the algorithm that given a dataset $x_{1:n}\in\mathcal{D}^{n}$, samples a uniformly random permutation $\pi$, then sequentially computes $z_{i}=\mathcal{R}^{(i)}(z_{1:i-1},x_{\pi(i)})$ for $i\in[n]$ and outputs $z_{1:n}$. Let $X_{0}=(x^{0}_{1},x_{2},\ldots,x_{n})$ and $X_{1}=(x^{1}_{1},x_{2},\ldots,x_{n})$ be two neighboring datasets such that for all $j\neq 1$, $x_{j}\notin\{x_{1}^{0},x_{1}^{1}\}$. Suppose that there exist positive values $p\in(0,1/3]$ and $q\in(0,1)$ such that for all $i\in[n]$ and $z_{1:i-1}\in\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$, there exists distributions $\mathcal{Q}^{(i)}_{0}(z_{1:i-1}),\mathcal{Q}^{(i)}_{1}(z_{1:i-1},x_{1}^{0})$ and $\mathcal{Q}^{(i)}_{1}(z_{1:i-1},x_{1}^{1})$ such that for all $b\in\{0,1\}$,

and for all $x\in\mathcal{D}\setminus\{x_{1}^{0},x_{1}^{1}\}$, there exists a distribution $\textup{{LO}}{(i)}(z_{1:i-1},x)$ such that

The reduction to analysis of the divergence between a pair of multinomial distributions in the proof of Theorem 4.1 is achieved using the same argument as the one we used to prove Theorem 3.2. The analysis of the resulting divergence relies on decomposing each of the resulting multinomial distributions into a mixture of two distributions. We then show that distributions we analyzed when proving Lemma 3.5 can be postprocessed into pairs of components of these mixtures. This allows us to show that all components of these mixtures are $({\varepsilon}^{\prime},\delta^{\prime})$-indistinguishable. Joint convexity can then be used to obtain the bound. The details of the proof appear in Appendix D.

The main strength of Theorem 4.1 is that it allows us to prove tighter bounds than Theorem 3.1 for specific local randomizers. In the next section, we will show how Theorem 4.1 can be used to provide a tighter analysis of $k$ randomized response. However, we can also use it to rederive the bound from Theorem 3.1, although with a slightly worse constant factor. The decomposition in Lemma 3.4 implies that for any ${\varepsilon}_{0}$-DP local randomizer Equation (8) holds with $q=\frac{e^{{\varepsilon}_{0}}-1}{e^{{\varepsilon}_{0}}+1}$. That is, given a sequence of $\mathcal{R}^{(i)}$ of ${\varepsilon}_{0}$-DP local randomizers, and neighbouring datasets $X_{0}$ and $X_{1}$ such that $x_{0}^{0}\neq x_{1}^{1}$, there exist distributions $\mathcal{Q}^{(i)}(z_{1:i-1},x_{1}^{0})$ and $\mathcal{Q}^{(i)}(z_{1:i-1},x_{1}^{1})$ that satisfy equations (3) and (4). Thus, by setting

we get that for $b\in\{0,1\}$ and $q=\frac{e^{{\varepsilon}_{0}}-1}{e^{{\varepsilon}_{0}}+1}$,

Further, Equation (5) implies that for any $x\in\mathcal{D}$ and $b\in\{0,1\}$,

Letting $q=\frac{e^{{\varepsilon}_{0}}-1}{e^{{\varepsilon}_{0}}+1}$ and $p=e^{-{\varepsilon}_{0}}/3$ and assuming {\varepsilon}_{0}\leq\ln\mathopen{}\mathclose{{}\left(\frac{n}{24\ln(2/\delta)}}\right) (which implies $p\geq\frac{8\ln(2/\delta)}{n}$), Equation (10) gives the bound

which matches the bound stated in Equation (1) of Theorem 3.1 up to a factor of $\sqrt{3/2}$.

where $\mathcal{U}_{[k]}$ is the uniform distribution over $[k]$. That is, with probability $\frac{e^{{\varepsilon}_{0}}-1}{e^{{\varepsilon}_{0}}+k-1}$ the true data point is reported, and otherwise a random value is reported.

Notice that when $k$ is small, this bound matches that given in Theorem 3.1, but when $k$ and ${\varepsilon}_{0}$ are large, ${\varepsilon}$ scales like $\frac{e^{{\varepsilon}_{0}}}{\sqrt{kn}}$. The proof of Corollary 4.2 can be found in Appendix E. The key observation is that if we let $\nu$ be the uniform distribution on $[k]$, then for any $x\in[k]$,

where $\mathds{1}_{x}$ is the distribution that always outputs $x$.

Applications

where the expectation is over the randomness of samples and the algorithm.

and therefore an algorithm for frequency estimation implies an algorithm for distribution estimation with error larger by at most $1/\sqrt{n}$.

A number of algorithms for frequency and distribution estimation in the local model have been developed [HKR12, EPK14a, BS15, KBR16, WHWNXYLQ16, WBLJ17, YB18, ASZ19, AS19, BNS19, BNST20, CKÖ20, FT21]. Recent work focuses on achieving (asymptotically) optimal accuracy in the ${\varepsilon}_{0}>1$ regime and low communication. In particular, [ASZ19] give an efficient, low communication ($\log k+2$ bits per user) ${\varepsilon}_{0}$-DP local algorithm that is asymptotically optimal for all ${\varepsilon}_{0}$ (their result is stated for the distribution estimation problem but also applies to the frequency estimation problem). A related algorithm with similar theoretical guarantees but somewhat better empirical performance is given in [CKÖ20].

For every positive integer $k$ and ${\varepsilon}_{0}>0$, there exists an ${\varepsilon}_{0}$-LDP protocol for frequency estimation that outputs a vector of frequencies $\hat{p}$ such that for every dataset $X\in[k]^{n}$,

The bounds achieved by this algorithm are asymptotically optimal for LDP [YB18] when ${\varepsilon}_{0}\leq\log k$. (A different setting of parameters can be used to achieve optimality in the regime when ${\varepsilon}_{0}>\log k$ but we omit this regime as it does not appear to be practically relevant.) The best accuracy for low-communication protocols, specifically

is achieved by an algorithm in a recent work of [FT21] albeit at the expense of slower server-side decoding time.

Using the fact that our amplification bound has optimal dependence on ${\varepsilon}_{0}$, we are able to leverage any of the asymptotically optimal results for local DP to immediately obtain a low communication, single round algorithm in the shuffle model whose error matches the optimal error for distribution estimation in the central model up to a $O(\sqrt{\log(1/\delta)})$ factor. For frequency estimation the error in the central model is optimal up to the $1/\sqrt{n}$ additive term (that is comparable to the statistical error) which is known to be necessary for algorithms in the single message shuffle model [GGKPV19].

For every positive integer $k$ and ${\varepsilon},\delta\in(0,1)$, there exists an $({\varepsilon},\delta)$-DP protocol for frequency estimation that outputs a vector of frequencies $\hat{p}$ such that for every dataset $X\in[k]^{n}$,

For a local randomizer ${\mathcal{A}_{\rm ldp}}$, let $\mathcal{A}_{\rm s}({\mathcal{A}_{\rm ldp}})$ be the algorithm that given a data set $x_{1:n}\in\mathcal{D}^{n}$, samples a uniform random permutation $\pi$ over $[n]$, then outputs $({\mathcal{A}_{\rm ldp}}(x_{\pi(1)}),\cdots,{\mathcal{A}_{\rm ldp}}(x_{\pi(n)}))$.

ensure that for a local randomizer ${\mathcal{A}_{\rm ldp}}$ that is $\varepsilon_{0}$-DP, the shuffled output $\mathcal{A}_{\rm s}({\mathcal{A}_{\rm ldp}})$ is $(\varepsilon,\delta)$-DP.

According to Theorem 5.1, there exists an ${\varepsilon}_{0}$-DP local randomizer ${\mathcal{A}_{\rm ldp}}$ and algorithm $f$ such that $f\circ{\mathcal{A}_{\rm ldp}}$ has error

Substituting the value of ${\varepsilon}_{0}$ gives the claimed result. ∎

We note that for the frequency estimation problem in the shuffle model the first algorithm that achieves communication cost that is $o(k)$ while being asymptotically nearly optimal for the central model was given in [GGKPV19]. Their relatively involved multi-message protocol has communication cost of $O(\log k\cdot\log n\cdot\log(1/({\varepsilon}\delta))/{\varepsilon}^{2})$. It also does not have local DP guarantees and is relatively inefficient computationally.

2 Privacy Analysis of Private Stochastic Gradient Descent

For any $\delta\in$ such that ${\varepsilon}_{0}\leq\log(\frac{n}{16\log(2/\delta)})$, Algorithm 2 is $({\varepsilon},\delta+O(e^{{\varepsilon}}\delta_{0}n))$-DP where

then the output of Algorithm 2 can be obtained by post-processing of the shuffled output $\mathcal{A}_{\rm s}(X)$. Since each $\mathcal{R}^{(i)}(z_{1:i-1},\cdot)$ is a $({\varepsilon}_{0},\delta_{0})$-DP local randomizer and ${\varepsilon}_{0}\leq\log(\frac{n}{16\log(2/\delta)})$, Theorem 3.8 implies that Algorithm 2 is $({\varepsilon},\delta+(e^{{\varepsilon}}+1)(1+e^{-{\varepsilon}_{0}}/2)n\delta_{0})$-DP, where ${\varepsilon}$ is as given in Equation (12). ∎

For a single pass over the data and ${\varepsilon}_{0}>1$, the privacy analysis in Proposition 5.3 is tighter than that given by [BST14], who analyse sampling with replacement. For any $\delta>0$, their analysis, which relies on privacy amplification by subsampling and advanced composition of differentially private algorithms, gives a privacy guarantee of $({\varepsilon},n\delta+\frac{\delta_{0}}{n})$ where

For large ${\varepsilon}_{0}$, our result above (Proposition 5.3) improves on this by a factor of $\Theta(\sqrt{e^{{\varepsilon}_{0}}})$. We note that for multiple passes over the data, our analysis suffers an extra $\sqrt{\log(1/\delta)}$ factor in the privacy loss compared to Equation (13). Work subsequent to [BST14] has improved the privacy analysis for multiple passes using concentrated differential privacy to shave an additional $\sqrt{\log(1/\delta)}$ [ACGMMTZ16, WBK21]. Our analysis technique for Algorithm 2 is also the basis of the analysis of the optimization algorithms in [BKMTT20]. We also note that Proposition 5.3 can be easily extended to the batched version of SGD by viewing each batch of size $b$ as a single data element in $\mathcal{D}^{b}$.

Numerical Results

Theorem 3.2 provides an efficient method for numerically computing an amplification bound that is tighter than our closed-form bound. Our implementation is outlined in Appendix F, but the main component is numerically computing the indistinguishability bound for multinomial random variables from Lemma 3.5. In this section, we provide numerical evaluations of the privacy amplification bound in a variety of parameter regimes. In Figure 2, Clones, Theoretical is the bound presented in Theorem 3.1 and Clones is the numerical version derived from Theorem 3.2. Also, BBGN’19 is the privacy amplification bound for general algorithms given in [BBGN19]BBGN’19 curves were produced using open source code released by \AtNextCite\AtEachCitekey\@nocounterrmaxnames [BBGN19], they correspond to the curve (Bennett, Generic) in [BBGN19]. and BKMTT’20 is the bound proven in [BKMTT20]. Finally, CSUZZ’19, 2RR is the closed form amplification bound for binary randomized response proved in [CSUZZ19] and 2RR, lower bound is a lower bound on the shuffling privacy guarantee of binary randomized response that we compute directly. A description of our implementation of 2RR, lower bound is found in Appendix G. We do not include the bounds from [EFMRTT19] in the comparison since [BKMTT20] gives a tighter bound for the same analysis.

In all parameter regimes tested, Clones gives a tighter bound compared to BBGN’19 as well as BKMTT’20. We can see in Figure 2(c) that this effect is particularly pronounced when ${\varepsilon}_{0}$ is large, which is the parameter regime where our closed-form bounds asymptotically improve over prior work. Being a lower bound for a particular algorithm, 2RR, lower bound provides a lower bound on any general privacy amplification result. We can see in Figure 2(c) that for large $n$, Clones closely tracks 2RR, lower bound, particularly for small ${\varepsilon}_{0}$. We note in all three graphs in Figure 2, Clones should be monotone. The slight non-monotonicity results from some optimizations that speed up the computation at the cost of slightly looser upper bound. We defer details to Appendix F.

Indistinguishability of random variables is only one way of several possible ways to measure to similarity in the output distributions of neighboring datasets. The Rényi divergence, that captures the moment generating function of the privacy loss random variable, is an alternate measure resulting in Rényi differential privacy [DR16, ACGMMTZ16, Mir17, BS16].

For two random variables $P$ and $Q$, the Rényi divergence of $P$ and $Q$ of order $\alpha>1$ is

For $\alpha>1$, an algorithm $\mathcal{A}:\mathcal{D}^{n}\to\mathcal{S}$ is $({\varepsilon}(\alpha),\alpha)$-Rényi differentially private (RDP) if for all neighboring databases $X$ and $X^{\prime}$, $D^{\alpha}(\mathcal{A}(X)\|\mathcal{A}(X^{\prime}))\leq{\varepsilon}(\alpha)$.

Theorem 3.2 implies that to bound the RDP guarantees of $\mathcal{A}_{\rm s}$ it suffices to compute the Rényi divergence between the two multinomial distributions $(A+\Delta,C-A+1-\Delta)$ and $(A+1-\Delta,C-A+\Delta)$. Below we evaluate this approach numerically in Section 6.1.

In Figure 3 we plot the Rényi privacy parameter for shuffling $n$ ${\varepsilon}_{0}$-DP local randomizers as a function of the RDP order $\alpha$. Clones is computed by directly computing the Rényi divergence between the two multinomial distributions $(A+1-\Delta,C-A+\Delta)$ and $(A+\Delta,C-A+1-\Delta)$, providing an upper bound on the privacy amplification by shuffling for RDP. For comparison, we include a bound computed using Theorem 1 from [GDDSK21] which we label as GDDSK’21. (We remark that the results in this subsection were not included in the earlier version of our work.) 2RR, lower bound provides a lower bound on the shuffling privacy guarantee of binary randomized response, and hence a lower bound on any general amplification result for RDP. Figure 3(a) shows that privacy amplification is achieved for small/moderate moments, but the Rényi DP parameter ${\varepsilon}(\alpha)$ approaches ${\varepsilon}_{0}$ as $\alpha$ increases.

A key property of differentially private algorithms is that the composition of differentially private algorithms is differentially private. The advanced composition theorem quantifies the privacy guarantee after composing $T$ $({\varepsilon},\delta)$-DP algorithms. When composing a large number of algorithms, [ACGMMTZ16] showed that tighter privacy guarantees can be obtained by computing the composition guarantees in terms of RDP and then converting back to approximate differential privacy. In Figure 3, we plot the privacy guarantee for $T$ adaptively composed outputs of a shuffler with each shuffler operating on $n$, ${\varepsilon}_{0}$-DP local randomizers as defined as in Theorem 3.1. We compare two methods for computing the resulting privacy guarantee. Clones, via Approximate DP computes the privacy guarantee of $\mathcal{A}_{\rm s}$ numerically in terms of approximate differential privacy, then used advanced composition [KOV15, Theorem 4.3] to compute the privacy guarantee of the composition. Clones, via RDP computes the privacy guarantee of $\mathcal{A}_{\rm s}$ numerically in terms of Rényi differential privacy, computes the privacy guarantee of the composition using the composition theorem for Rényi DP [Mir17], then converts to an approximate DP guarantee [CKS20, Proposition 12]. We also compare to the latter approach performed using the RDP privacy amplification result presented in [GDDSK21] (with parameters chosen as in [GDDSK21]). As can be seen from the results, our technique provides a significantly tighter upper bound.

References

Appendix A Proof of Lemma 3.5

See 3.5 To prove Lemma 3.5 we first upper bound the divergence between a pair of slightly simpler distributions.

Consider the process where we sample $C\sim{\rm Bin}(n-1,p)$ and $A\sim{\rm Bin}(C,1/2)$. Let $P=(A+1,C-A)$ and $Q=(A,C-A+1)$, then

In particular, $P$ and $Q$ are $({\varepsilon},\delta)$- indistinguishable.

Using a Chernoff bound and Hoeffding’s inequality, with probability $\delta$ since $p\geq\frac{3\log(4/\delta)}{n}$ both

Now, note that $p\geq\frac{16\ln(4/\delta)}{n}$ implies that $\sqrt{3pn\log(4/\delta)}\leq pn/2$ and, $\sqrt{\frac{C}{2}\log(4/\delta)}\leq C/4$. Given a specific output $(a,b)$,

Now, if $A$ and $C$ satisfy equation (14) then

Therefore, setting ${\varepsilon}=\log(1+\frac{\sqrt{64\log(4/\delta)}}{\sqrt{pn}}+\frac{8}{pn})$ gives that $P$ and $Q$ are $({\varepsilon},\delta)$ indistinguishable.

We can now complete the proof of Lemma 3.5 by using the advanced joint convexity of the hockey-stick divergence.

Let $P_{0}=(A+1,C-A)$ and $Q_{0}=(A,C-A+1)$ and let $\rho_{0}$ and $\rho_{1}$ denote their respective probability distributions. Then, by Lemma A.1 for $p=e^{-{\varepsilon}_{0}}$,