Privacy Amplification via Random Check-Ins

Introduction

Modern mobile devices and web services benefit significantly from large-scale machine learning, often involving training on user (client) data. When such data is sensitive, steps must be taken to ensure privacy, and a formal guarantee of differential privacy (DP) is the gold standard. For this reason, DP has been adopted by companies including Google , Apple , Microsoft , and LinkedIn , as well as the US Census Bureau .

Other privacy-enhancing techniques can be combined with DP to obtain additional benefits. In particular, cross-device federated learning (FL) allows model training while keeping client data decentralized (each participating device keeps its own local dataset, and only sends model updates or gradients to the coordinating server). However, existing approaches to combining FL and DP make a number of assumptions that are unrealistic in real-world FL deployments such as . To highlight these challenges, we must first review the state-of-the-art in centralized DP training, where differentially private stochastic gradient descent (DP-SGD) is ubiquitous. It achieves optimal error for convex problems , and can also be applied to non-convex problems, including deep learning, where the privacy amplification offered by randomly subsampling data to form batches is critical for obtaining meaningful DP guarantees .

Attempts to combine FL and the above lines of DP research have been made previously; notably, extended the approach of to FL and user-level DP. However, these works and others in the area sidestep a critical issue: the DP guarantees require very specific sampling or shuffling schemes assuming, for example, that each client participates in each iteration with a fixed probability. While possible in theory, such schemes are incompatible with the practical constraints and design goals of cross-device FL protocols ; to quote , a comprehensive recent FL survey, “such a sampling procedure is nearly impossible in practice.”In cross-silo FL applications , an enumerated set of addressable institutions or data-silos participate in FL, and so explicit server-mediated subsampling or shuffling using existing techniques may be feasible. The fundamental challenge is that clients decide when they will be available for training and when they will check in to the server, and by design the server cannot index specific clients. In fact, it may not even know the size of the participating population.

Our work targets these challenges. Our primary goal is to provide strong central DP guarantees for the final model released by FL-like protocols, under the assumption of a trustedNotably, our guarantees are obtained by amplifying the privacy provided by local DP randomizers; we treat this use of local DP as an implementation detail in accomplishing the primary goal of central DP. As a byproduct, our approach offers (weaker) local DP guarantees even in the presence of an untrusted server. orchestrating server. This is accomplished by building upon recent work on amplification by shuffling and combining it with new analysis techniques targeting FL-specific challenges (e.g., client-initiated communications, non-addressable global population, and constrained client availability).

We propose the first privacy amplification analysis specifically tailored for distributed learning frameworks. At the heart of our result is a novel technique, called random check-in, that relies only on randomness independently generated by each individual client participating in the training procedure. We show that distributed learning protocols based on random check-ins can attain privacy gains similar to privacy amplification by subsampling/shuffling (see Table 1 for a comparison), while requiring minimal coordination from the server. While we restrict our exposition to distributed DP-SGD within the FL framework for clarity and concreteness (see Figure 1 for a schematic of one of our protocols), we note that the techniques used in our analyses are broadly applicable to any distributed iterative method and might be of interest in other applicationsIn particular, the Federated Averaging algorithm, which computes an update based on multiple local SGD steps rather than a single gradient, can immediately be plugged into our framework..

𝑖1\theta_{i+1} (or gradient accumulator if using minibatches). Contributions The main contributions of this paper can be summarized as follows:

We propose random check-ins, the first privacy amplification technique for distributed systems with minimal server-side overhead. We also instantiate three distributed learning protocols that use random check-ins, each addressing different natural constraints that arise in applications.

We provide formal privacy guarantees for our protocols, and show that random check-ins attain similar rates of privacy amplification as subsampling and shuffling while reducing the need for server-side orchestration. We also provide utility guarantees for one of our protocols in the convex case that match the optimal privacy/accuracy trade-offs for DP-SGD in the central setting .

As a byproduct of our analysis, we improve privacy amplification by shuffling on two fronts. For the case of $\varepsilon_{0}$-DP local randomizers, we improve the dependency of the final central DP $\varepsilon$ by a factor of $O(e^{0.5\varepsilon_{0}})$. Figure 2 provides a numerical comparison of the bound from with our bound; for typical parameter values this improvement allows us to provide similar privacy guarantees while reducing the number of required users by one order of magnitude. We also extend the analysis to the case of $(\varepsilon_{0},\delta_{0})$-DP local randomizers, including Gaussian randomizers that are widely used in practice.

Related work

Our work considers the paradigm of federated learning as a stylized example throughout the paper. We refer the reader to for an excellent overview of the state-of-the-art in federated learning, along with a suite of interesting open problems. There is a rich literature on studying differentially private ERM via DP-SGD . However, constraints such as limited availability in distributed settings restrict direct applications of existing techniques. There is also a growing line of works on privacy amplification by shuffling that focus on various ways in which protocols can be designed using trusted shuffling primitives. Lastly, privacy amplification by iteration is another recent advancement that can be applied in an iterative distributed setting, but it is limited to convex objectives.

Background and Problem Formulation

To formally introduce our notion of privacy, we first define neighboring data sets. We will refer to a pair of data sets $D,D^{\prime}\in\mathcal{D}^{n}$ as neighbors if $D^{\prime}$ can be obtained from $D$ by modifying one sample $d_{i}\in D$ for some $i\in[n]$.

A randomized algorithm $\mathcal{A}:\mathcal{D}^{n}\to\mathcal{S}$ is $(\varepsilon,\delta)$-differentially private if, for any pair of neighboring data sets $D,D^{\prime}\in\mathcal{D}^{n}$, and for all events $S\subseteq\mathcal{S}$ in the output range of $\mathcal{A}$, we have $\mathop{\mathbf{Pr}}[\mathcal{A}(D)\in S]\leq e^{\varepsilon}\cdot\mathop{\mathbf{Pr}}[\mathcal{A}(D^{\prime})\in S]+\delta$.

For meaningful central DP guarantees (i.e., when $n>1$), $\varepsilon$ is assumed to be a small constant, and $\delta\ll 1/n$. The case $\delta=0$ is often referred to as pure DP (in which case, we just write $\varepsilon$-DP). We shall also use the term approximate DP when $\delta>0$.

Adaptive differentially private mechanisms occur naturally when constructing complex DP algorithms, for e.g., DP-SGD. In addition to the dataset $D$, adaptive mechanisms also receive as input the output of other differentially private mechanisms. Formally, we say that an adaptive mechanism $\mathcal{A}:\mathcal{S}^{\prime}\times\mathcal{D}^{n}\to\mathcal{S}$ is $(\varepsilon,\delta)$-DP if the mechanism $\mathcal{A}(s^{\prime},\bullet)$ is $(\varepsilon,\delta)$-DP for every $s^{\prime}\in\mathcal{S}^{\prime}$.

Specializing Definition 2.1 to the case $n=1$ gives what we call a local randomizer, which provides a local DP guarantee. Local randomizers are the typical building blocks of local DP protocols where individuals privatize their data before sending it to an aggregator for analysis .

Problem Setup

Our results consider three different setups inspired by practical applications : (1) The server uses $m\ll n$ time slots, where at most one user’s update is used in each slot, for a total of $m/b$ minibatch SGD iterations. It is assumed all $n$ users are available for the duration of the protocol, but the server does not have enough bandwidth to process updates from every user (Section 3.1); (2) The server uses $m\approx n/b$ time slots, and all $n$ users are available for the duration of the protocol (Section 4.1). On average, $b$ users contribute updates to each time slot, and so, we take $m$ minibatch SGD steps; (3) As with (2), but each user is only available during a small window of time relative to the duration of the protocol (Section 4.2).

Distributed Learning with Random Check-Ins

This section presents the random check-ins technique for privacy amplification in the context of distributed learning. We formally define the random check-ins procedure, describe a fully distributed DP-SGD protocol with random check-ins, and analyze its privacy and utility guarantees.

Consider the distributed learning setup described in Section 2 where each client is willing to participate in the training procedure as long as their data remains private. To boost the privacy guarantees provided by the local randomizer $\mathcal{A}_{ldp}$, we will let clients volunteer their updates at a random time slot of their choosing. This randomization has a similar effect on the uncertainty about the use of an individual’s data on a particular update as the one provided by uniform subsampling or shuffling. We formalize this concept using the notion of random check-in, which can be informally expressed as a client in a distributed iterative learning framework randomizing their instant of participation, and determining with some probability whether to participate in the process at all.

Let $\mathcal{A}$ be a distributed learning protocol with $m$ check-in time slots. For a set $R_{j}\subseteq[m]$ and probability $p_{j}\in$, client $j$ performs an $(R_{j},p_{j})$-check-in in the protocol if with probability $p_{j}$ she requests the server to participate in $\mathcal{A}$ at time step $I\xleftarrow{u.a.r.}R_{j}$, and otherwise abstains from participating. If $p_{j}=1$, we alternatively denote it as an $R_{j}$-check-in.

2 Privacy Analysis

From a privacy standpoint, Algorithm 1 shares an important pattern with DP-SGD: each model update uses noisy gradients obtained from a random subset of the population. However, there exist two key factors that make the privacy analysis of our protocol more challenging than the existing analysis based on subsampling and shuffling. First, unlike in the case of uniform sampling where the randomness in each update is independent, here there is a correlation induced by the fact that clients that check-in into one step cannot check-in into a different step. Second, in shuffling there is also a similar correlation between updates, but there we can ensure each update uses the same number of datapoints, while here the server does not control the number of clients that will check-in into each individual step. Nonetheless, the following result shows that random check-ins provides a factor of privacy amplification comparable to these techniques.

Suppose $\mathcal{A}_{ldp}$ is an $\varepsilon_{0}$-DP local randomizer. Let $\mathcal{A}_{fix}:\mathcal{D}^{n}\rightarrow\Theta^{m}$ be the protocol from Algorithm 1 with check-in probability $p_{j}=p_{0}$ and check-in window $R_{j}=[m]$ for each client $j\in[n]$. For any $\delta\in(0,1)$, algorithm $\mathcal{A}_{fix}$ is $\left(\varepsilon,\delta\right)$-DP with $\varepsilon=p_{0}(e^{\varepsilon_{0}}-1)\sqrt{\frac{2e^{\varepsilon_{0}}\log{(1/\delta)}}{m}}+\frac{p_{0}^{2}e^{\varepsilon_{0}}(e^{\varepsilon_{0}}-1)^{2}}{2m}$. In particular, for $\varepsilon_{0}\leq 1$ and $\delta\leq 1/100$, we get $\varepsilon\leq 7p_{0}\varepsilon_{0}\sqrt{\frac{\log(1/\delta)}{m}}$. Furthermore, if $\mathcal{A}_{ldp}$ is $(\varepsilon_{0},\delta_{0})$-DP with $\delta_{0}\leq\frac{(1-e^{-\varepsilon_{0}})\delta_{1}}{4e^{\varepsilon_{0}}\left(2+\frac{\ln(2/\delta_{1})}{\ln(1/(1-e^{-5\varepsilon_{0}}))}\right)}$, then $\mathcal{A}_{fix}$ is $(\varepsilon^{\prime},\delta^{\prime})$-DP with $\varepsilon^{\prime}=\frac{p_{0}^{2}e^{8\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)^{2}}{2m}+p_{0}(e^{8\varepsilon_{0}}-1)\sqrt{\frac{2e^{8\varepsilon_{0}}\log{(1/\delta)}}{m}}$ and $\delta^{\prime}=\delta+m(e^{\varepsilon^{\prime}}+1)\delta_{1}$.

We can always increase privacy in the above statement by decreasing $p_{0}$. However, this will also increase the number of dummy updates, which suggests choosing $p_{0}=\Theta(m/n)$. With such a choice, we obtain an amplification factor of $\sqrt{m}/n$. Critically, however, exact knowledge of the population size is not required to have a precise DP guarantee above.

Remark 2

At first look, the amplification factor of $\sqrt{m}/n$ may appear stronger than the typical $1/\sqrt{n}$ factor obtained via uniform subsampling/shuffling. Note that one run of our technique provides $m$ updates (as opposed to $n$ updates via the other methods). When the server has sufficient capacity, we can set $m=n$ to recover a $1/\sqrt{n}$ amplification. The primary advantage of our approach is that we can benefit from amplification in terms of $n$ even if only a much smaller number of updates are actually processed. We can also extend our approach to recover the $1/\sqrt{n}$ amplification even when the server is rate limited ($p_{0}=m/n$), by repeating the protocol $\mathcal{A}_{fix}$ adaptively $n/m$ times to get Corollary 3.3 from Theorem 3.2 and applying advanced composition for DP .

Comparison to Existing Privacy Amplification Techniques

Table 1 provides a comparison of the bound in Corollary 3.3 to other existing techniques, for performing one epoch of training (i.e., use one update from each client). Note that for this comparison, we assume that $\varepsilon_{0}>1$, since for $\varepsilon_{0}\leq 1$ all the shown amplification bounds can be written as $O\left(\varepsilon_{0}/\sqrt{n}\right)$. “None” denotes a naïve scheme (with no privacy amplification) where each client is used exactly once in any arbitrary order. Also, note that in general, the guarantees via privacy amplification by subsampling/shuffling apply only under the assumption of complete participation availabilityBy a complete participation availability for a client, we mean that the client should be available to participate when requested by the server for any time step(s) of training. of each client. Thus, they define the upper limits of achieving such amplifications. Also, note that even though the bound in Corollary 3.3 appears better than amplification via shuffling, our technique does include dummy updates which do not occur in the other techniques. For linear optimization problems, it is easy to see that our technique will add a factor of $e$ more noise as compared to the other two privacy amplification techniques at the same privacy level.

Proof Sketch for Theorem 3.2

3 Utility Analysis

For algorithm $\mathcal{A}_{fix}:\mathcal{D}^{n}\rightarrow\Theta^{m}$ described in Theorem 3.2, the expected number of dummy updates performed by the server is at most $\left(m\left(1-\frac{p_{0}}{m}\right)^{n}\right)$. For $c>0$ if $p_{0}=\frac{cm}{n}$, we get at most $\frac{m}{e^{c}}$ expected dummy updates.

We now instantiate our amplification theorem (Theorem 3.2) in the context of differentially private empirical risk minimization (ERM). For convex ERMs, we will show that DP-SGD in conjunction with our privacy amplification theorem (Theorem 3.2) is capable of achieving the optimal privacy/accuracy trade-offs .

Remark 3

Note that as $m\to n$, it is easy to see for $p_{0}=\Omega\left(\frac{m}{n}\right)$ that Theorem 3.5 achieves the optimal population risk trade-off .

Variations: Thrifty Updates, and Sliding Windows

This section presents two variants of the main protocol from the previous section. The first variant makes a better use of the updates provided by each user at the expense of a small increase in the privacy cost. The second variant allows users to check-in into a sliding window to model the case where different users might be available during different time windows.

Now, we present a variant of Algorithm 1 which, at the expense of a mild increase in the privacy cost, removes the need for dummy updates, and for discarding all but one of the clients checked-in at every time step. The server-side protocol of this version is given in Algorithm 2 (the client-side protocol is identical as Algorithm 1). Note that here, if no client checked-in at some step $i\in[m]$, the server simply skips the update. Furthermore, if at some step multiple clients checked in, the server requests gradients from all the clients, and performs a model update using the average of the submitted noisy gradients.

These changes have the obvious advantage of reducing the noise in the model coming from dummy updates, and increasing the algorithm’s data efficiency by utilizing gradients provided by all available clients. The corresponding privacy analysis becomes more challenging because (1) the adversary gains information about the time steps where no clients checked-in, and (2) the server uses the potentially non-private count $|S_{i}|$ of clients checked-in at time $i$ when performing the model update. Nonetheless, we show that the privacy guarantees of Algorithm 2 are similar to those of Algorithm 1 with an additional $O(e^{3\varepsilon_{0}/2})$ factor, and the restriction of non-collusion among the participating clients. For simplicity, we only analyze the case where each client has check-in probability $p_{j}=1$.

Suppose $\mathcal{A}_{ldp}$ is an $\varepsilon_{0}$-DP local randomizer. Let $\mathcal{A}_{avg}:\mathcal{D}^{n}\rightarrow\Theta^{m}$ be the protocol from Algorithm 2 performing $m$ averaged model updates with check-in probability $p_{j}=1$ and check-in window $R_{j}=[m]$ for each user $j\in[n]$. Algorithm $\mathcal{A}_{avg}$ is $\left(\varepsilon,\delta+\delta_{2}\right)$-DP with

where $\varepsilon_{1}=\sqrt{\frac{1}{n}+\frac{1}{m}}+\sqrt{\frac{\log(1/\delta_{2})}{n}}$. In particular, for $\varepsilon_{0}\leq 1$ we get $\varepsilon=O(\varepsilon_{0}/\sqrt{m})$. Furthermore, if $\mathcal{A}_{ldp}$ is $(\varepsilon_{0},\delta_{0})$-DP with $\delta_{0}\leq\frac{(1-e^{-\varepsilon_{0}})\delta_{1}}{4e^{\varepsilon_{0}}\left(2+\frac{\ln(2/\delta_{1})}{\ln(1/(1-e^{-5\varepsilon_{0}}))}\right)}$, then $\mathcal{A}_{avg}$ is $(\varepsilon^{\prime},\delta^{\prime})$-DP with $\varepsilon^{\prime}=\frac{e^{32\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)^{2}\varepsilon_{1}^{2}}{2}+e^{16\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)\varepsilon_{1}\sqrt{2\log(1/\delta)}$ and $\delta^{\prime}=\delta+\delta_{2}+m(e^{\varepsilon^{\prime}}+1)\delta_{1}$.

Next, we provide a utility guarantee for $\mathcal{A}_{avg}$ in terms of the excess population risk for convex ERMs (similar to Theorem 3.5).

2 Random Check-Ins with a Sliding Window

The second variant we consider removes the need for all clients to be available throughout the training period. Instead, we assume that the training period comprises of $n$ time steps, and each client $j\in[n]$ is only available during a window of $m$ time steps. Clients perform a random check-in to provide the server with an update during their window of availability. For simplicity, we assume clients wake up in order, one every time step, so client $j\in[n]$ will perform a random check-in within the window $R_{j}=\{j,\ldots,j+m-1\}$. The server will perform $n-m+1$ updates starting at time $m$ to provide a warm-up period where the first $m$ clients perform their random check-ins.

Suppose $\mathcal{A}_{ldp}$ is an $\varepsilon_{0}$-DP local randomizer. Let $\mathcal{A}_{sldw}:\mathcal{D}^{n}\rightarrow\Theta^{n-m+1}$ be the distributed algorithm performing $n$ model updates with check-in probability $p_{j}=1$ and check-in window $R_{j}=\{j,\ldots,j+m-1\}$ for each user $j\in[n]$. For any $m\in[n]$, algorithm $\mathcal{A}_{sldw}$ is $\left(\varepsilon,\delta\right)$-DP with $\varepsilon=\frac{e^{\varepsilon_{0}}(e^{\varepsilon_{0}}-1)^{2}}{2m}+(e^{\varepsilon_{0}}-1)\sqrt{\frac{2e^{\varepsilon_{0}}\log{(1/\delta)}}{m}}$. For $\varepsilon_{0}\leq 1$ and $\delta\leq 1/100$, we get $\varepsilon\leq 7\varepsilon_{0}\sqrt{\frac{\log(1/\delta)}{m}}$. Furthermore, if $\mathcal{A}_{ldp}$ is $(\varepsilon_{0},\delta_{0})$-DP with $\delta_{0}\leq\frac{(1-e^{-\varepsilon_{0}})\delta_{1}}{4e^{\varepsilon_{0}}\left(2+\frac{\ln(2/\delta_{1})}{\ln(1/(1-e^{-5\varepsilon_{0}}))}\right)}$, then $\mathcal{A}_{sldw}$ is $(\varepsilon^{\prime},\delta^{\prime})$-DP with $\varepsilon^{\prime}=\frac{e^{8\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)^{2}}{2m}+(e^{8\varepsilon_{0}}-1)\sqrt{\frac{2e^{8\varepsilon_{0}}\log{(1/\delta)}}{m}}$ and $\delta^{\prime}=\delta+m(e^{\varepsilon^{\prime}}+1)\delta_{1}$.

We can always increase privacy in the statement above by increasing $m$. However, that also increases the number of clients who do not participate in training because their scheduled check-in time is before the process begins, or after it terminates. Moreover, the number of empty slots where the server introduces dummy updates will also increase, which we would want to minimize for good accuracy. Thus, $m$ introduces a trade-off between accuracy and privacy.

For algorithm $\mathcal{A}_{sldw}:\mathcal{D}^{n}\rightarrow\Theta^{n-m+1}$ described in Theorem 4.3, the expected number of dummy gradient updates performed by the server is at most $(n-m+1)/e$.

Improvements to Amplification via Shuffling

Here, we provide an improvement on privacy amplification by shuffling. This is obtained using two technical lemmas (deferred to the supplementary material) to tighten the analysis of amplification by swapping, a central component in the analysis of amplification by shuffling given in .

Let $\mathcal{A}^{(i)}:\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}\times\mathcal{D}\rightarrow\mathcal{S}^{(i)}$, $i\in[n]$, be a sequence of adaptive $\varepsilon_{0}$-DP local randomizers. Let $\mathcal{A}_{sl}:\mathcal{D}^{n}\rightarrow\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(n)}$ be the algorithm that given a dataset $D=(d_{1},\ldots,d_{n})\in\mathcal{D}^{n}$ samples a uniform random permutation $\pi$ over $[n]$, sequentially computes $s_{i}=\mathcal{A}^{(i)}(s_{1:i-1},d_{\pi(i)})$ and outputs $s_{1:n}$. For any $\delta\in(0,1)$, algorithm $\mathcal{A}_{sl}$ satisfies $\left(\varepsilon,\delta\right)$-DP with $\varepsilon=\frac{e^{3\varepsilon_{0}}(e^{\varepsilon_{0}}-1)^{2}}{2n}+e^{3\varepsilon_{0}/2}(e^{\varepsilon_{0}}-1)\sqrt{\frac{2\log{(1/\delta)}}{n}}$. Furthermore, if $\mathcal{A}^{(i)}$, $i\in[n]$, is $(\varepsilon_{0},\delta_{0})$-DP with $\delta_{0}\leq\frac{(1-e^{-\varepsilon_{0}})\delta_{1}}{4e^{\varepsilon_{0}}\left(2+\frac{\ln(2/\delta_{1})}{\ln(1/(1-e^{-5\varepsilon_{0}}))}\right)}$, then $\mathcal{A}_{sl}$ satisfies $(\varepsilon^{\prime},\delta^{\prime})$-DP with $\varepsilon^{\prime}=\frac{e^{24\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)^{2}}{2n}+e^{12\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)\sqrt{\frac{2\log{(1/\delta)}}{n}}$ and $\delta^{\prime}=\delta+n(e^{\varepsilon^{\prime}}+1)\delta_{1}$.

For comparison, the guarantee in [19, Theorem 7] in the case $\delta_{0}=0$ results in

Conclusion

Our work highlights the fact that proving DP guarantees for distributed or decentralized systems can be substantially more challenging than for centralized systems, because in a distributed setting it becomes much harder to precisely control and characterize the randomness in the system, and this precise characterization and control of randomness is at the heart of DP guarantees. Specifically, production FL systems do not satisfy the assumptions that are typically made under state-of-the-art privacy accounting schemes, such as privacy amplification via subsampling. Without such accounting schemes, service providers cannot provide DP statements with small $\varepsilon$’s. This work, though largely theoretical in nature, proposes a method shaped by the practical constraints of distributed systems that allows for rigorous privacy statements under realistic assumptions.

Nevertheless, there is more to do. Our theorems are sharpest in the high-privacy regime (small $\varepsilon$’s), which may be too conservative to provide sufficient utility for some applications. While significantly relaxed from previous work, our assumptions will still not hold in all real-world systems. Thus, we hope this work encourages further collaboration between distributed systems and DP theory researchers in establishing protocols that address the full range of possible systems constraints as well as improving the full breadth of the privacy vs. utility Pareto frontier.

Acknowledgements

The authors would like to thank Vitaly Feldman for suggesting the idea of privacy accounting in DP-SGD via shuffling, and for help in identifying and fixing a mistake in the way a previous version of this paper handled $(\varepsilon_{0},\delta_{0})$-DP local randomizers.

References

Appendix A Omitted Results and Proofs

Let $\mathcal{A}_{ldp}:\mathcal{D}\rightarrow\mathcal{S}$ be an $\varepsilon_{0}$-DP local randomizer. For $D=(d_{1},\ldots,d_{m})\in\mathcal{D}^{m},q\in(0,1)$, and $k\in[m]$, define $\mathsf{BiasedSampling}_{q}(D,k)$ to return $d_{k}$ with probability $q$, and a sample from an arbitrary distribution over $D\setminus\{d_{k}\}$ with probability $1-q$. For any $k\in[m]$ and any set of outcomes $S\subseteq\mathcal{S}$, we have

Fix a set of outcomes $S\subseteq\mathcal{S}$. By $\varepsilon_{0}$-LDP of $\mathcal{A}_{ldp}$, for any $d,d^{\prime}\in\mathcal{D}$, we get

Now, for dataset $D=(d_{1},\ldots,d_{m})\in\mathcal{D}^{n}$ and $k\in[m]$, we have:

where the third equality follows as $\mathop{\mathbf{Pr}}[d=d_{k}]=q$, and the first inequality follows using inequality 1, and the fourth equality follows as $\sum\limits_{j\neq k}\mathop{\mathbf{Pr}}[d=d_{j}]=1-q$. ∎

Let $\mathcal{A}^{(1)},\ldots,\mathcal{A}^{(k)}$ be mechanisms of the form $\mathcal{A}^{(i)}:\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}\times\mathcal{D}\rightarrow\mathcal{S}^{(i)}$. Suppose there exist constants $a>0$ and $b\in(0,1)$ such that each $\mathcal{A}^{(i)}$ is $\varepsilon_{i}$-DP with $\varepsilon_{i}\leq\log\left(1+\frac{a}{k-b(i-1)}\right)$. Then, for any $\delta\in(0,1)$, the $k$-fold adaptive composition of $\mathcal{A}^{(1)},\ldots,\mathcal{A}^{(k)}$ is $\left(\varepsilon,\delta\right)$-DP with $\varepsilon=\frac{a^{2}}{2k(1-b)}+\sqrt{\frac{2a^{2}\log{(1/\delta)}}{k(1-b)}}$.

We start by applying the heterogeneous advanced composition for DP for the sequence of mechanisms $\mathcal{A}_{1},\ldots,\mathcal{A}_{k}$ to get $\left(\varepsilon,\delta\right)$-DP for the composition, where

Let us start by bounding the second term in equation 2. First, observe that:

where the first inequality follows from $\log(1+x)\leq x$.

where the second equality follows as we have $\int\frac{1}{(c-dx)^{2}}dx=\frac{1}{cd-d^{2}x}$.

Next, we bound the first term in equation 2 as follows:

where the first inequality follows from $\log(1+x)\leq x$, and the last inequality follows from inequality 4.

Using inequalities 3, 4 and 5 in equation 2, we get that the $k$-fold adaptive composition of $\mathcal{A}_{1},\ldots,\mathcal{A}_{k}$ satisfies $\left(\varepsilon,\delta\right)$-DP, for $\varepsilon=\frac{a^{2}}{2k(1-b)}+\sqrt{\frac{2a^{2}\log{(1/\delta)}}{k(1-b)}}$. ∎

Setting $p_{0}=\frac{m}{n}$ in $\mathcal{A}_{fix}$, we get from Theorem 3.2 that $\beta\in(0,1)$, algorithm $\mathcal{A}_{fix}$ satisfies $(\varepsilon_{1},\beta)$-DP for

where the inequality follows since $n\geq(e^{\varepsilon_{0}}-1)\sqrt{me^{\varepsilon_{0}}}$.

Now, using inequality 6 and applying advanced composition to $\frac{n}{m}$ repetitions of $\mathcal{A}_{fix}$, we get $\left(\varepsilon,\frac{n\beta}{m}+\delta\right)$-DP, for

Since $\varepsilon_{0}\leq\frac{2\log{\left(n/8\sqrt{m}\right)}}{3}$, we have that $\varepsilon_{1}\leq\frac{1}{2}$, and thus, $\left(e^{\varepsilon_{1}}-1\right)\leq\frac{3\varepsilon_{1}}{2}$. Therefore, we get from inequality 7 that

For $i\in[m]$, define an indicator random variable $E_{i}$ that indicates if $S_{i}$ is empty. Note that the server performs a dummy gradient update for instance $i\in[n]$ if and only if $S_{i}$ is empty (or, in other words, $E_{i}=1$). Next, for $j\in[n]$, let $I_{j}$ denote the index that user $j$ in Algorithm $\mathcal{A}_{fix}$ performs her $(R_{j},p_{j})$-check-in into, where $R_{j}=[m]$ and $p_{j}=p_{0}$. Thus, for index $i\in[m]$, we have

where the second equality follows since the check-ins for each user are independent of the others, and each user abstains from participating w.p. $(1-p_{0})$.

Thus, for the expected number of dummy gradient updates, we have:

If $p_{0}=\frac{cm}{n}$ for $c>0$, from equation 8 we get

where the inequality follows as $\left(1-\frac{a}{b}\right)^{b}\leq e^{-a}$ for $b>1,|a|\leq b$. ∎

To be able to directly apply [32, Theorem 2], our technique $\mathcal{A}_{fix}$ needs to satisfy two conditions: i) each model update should be an unbiased estimate of the gradient, and ii) a bound on the expected $L_{2}$-norm of the gradient. Notice that in $\mathcal{A}_{fix}$, every client $j\in[n]$ performs a $([m],p_{0})$-check-in. This is analogous to a bins-and-balls setting where $n$ balls are thrown, each with probability $p_{0}$, into $m$ bins. Thus, for each update step $i\in[m]$, the number of clients checking-in for this step (i.e., $|S_{i}|$ in the notation of Algorithm 1) can be approximated by an independent Poisson random variable $Y_{i}$ with mean $np_{0}/m$, using Poisson approximation , as follows:

Optimizing the learning rate to be $\eta_{i}=\frac{R\left(1-2e^{-np_{0}/m}\right)}{\sqrt{\left(p\sigma^{2}+L^{2}\right)i}}$ gives the statement of the theorem. ∎

Optimizing the learning rate to be $\eta_{i}=\frac{R\sqrt{n}}{\sqrt{\left(mp\sigma^{2}+nL^{2}\right)i}}$ gives the statement of the theorem.

The result now follows from observing that

In Algorithm $\mathcal{A}_{sldw}$, for $i\in[n-m+1]$, we have

For $i\in[n]$, define an indicator random variable $E_{i}$ that indicates if $S_{i}$ is empty. Note that the server performs a dummy gradient update for instance $i\in[n]$ if and only if $S_{i}$ is empty (or, in other words, $E_{i}=1$). Next, for $j\in[m]$, let $I_{j}$ denote the index that user $j$ in Algorithm $\mathcal{A}_{fix}$ performs her $R_{j}$-check-in into, where $R_{j}=\{j,\ldots,j+m-1\}$. Thus, for index $i\in\{m,\ldots,n-m+1\}$, we have

where the second equality follows since the check-ins for each user are independent of the others, and the inequality follows as $\left(1-\frac{a}{b}\right)^{b}\leq e^{-a}$ for $b>1,|a|\leq b$.

Thus, for the expected number of dummy gradient updates, we have:

where the inequality follows from inequality 9. ∎

We will first prove the privacy guarantee of $\mathcal{A}_{fix}$ (Algorithm 1) by reducing it to algorithm $\mathcal{A}_{rep}$ (Algorithm 3) that starts by swapping the first element in the dataset by a given replacement element, randomly chooses a position in the dataset to get replaced by the original first element with a given probability, and then carries out DP-SGD with the local randomizer. W.l.o.g., for simplicity we will define $\mathcal{A}_{rep}$ to update the model for 1-sized minibatches (i.e., update at every time step). It is easy to extend to $b$-sized minibatch updates by accumulating the gradient updates for every $b$ steps and then updating the model.

For the proofs that follow, it will be convenient to define additional notation for denoting distance between distributions. Given 2 distributions $\mu$ and $\mu^{\prime}$, we denote them as $\mu\approxeq_{(\varepsilon,\delta)}\mu^{\prime}$ if they are $(\varepsilon,\delta)$-DP close, i.e., if for all measurable outcomes $S$, we have

We start by proving the privacy guarantee of $\mathcal{A}_{rep}$ for the case where the local randomizer $\mathcal{A}_{ldp}$ is $\varepsilon_{0}$-DP, i.e., for the case where $\delta_{0}=0$. Let us denote the output sequence of $\mathcal{A}_{rep}$ by $Z_{2},Z_{3},\ldots,Z_{m+1}$. Note that $Z_{2:m+1}$ can be seen as the output of a sequence of $m$ algorithms with conditionally independent randomness: $\mathcal{B}^{(i)}$ for $i\in[m]$ as follows. On input $\theta_{2:i}$ and $D$, $\mathcal{B}^{(i)}$ outputs a random sample from the distribution of $Z_{i+1}|Z_{2:i}=\theta_{2:i}$. The outputs of $\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(i-1)}$ are given as input to $\mathcal{B}^{(i)}$. Therefore, in order to upper bound the privacy parameters of $\mathcal{A}_{rep}$, we analyze the privacy parameters of $\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(m)}$ and apply the heterogeneous advanced composition for DP .

For $i\in[m]$, we observe that $\mu_{0}=\mu_{0}^{\prime}$, since in both cases the output is generated by $\mathcal{A}_{ldp}(\theta_{1},d_{r})$ for $i=1$, and $\mathcal{A}_{ldp}(\theta_{2:i};d_{i})$ for $i\geq 2$. W.l.o.g. assume that $q_{i}\geq q_{i}^{\prime}$. Thus, we can shift $(q_{i}-q_{i}^{\prime})w_{i}$ mass from the first component of the mixture in $\mu^{\prime}$ to the second component to obtain

This shows that $\mu$ and $\mu^{\prime}$ are overlapping mixtures . Now, $\varepsilon_{0}$-LDP of $\mathcal{A}_{ldp}$ implies $\mu_{0}\approxeq_{(\varepsilon_{0},0)}\mu_{1}$ and $\mu_{0}^{\prime}\approxeq_{(\varepsilon_{0},0)}\mu_{1}^{\prime}$. Moreover, $\varepsilon_{0}$-LDP of $\mathcal{A}_{ldp}$ also implies $\mu_{1}\approxeq_{(\varepsilon_{0},0)}\mu_{1}^{\prime}$, so by the joint convexity of the relation $\approxeq_{(\varepsilon_{0},0)}$ we also have $\mu_{1}\approxeq_{(\varepsilon_{0},0)}\mu_{1}^{\prime\prime}$. Thus, we can apply Advanced Joint Convexity of overlapping mixtures (Theorem 2 in ) to get that

We now claim that $q_{i}\leq\frac{e^{\varepsilon_{0}}}{i-1+e^{\varepsilon_{0}}(m-i+1)}$. Observe that for each $D^{*}\in\{D,D^{\prime}\}$, conditioning on $T=i$ reduces $\mathcal{A}_{rep}$ to running $\mathcal{A}_{ldp}$ on $\sigma_{i}(D^{*})$. Note that for $j<i$, we have that $\sigma_{i}(D^{*})[1:i-1]$ differs from $\sigma_{j}(D^{*})[1:i-1]$ in at most 1 position, and for $j>i$, we have $\sigma_{i}(D^{*})[1:i-1]=\sigma_{j}(D^{*})[1:i-1]$. Since $\mathop{\mathbf{Pr}}[j\geq i]=\frac{m-i+1}{m}$, by setting $q=\frac{m-i+1}{m}$ in Lemma A.1, we get that

This immediately implies our claim, since we have

where the inequality follows from inequality 11, and as $\mathop{\mathbf{Pr}}[T=i]=\frac{1}{m}$.

Substituting the value of $q_{i}$ in equation 10, and using the fact that $w_{i}\leq w_{max}$, we get that for each $i\in[m]$, algorithm $\mathcal{B}^{(i)}$ is $\left(\varepsilon_{i},0\right)$-DP at index 1, where $\varepsilon_{i}=\log\left(1+\frac{w_{max}e^{\varepsilon_{0}}(e^{\varepsilon_{0}}-1)}{i-1+e^{\varepsilon_{0}}(m-i+1)}\right)$. This can alternatively be written as $\varepsilon_{i}=\log\left(1+\frac{w_{max}(e^{\varepsilon_{0}}-1)}{m-(i-1)\frac{e^{\varepsilon_{0}}-1}{e^{\varepsilon_{0}}}}\right)$, and using Lemma A.2 for the sequence of mechanisms $\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(m)}$ by setting $a=w_{max}(e^{\varepsilon_{0}}-1)$, $b=\frac{e^{\varepsilon_{0}}-1}{e^{\varepsilon_{0}}}$, and $k=m$, we get that algorithm $\mathcal{A}_{rep}$ satisfies $\left(\varepsilon,\delta\right)$-DP at index 1, for $\varepsilon=\frac{w_{max}^{2}e^{\varepsilon_{0}}(e^{\varepsilon_{0}}-1)^{2}}{2m}+w_{max}(e^{\varepsilon_{0}}-1)\sqrt{\frac{2e^{\varepsilon_{0}}\log{(1/\delta)}}{m}}$.

Now, for the above bound, if $\varepsilon_{0}\leq 1$ and $\delta\leq 1/4$, we get that

where the first inequality follows since $e^{0.5\varepsilon_{0}}(e^{\varepsilon_{0}}-1)\leq 3\varepsilon_{0}$ for $\varepsilon_{0}\leq 1$, and the second inequality follows since $\frac{3w_{max}\varepsilon_{0}}{2\sqrt{m}}\leq\sqrt{\frac{\log{\frac{1}{\delta}}}{2}}$ for $\delta\leq 1/100$.

Now, we prove the privacy guarantee of $\mathcal{A}_{rep}$ for the more general case where for each $i\in[m]$, the local randomizer $\mathcal{A}_{ldp}$ is $(\varepsilon_{0},\delta_{0})$-DP. To upper bound the privacy parameters of $\mathcal{A}_{rep}$, we modify the local randomizer to satisfy pure DP, apply the previous analysis, and then account for the difference between the protocols with original and modified randomizers using the total variation distance.

Now, we are ready to prove Theorems 3.2 and 4.3.

Let $D$ and $D^{\prime}$ be 2 datasets of $n$ users that differ in a user at some index $i^{*}\in[n]$. Algorithm $\mathcal{A}_{fix}$ can be alternatively seen as follows. The server starts by initializing $F=[0^{p}]^{m}$, weights $W=^{m}$, and for $i\in[m]$, set $S_{i}=\phi$. For each user $j\in[n]$ s.t. $j\neq i^{*}$, user $j$ performs a random check-in along with some additional operations. She first samples $I_{j}$ u.a.r. from $[m]$, and w.p. $p_{0}$ does the following: she requests the server for model at index $I_{j}$ (and gets inserted into set $S_{I_{j}}$ at the server). She also updates $F[I_{j}]=d_{j}$ with probability $W[I_{j}]$, and sets $W[I_{j}]=\frac{W[I_{j}]}{W[I_{j}]+1}$. Next, the server runs $\mathcal{A}_{rep}$ on input dataset $\pi^{*}(D)=(d_{i^{*}},F[2:m])$, with the replacement element $F$, initial model $\theta_{1}$, and weight parameters set to $W^{\prime}[1:m]$, where $W^{\prime}[i]=W[i]\cdot p_{0}$.

First, notice that in the alternative strategy above, for each of the weights $W[i],i\in[m]$, it always holds that $W[i]=\frac{1}{\left|S_{i}\right|}$. Thus, each weight $W[i],i\in[m]$ is updated to simulate reservoir sampling of size 1 in slot $F[i]$. In other words, updating $F[i]=d$ with probability $W[i]$ for an element $d$ is equivalent to $F[j]\xleftarrow{u.a.r.}S_{i}$, where $S_{i}$ is the set containing $d$ and all the elements previously considered for updating $S_{i}$. As a result, since the first element in $\mathcal{A}_{rep}$ performs a random replacement with weights set to $W^{\prime}[1:m]$ for its input dataset, it is easy to see that performing a concurrent random check-in for user $i^{*}$ (as in Algorithm 1) is equivalent to performing a random replacement for her after the check-ins of all the other users.

From our construction, we know that datasets $\pi^{*}(D)$ and $\pi^{*}(D^{\prime})$, which are each of length $m$, differ only in the element with index 1. Moreover, in the alternative strategy above, note that the weights $W^{\prime}[1:m]$ and the replacement element $F$ input to $\mathcal{A}_{rep}$ are independent of the data of user $i^{*}$ in the original dataset. Therefore, in the case $\delta_{0}=0$, using Theorem A.4 and setting $w_{max}=p_{0}$, we get $\mathcal{A}_{rep}(\pi^{*}(D))\approxeq_{\varepsilon,\delta}\mathcal{A}_{rep}(\pi^{*}(D^{\prime}))$ at index 1, for $\varepsilon=\frac{p^{2}e^{\varepsilon_{0}}(e^{\varepsilon_{0}}-1)^{2}}{2m}+\frac{p(e^{\varepsilon_{0}}-1)\sqrt{2e^{\varepsilon_{0}}\log{(1/\delta)}}}{m}$, which implies $\mathcal{A}_{dist}(D)\approxeq_{\varepsilon,\delta}\mathcal{A}_{dist}(D^{\prime})$. Consequently, it implies $\varepsilon\leq 7p_{0}\varepsilon_{0}\sqrt{\frac{\log(1/\delta)}{m}}$ for $\varepsilon_{0}\leq 1$ and $\delta\leq 1/100$.

The case $\delta_{0}>0$ follows from the same reduction using the corresponding setting of Theorem A.4. ∎

We proceed similar to the proof of Theorem 3.2. Let $D$ and $D^{\prime}$ be 2 datasets of $n$ users that differ in a user at some index $i^{*}\in[n]$. Algorithm $\mathcal{A}_{sldw}$ can be alternatively seen as follows. The server starts by initializing $F=[0^{p}]^{n-m+1}$, weights $W=^{n-m+1}$, and for $j\in\{m,\ldots,n\}$, set $S_{j}=\phi$. For each user $j\in[n]$ s.t. $j\neq i^{*}$, user $j$ performs a random check-in along with some additional operations. She first samples $I_{j}$ u.a.r. from $\{j,\ldots,j+m-1\}$, requests the server for model at index $I_{j}$ (and gets inserted into set $S_{I_{j}}$ at the server). She also updates $F[I_{j}]=d_{j}$ with probability $W[I_{j}]$, and sets $W[I_{j}]=\frac{W[I_{j}]}{W[I_{j}]+1}$.

Now, the server runs its loop until it releases $i^{*}-1$ outputs. Next, the server runs $\mathcal{A}_{rep}$ on input dataset $\pi^{*}(D)=(d_{i^{*}},F[i^{*}+1:i^{*}+m])$, with weight parameters set to $W[i^{*}:i^{*}+m]$, initializing model $\theta_{i^{*}}$, and the replacement element $F[i^{*}]$. Lastly, the server releases the last $(n-(i^{*}+m)+1)$ outputs of $\mathcal{A}_{sldw}$ using $F[i^{*}+m+1:n]$ and the local randomizer $\mathcal{A}_{ldp}$.

First, notice that in the alternative strategy above, for each of the weights $W[i],i\in[n]$, it always holds that $W[i]=\frac{1}{\left|S_{i}\right|}$. Thus, each weight $W[i],i\in[n]$ is updated to simulate reservoir sampling of size 1 in slot $F[i]$. In other words, updating $F[i]=d$ with probability $W[i]$ for an element $d$ is equivalent to $F[i]\xleftarrow{u.a.r.}S_{i}$, where $S_{i}$ is the set containing $z$ and all the elements previously considered for updating $S_{i}$. As a result, since the first element in $\mathcal{A}_{rep}$ performs a random replacement for its input dataset (which doesn’t include $F_{1:i^{*}-1}\bigcup F_{i^{*}+m+1:n}$ in the alternative strategy above), it is easy to see that sequentially performing a random check-in for user $i^{*}$ (as in Algorithm 1) is equivalent to performing a random replacement for her after the check-ins of all the other users and releasing the first $i^{*}-1$ outputs of $\mathcal{A}_{sldw}$.

From our construction, we know that datasets $\pi^{*}(D)$ and $\pi^{*}(D^{\prime})$, which are each of length $m$, differ only in the element with index 1. Moreover, in the alternative strategy above, note that the weights $W[i^{*}:i^{*}+m]$, initializing model $\theta_{i^{*}}$ and the replacement element $F[i^{*}]$ input to $\mathcal{A}_{rep}$ are independent of the data of user $i^{*}$ in the original dataset. Therefore, using Theorem A.4 and setting $w_{max}=1$, we get $\mathcal{A}_{rep}(\pi^{*}(D))\approxeq_{\varepsilon,\delta+m\delta_{0}}\mathcal{A}_{rep}(\pi^{*}(D^{\prime}))$ at index 1, for $\varepsilon=\frac{e^{\varepsilon_{0}}(e^{\varepsilon_{0}}-1)^{2}}{2m}+(e^{\varepsilon_{0}}-1)\sqrt{\frac{2e^{\varepsilon_{0}}\log{(1/\delta)}}{m}}$, which implies $\mathcal{A}_{rc}(D)\approxeq_{\varepsilon,\delta+m\delta_{0}}\mathcal{A}_{rc}(D^{\prime})$. Consequently, it implies $\varepsilon\leq 7\varepsilon_{0}\sqrt{\frac{\log(1/\delta)}{m}}$ for $\varepsilon_{0}\leq 1$ and $\delta\leq 1/100$.

The case $\delta_{0}>0$ follows from the same reduction using the corresponding setting of Theorem A.4. ∎

A.2 Proof of Theorem 4.1

By post-processing, each of the $\mathcal{A}^{(i)}$ is $(\varepsilon_{0},\delta_{0})$-DP.

To bound the probabilities $p_{i}$ we write:

To proceed, we assume $\delta_{0}=0$. If that is not the case, then the same argument based on Lemma A.3 used in the proof of Theorem A.4 allows us to reduce the analysis to the case $\delta_{0}=0$ and modify the final $\varepsilon$ and $\delta$ accordingly. When the local randomizers satisfy pure DP, we have

To conclude the proof of Theorem 4.1, we provide a high probability bound for $\left\|L\right\|_{2}$ for random $L$ representing the loads of $m$ bins when $n$ balls are thrown uniformly and independently.

Let $L=(L_{1},\ldots,L_{m})$ denote the number of users checked in into each of $m$ update slots in the protocol from Figure 2. With probability at least $1-\delta$, we have

The proof is a standard application of McDiarmid’s inequality. First note that $\left\|L\right\|_{2}$ is a function of $n$ i.i.d. random variables indicating the bin where each ball is allocated. Since changing the assignment of one ball can only change $\left\|L\right\|_{2}$ by $\sqrt{2}$, we have

with probability at least $1-\delta$. Finally, we use Jensen’s inequality to obtain

The privacy claim in Theorem 4.1 follows from using Lemma A.6 to condition with probability at least $1-\delta_{2}$ to the case where $L$ is such that

A.3 Proof of Theorem 5.1

We will prove the privacy guarantee of $\mathcal{A}_{sl}$ (Algorithm 5) in a similar manner as in the proof of Theorem 7 in : by reducing $\mathcal{A}_{sl}$ to $\mathcal{A}_{swap}$ that starts by swapping the first element with a u.a.r. sample in the dataset, and then applies the local randomizers (Algorithm 6). They key difference between our proof and the one in is that we provide tighter, position-dependent privacy guarantees for each of the outputs of $\mathcal{A}_{swap}$, and then use an heterogeneous adaptive composition theorem from to compute the final privacy parameters.

(Amplification by swapping) For a domain $\mathcal{D}$, let $\mathcal{A}^{(i)}_{ldp}:\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}\times\mathcal{D}\rightarrow\mathcal{S}^{(i)}$ for $i\in[n]$ (where $\mathcal{S}^{(i)}$ is the range space of $\mathcal{A}^{(i)}_{ldp}$) be a sequence of algorithms s.t. $\mathcal{A}^{(i)}_{ldp}$ is $\varepsilon_{0}$-DP for all values of auxiliary inputs in $\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(i-1)}$. Let $\mathcal{A}_{swap}:\mathcal{D}^{n}\rightarrow\mathcal{S}^{(1)}\times\cdots\times\mathcal{S}^{(n)}$ be the algorithm that given a dataset $D=d_{1:n}\in\mathcal{D}^{n}$, swaps the first element in $D$ with an element sampled u.a.r. in $D$, and then applies the local randomizers to the resulting dataset sequentially (see Algorithm 6). $\mathcal{A}_{swap}$ satisfies $(\varepsilon,\delta)$-DP at index 1 in the central model, for $\varepsilon=\frac{e^{3\varepsilon_{0}}(e^{\varepsilon_{0}}-1)^{2}}{2n}+e^{3\varepsilon_{0}/2}(e^{\varepsilon_{0}}-1)\sqrt{\frac{2\log{(1/\delta)}}{n}}$. Furthermore, if the $\mathcal{A}^{(i)}$ are $(\varepsilon_{0},\delta_{0})$-DP with $\delta_{0}\leq\frac{(1-e^{-\varepsilon_{0}})\delta_{1}}{4e^{\varepsilon_{0}}\left(2+\frac{\ln(2/\delta_{1})}{\ln(1/(1-e^{-5\varepsilon_{0}}))}\right)}$, then $\mathcal{A}_{swap}$ is $(\varepsilon^{\prime},\delta^{\prime})$-DP with $\varepsilon^{\prime}=\frac{e^{24\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)^{2}}{2n}+e^{12\varepsilon_{0}}(e^{8\varepsilon_{0}}-1)\sqrt{\frac{2\log{(1/\delta)}}{n}}$ and $\delta^{\prime}=\delta+m(e^{\varepsilon^{\prime}}+1)\delta_{1}$.