The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation

Introduction

Software and service providers rely on increasingly complex data analytics and machine learning models to improve their services. However, training these machine learning models hinges on the availability of large datasets, which are often distributed across user devices and contain sensitive information. The collection of these datasets comes with several privacy risks – can the service provider address issues around consent, transparency, control, breaches, persistence, processing, and release of data? There is thus a strong desire for technologies which systematically address privacy concerns while preserving, to the best extent possible, the utility of the offered services.

To address this need, several privacy-enhancing technologies have been studied and built over the past few years. Prominent examples of such technologies include federated learning (FL) to ensure that raw data never leaves users’ devices [MMRHA17, KM+19], cryptographic secure aggregation (SecAgg) to prevent a server from inspecting individual user updates [BIKMMPRSS17, BBGLR20], and differentially private stochastic gradient descent (DP-SGD) to train models with provably limited information leakage [ACGMMTZ16, TB20]. While these technologies have been extremely well studied in a separate fashion, little work has focused on understanding precisely how they can be combined in a rigorous and principled fashion. Towards this end, we present a comprehensive end-to-end system where each client appropriately discretizes their model update and adds discrete Gaussian noise to it before sending it for modular secure summation using SecAgg. This provides the first concrete step towards building a communication-efficient FL system with distributed DP See “Distributed DP” paragraph in Section 1.2 for a definition of this notion of DP and a literature review. and SecAgg guarantees.

1 Main Results

Privacy is achieved by each client independently adding discrete Gaussian noise [CKS20] to its (appropriately discretized) vector. The sum of independent discrete Gaussians is not a discrete Gaussian, but we show that it is extremely close for the parameter regime of interest. This is the basis of our differential privacy guarantee, and we believe this result to be of independent interest.

Communication and Computation: It is crucial that our algorithms are efficient, especially the client side, which may be running on a mobile device. Computationally, our algorithms run in time that is nearly linear in the dimension. The communication cost is $O(d\log m)$. While we cannot control the dimension $d$, we can minimize the number of bits per coordinate, which is $\log m$. However, this introduces a tradeoff between communication and accuracy – larger $m$ means more communication, but we can reduce the probability of a modular wrap around and pick a finer discretization to reduce the rounding error.

We focus our discussion on the simple task of summing vectors. In a realistic federated learning system, there will be many summing rounds as we iteratively update our model. Each round will be one invocation of our protocol. The privacy loss parameters of the larger system can be controlled using the composition and subsampling properties of differential privacy. That is, we can use standard privacy accounting techniques [DR16, BS16, Mir17, WBK19] to analyse the more complex system, as long as we have differential privacy guarantees for the basic protocol that is used as a subroutine.

We now state the privacy of our algorithm.

Let $c,d,\gamma,\beta,\sigma$ be the parameters of Algorithm 1 and $n$ the number of trustworthy clients. Define

We remark on the parameters of the theorem: To first approximation, $\varepsilon\approx\frac{c}{\sqrt{n}\sigma}$. This is because the input vectors are clipped to have norm $c$ and then each client adds (discrete) Gaussian noise with variance $\approx\sigma^{2}$. The noise added to the sum thus has variance $\approx n\sigma^{2}$. However, there are two additional effects to account for: First, randomized rounding can increase the norm from $c$ to $\Delta_{2}$ and this becomes the sensitivity bound that we use for the privacy analysis. Second, the sum of $n$ discrete Gaussians is not a discrete Gaussian, but it is close; $\tau$ bounds the max divergence between the sum of $n$ discrete Gaussians each with scale parameter $\sigma/\gamma$ and one discrete Gaussian with scale parameter $\sqrt{n}\sigma/\gamma$.

Note that $\frac{1}{2}\varepsilon^{2}$-concentrated DP [DR16, BS16] is equivalent to satisfying $\left(\alpha,\frac{1}{2}\varepsilon^{2}\alpha\right)$-Rényi DP [Mir17] simultaneously for all $\alpha>1$. Concentrated DP can be converted to the more standard approximate differential privacy [CKS20]: For any $\delta>0$, $\frac{1}{2}\varepsilon^{2}$-concentrated DP implies $\left(\varepsilon_{\text{aDP}}(\delta),\delta\right)$-DP, where

Next we turn to the accuracy of the algorithm. We provide both an empirical evaluation and theoretical analysis. We give the following asymptotic guarantee; a more precise guarantee with exact constants can be found in Theorem 36.

To interpret Theorem 2, note that mean squared error $O\left(\frac{c^{2}d}{\varepsilon^{2}}\right)$ is, up to constants, exactly the error we would expect to attain for differential privacy in the central model. Our analysis attains reasonably sharp constants (at the expense of many lower order terms that we suppress here in the introduction). However, to truly gauge the practicality of our method, we perform an empirical evaluation.

To investigate the interplay between communication, accuracy, and privacy under our proposed protocol in practice, we empirically evaluate our protocol and compare it to the commonly used centralized continuous Gaussian mechanism on two canonical tasks: distributed mean estimation (DME) and federated learning (FL). For DME, each client holds a vector and the server’s goal is to obtain a differentially private mean estimate of the vectors. We show that 16 bits per coordinate are sufficient to nearly match the utility of the Gaussian baseline for regimes of interest. For FL, we show on Federated EMNIST [CDWLKMST18] and Stack Overflow [Aut19] that our approach gives good performance under tight privacy budgets, despite using generic RDP amplification via sampling [ZW19] for our methods and the precise RDP analysis for the subsampled Gaussian mechanism [MTZ19]. We provide an open-source implementation of our methods in TensorFlow Privacy [ATMR19] and TensorFlow Federated [IO19]. Code: https://github.com/google-research/federated/tree/master/distributed_dp.

2 Related Work

Under FL, a set of clients (e.g., mobile devices or institutions) collaboratively train a model under the orchestration of a central server, while keeping training data decentralized [MMRHA17, Bon+19]. It embodies the principles of focused data collection and minimization, and can mitigate many of the systemic privacy risks and costs resulting from traditional, centralized machine learning and data science approaches. FL performs many rounds of interaction between the server and subsets of online clients; for example, each round may consist of computing and aggregating the gradients of the loss for a given set of model weights, which are then updated using the aggregated gradients for the next round. This allows us to focus on the simple task of computing the sum of vectors (model updates) held by the clients. We refer the reader to [KM+19] for a survey of recent advances and open problems in FL.

While the above features can offer significant practical privacy improvements over centralizing training data, FL offers no formal guarantee of privacy and has to be composed with other privacy technologies to offer strong (worst-case) privacy guarantees. The primary goal of this paper is to show how two such technologies, namely secure aggregation and differential privacy, can be carefully combined with FL to offer strong and quantifiable privacy guarantees.

While SecAgg prevents the server from inspecting individual client updates, the server is still able to learn the sum of the updates, which itself may leak potentially sensitive information [MSDCS19, CLEKS19, SS19, DSSUV15, SS19a, NSTPC21, SSSS17]. To address this issue, differential privacy (DP) [DMNS06], and in particular, DP-SGD can be employed [SCS13, BST14, ACGMMTZ16, TB20]. DP is a rigorous measure of information disclosure about individuals participating in computations over centralized or distributed datasets. Over the last decade, an extensive set of techniques has been developed for differentially private data analysis, particularly under the assumption of a centralized setting, where the raw data is collected by a trusted service provider prior to applying perturbations necessary to achieve privacy. This setting is commonly referred to as the central DP setting. More recently, there has been a great interest in the local model of DP [KLNRS11, ESAG04, War65] where the data is perturbed on the client side before it is collected by a service provider.

Local DP avoids the need for a fully trusted aggregator. However, it is now well-established that local DP usually leads to a steep hit in accuracy [KLNRS11, DJW13, KBR16]. In order to recover some of the utility of central DP, without having to rely on a fully trusted central server, an emerging set of models of DP, often referred to as distributed DP, can be used. Under distributed DP, clients employ a cryptographic protocol (e.g., SecAgg) to simulate some of the benefits of a trusted central party. Clients first compute minimal application-specific reports, perturb these slightly, and then execute the aggregation protocol. The untrusted server then only has access to the aggregated reports, with the aggregated perturbations. The noise added by individual clients is typically insufficient for a meaningful local DP guarantee on its own. However, after aggregation, the aggregated noise is sufficient for a meaningful DP guarantee, under the security assumptions necessary for the cryptographic protocol.

Despite the recent surge of interest in distributed DP, much of the work in this space focuses on the shuffled model of DP where a trusted third party (or a trusted execution environment) shuffles the noisy client updates before forwarding them to the server [EFMRTT19, BEMMRLRKTS17, CSUZZ19]. For more information on the shuffled model of DP, we refer the reader to [GKMP20, GGKPV21, GMPV20, GGKMPV20, IKOS06, BBGN19, BBGN20, BC20, BCJM21, GDDKS20].

The combination of SecAgg and distributed DP in the context of communication-efficient FL is far less studied. For instance, the majority of existing works ignore the finite precision and modular summation arithmetic associated with secure aggregation [GXS13, TBASLZZ19, VA17]. This is especially problematic at low SecAgg bit-widths (e.g., in practical FL settings where communication efficiency is critical).

The closest work to ours is cpSGD [ASYKM18], which also serves as an inspiration for much of our work. cpSGD uses a distributed version of the binomial mechanism [DKMMN06] to achieve distributed DP. When properly scaled, the binomial mechanism can (asymptotically) match the continuous Gaussian mechanism. However, there are several important differences between our work and cpSGD. First, the binomial mechanism does not achieve Rényi or concentrated DP [DR16, BS16, Mir17] and hence we cannot combine it with state-of-the-art composition and subsampling results, which is a significant barrier if we wish to build a larger FL system. The binomial mechanism is analyzed via approximate DP; in other words, the privacy loss for the binomial mechanism can be infinite with a non-zero probability. We avoid this issue by basing our privacy guarantee on the discrete Gaussian mechanism [CKS20], which also matches the performance of the continuous Gaussian and yields clean concentrated DP guarantees that are suitable for sharp composition and subsampling analysis. cpSGD also does not consider the impact of modular arithmetic, which makes it harder to combine with secure aggregation.

Previous attempts at achieving DP using a distributed version of the discrete Gaussian mechanism have either inaccurately glossed over the fact that the sum of discrete Gaussians is not a discrete Gaussian, or assumed that all clients secretly share a seed that is used to generate the same discrete Gaussian instance, which is problematic because a single honest-but-curious client can fully break the privacy guarantees [WJS21]. We provide a careful privacy analysis for sums of discrete Gaussians. Our privacy guarantees degrade gracefully as a function of the fraction of malicious (or dropped out) clients.

Preliminaries

We begin by defining the Rényi divergences, which we use throughout to quantify privacy.

For $\alpha\in(1,\infty)$, we define the Rényi divergence of order $\alpha$ of $P$ with respect to $Q$ as

We will abuse this notation by considering the divergence between random variables when we mean the divergence between their respective distributions.

We now state some properties of the Rényi divergences; proofs and further properties can be found in the literature [BS16, BS19].

Let $P,Q,R$ be probability distributions such that $P$ is absolutely continuous with respect to $Q$ and $Q$ is absolutely continuous with respect to $R$. Then the following hold.

(Quasi)convexity: If $P^{\prime}$ is a distribution on the same space as $P$ and $Q^{\prime}$ is a distribution on the same space as $Q$ and $P^{\prime}$ is absolutely continuous with respect to $Q^{\prime}$, then

where $tP+(1-t)P^{\prime}$ denotes the convex combination of distributions.

Now we can state the definitions of concentrated differential privacy [DR16, BS16] and Rényi differential privacy [Mir17] and relate these to the standard definition of differential privacy [DMNS06, DKMMN06]. We adopt user-level privacy – i.e., each entry in the input corresponds to all the records associated with a single person [MRTZ18]. Thus the differential privacy distributional similarity guarantee holds with respect to adding or removing all of the data belonging to a single person. This is stronger than the commonly-used notion of item level privacy where, if a user contributes multiple records, only the addition or removal of one record is protected.

We choose to define differential privacy with respect to adding or removing the records of an individual, rather than replacing the records. Since replacement can be achieved by a combination of an addition and a removal, group privacy (a.k.a. the triangle inequality) implies a differential privacy guarantee for replacement; however, the privacy parameter will be doubled. We define $\mathcal{X}^{*}=\bigcup_{n=0}^{\infty}\mathcal{X}^{n}$ to be the set of varying-size inputs from $\mathcal{X}$.

Concentrated differential privacy is a version of differential privacy that captures many natural techniques for attaining differential privacy and gives sharp composition results, among other features. We use the definition of[BS16] which is a simplification of the original definition of[DR16]. Specifically, we use what is also known as zero-concentrated differential privacy (zCDP) [BS16], although we drop the “zero” qualifier for brevity, as there is no need to distinguish it from the original version of concentrated differential privacy [DR16]. The two versions are loosely equivalent, but the version we use has cleaner mathematical properties.

A more general relaxation of concentrated differential privacy is Rényi differential privacy, which was defined by[Mir17].

We also use the original version of differential privacy that was defined by\AtNextCite\AtEachCitekey [DMNS06] with $\delta=0$ (a.k.a. pure or pointwise differential privacy) and with the possibility of $\delta>0$ (i.e., approximate differential privacy) by\AtNextCite\AtEachCitekey [DKMMN06].

A randomized algorithm $M:\mathcal{X}^{*}\to\mathcal{Y}$ satisfies $(\varepsilon,\delta)$-differential privacy iff, for all $x,x^{\prime}\in\mathcal{X}^{*}$ differing by the addition or removal of a single user’s records, we have

for all events $E\subset\mathcal{Y}$. We refer to $(\varepsilon,0)$-differential privacy as pure differential privacy or pointwise differential privacy and we refer to $(\varepsilon,\delta)$-differential privacy with $\delta>0$ as approximate differential privacy.

We remark that $(\varepsilon,0)$-DP is equivalent to $(\infty,\varepsilon)$-Rényi DP. Similarly, $\frac{1}{2}\varepsilon^{2}$-concentrated DP is equivalent to satisfying $(\alpha,\frac{1}{2}\varepsilon^{2}\alpha)$-Rényi DP simultaneously for all $\alpha\in(1,\infty)$.

In addition we have the following conversion lemma [BBGHS20, CKS20, ALCKS20] from concentrated DP to approximate DP.

If $M$ satisfies $(\varepsilon,0)$-differential privacy, then it satisfies $\frac{1}{2}\varepsilon^{2}$-concentrated differential privacy. If $M$ satisfies $\frac{1}{2}\varepsilon^{2}$-concentrated differential privacy, then, for any $\delta>0$, $M$ satisfies $(\varepsilon_{\text{aDP}}(\delta),\delta)$-differential privacy, where

Distributed Discrete Gaussian

We will use the discrete Gaussian [CKS20] as the basis of our privacy guarantee.

The discrete Gaussian has many of the desirable properties of the continuous Gaussian [CKS20], including the fact that it can be used to provide differential privacy.

Unlike the continuous Gaussian, the sum/convolution of two independent discrete Gaussians is not a discrete Gaussian. However, we show that, for reasonable parameter settings, it is very close to one. The following result is a simpler version of Theorem 4.6 of[GMPW20].

The bound of the theorem is surprisingly strong; if $\sigma^{2}=\tau^{2}=3$, then the bound is $\leq 10^{-12}$, which should suffice for most applications. Furthermore, closeness in max divergence is the strongest measure of closeness that we could hope for (rather than, say, total variation distance).

Note that this interval is independent of $z$. Here $c(\sigma^{2},\tau^{2})$ is an appropriate constant.

as long as $1/\sigma^{2}+1/\tau^{2}\leq 8$. ∎

Theorem 11 can easily be extended to sums of more than two discrete Gaussians by induction:

The result now follows by induction; the base case $n=1$ is trivial. ∎

We can now use the triangle inequality to combine our convolution closeness results with the privacy guarantee of a single discrete Gaussian to obtain a privacy guarantee for sums of discrete Gaussians:

That is, an algorithm $M$ that adds $Z_{n}$ to a sensitivity-$\Delta$ query satisfies $\frac{1}{2}\varepsilon^{2}$-concentrated differential privacy for $\varepsilon=\min\left\{\sqrt{\frac{\Delta^{2}}{n\sigma^{2}}+20\cdot\sum_{k=1}^{n-1}e^{-2\pi^{2}\sigma^{2}\frac{k}{k+1}}},\frac{|\Delta|}{\sqrt{n}\sigma}+10\cdot\sum_{k=1}^{n-1}e^{-2\pi^{2}\sigma^{2}\frac{k}{k+1}}\right\}$.

To make the above bound concrete, if $\sigma=\Delta=1$ and $n=10^{4}$, then $\varepsilon<0.02$.

Finally, we extend Proposition 13 to the multidimensional setting using the composition property:

This follows from Proposition 13 and summing over coordinates. Note that before summing we expand

To obtain the third expression we apply the bound $\|\Delta\|_{1}\leq\sqrt{d}\cdot\|\Delta\|_{2}$ and complete the square again. ∎

Finally, we state a utility bound for the discrete Gaussian.

Theoretical Utility Analysis

We now delve into the accuracy analysis of our algorithm. There are three sources of error that we must account for: (i) discretization via (conditional) randomized rounding, (ii) the noise added for privacy (which depends on the norm of the discretized vector), and (iii) the modular clipping operation. We address these concerns one at a time.

In order to apply discrete noise, we must first round the input vectors to the discrete grid. We must analyze the error (both bias and variance) that this introduces, and also ensure that it doesn’t increase the sensitivity too much. That is, the rounded vector may have larger norm than the original vector, and we must control this.

We begin by defining the randomized rounding operation:

We first look at how randomized rounding impacts the norm. It is easy to show that

for all $p\in[1,\infty]$. This bound may be sufficient for many purposes, but, if we relax the probability 1 requirement, we can do better (by constant factors), as demonstrated by the following lemma.

where $y:=x-\gamma\lfloor x/\gamma\rfloor\in[0,\gamma]^{d}$. Furthermore, for any $\beta\in(0,1)$, we have

Fix some $i\in[d]$ and $t,\lambda\geq 0$. By Hoeffding’s lemma,

Fix some $i\in[d]$ and $t,\lambda\geq 0$. Assume, without loss of generality, that $x_{i}\geq 0$. By Hoeffding’s lemma,

Setting $t=4\frac{\lambda-\|x\|_{1}}{\gamma^{2}d}$ and $\lambda=\|x\|_{1}+\gamma\sqrt{\frac{1}{2}d\log(1/\beta)}$ gives

The expectation and high probability bounds of Lemma 17 are only a constant factor better than the worst-case bound (20). Namely, Lemma 17 gives the bound

Nevertheless, constant factor improvements matter in practical systems. However, hopefully, $\gamma$ is sufficiently small that the increase in norm from randomized rounding is entirely negligible, even if we apply the worst-case bound.

Lemma 17 shows that, with high probability, randomized rounding will not increase the norm too much. We could use this directly as the basis of a privacy guarantee – the probability of the norm being too large would correspond to some kind of privacy failure probability. Instead what we will do is, if the norm is too large, we simply fix that – namely, by resampling the randomized rounding procedure. That is, instead of accepting a small probability of privacy failing, we accept a small probability of inaccuracy.

Now we give a lemma that bounds the error of conditional randomized rounding.

For an arbitrary random variable $X$ and nontrivial event $E$, we have

where $x^{*}\in\gamma\lfloor x/\gamma\rfloor+[0,\gamma]^{d}$ and, hence, $\|x-x^{*}\|_{2}\leq\gamma\cdot\sqrt{d}$.

By Hoeffding’s lemma, since $R_{\gamma}(x)\in\gamma\lfloor x/\gamma\rfloor+\{0,\gamma\}^{d}$ and is a product distribution with mean $x$, we have

We summarize the results of this section. First we give a proposition for a single instance of randomized rounding (this combines Lemma 17 and 21).

Now we give a proposition for sums of randomized roundings.

Proposition 23 provides some guidance on how to set the parameter $\beta$. We have the mean squared error bound (39)

If we set $\beta\approx 1/\sqrt{n}$, then the bias and variance terms in the bound are of the same order. Setting $\beta$ too small would needlessly increase the sensitivity $\Delta_{2}$. And we see that there is little value in setting $\beta\ll 1/\sqrt{n}$. So the theory suggests setting $\beta\approx 1/\sqrt{n}$.

However, we emphasize that this is a worst-case upper bound on the error and it is likely that, in practice, the error would likely be considerably less. Thus it is justifiable to set $\beta$ to be considerably larger – e.g., $\beta=e^{-1/2}$ – and simply hope for the best in terms of accuracy.

Proposition 23 covers the error introduced by discretization. Obviously, reducing the granularity $\gamma$ will reduce the discretization error. However, this comes at a cost in communication, so the choice of this parameter will need to be carefully made.

In Section 3 we have covered the noise that is injected to preserve privacy and in Section 4.1 we have covered the error introduced by discretizing the data. Now we state a result that combines these.

Let $\beta\in[0,1)$, $\sigma^{2}\geq\frac{1}{2}\gamma>0$, and $c>0$. Let

Then $A$ satisfies $\frac{1}{2}\varepsilon^{2}$-concentrated differential privacy. Not that this is with respect to the addition or removal of an element, not replacement. To keep $n$ fixed, we would need addition/removal to be defined to simply zero-out the relevant vectors.

2 Flattening

It is possible that the inputs $x_{i}$ and the sum $\bar{x}=\sum_{i}^{n}x_{i}$ are very heavily concentrated on one coordinate. This is a bad case, as the modular clipping will create a very large error, unless we use a very large modulus. To avoid this problem we will “flatten” the inputs as a pre-processing step (which is inverted by the server at the end of the protocol).

Specifically, our goal is to pre-process the inputs $x_{1},\cdots,x_{n}$ so that $\sum_{i}x_{i}\in[a,b]^{d}$ and then at the end we can undo the pre-processing to obtain the original value. Here $[a,b]$ is the range where modular arithmetic does not cause errors.

The flattening matrix $U$ is shared randomness – that is, the server and all the clients must have access to this matrix. Fortunately, the differential privacy guarantee does not depend on this randomness remaining hidden; thus $U$ can be published, and we do not need to worry about the privacy adversary having access to it.

There are many possibilities for this flattening transformation. A natural option is for $U$ to be a random unitary matrix or rotation matrix. This would attain the desired property:

Instead our approach is to first randomize the signs of the entries of $x$ and then multiply by a matrix with small entries. This attains the desired guarantee:

Walsh-Hadamard matrices are ideal for $H$ (after scaling appropriately). They attain the optimal $\rho=1$ and the fast Walsh-Hadamard transform can compute the matrix-vector products in $O(d\log d)$ operations. This is what we use in our experiments. Formally, the Walsh-Hadamard matrices are defined recursively as follows:

The only downside of Walsh-Hadamard matrices is that they require the dimension $d$ to be a power of $2$. We can pad the input vectors with zeros to ensure this. However, in the worst case, padding may nearly double the dimension $d$, which correspondingly slows down our algorithm. (E.g., if $d=2^{k}+1$, then we must pad to dimension $d=2^{k+1}$.)

To avoid or reduce padding, there are several solutions:

Such matrices exist for any dimension $d$ and the required matrix-vector products can still be computed in $O(d\log d)$ time. However, they attain a slightly suboptimal subgaussian flatness parameter of $\rho=2$.

Fortunately, there are explicit constructions of Hadamard matrices of many sizes which also allow efficient matrix-vector computations. By considering sizes other than powers of $2$, we can significantly reduce the required amount of padding.

For example, we can generalize the Kronecker product construction (53) to dimension $d=12\cdot 2^{k}$ for integers $k\geq 0$:

The addition of this construction alone is sufficient to reduce the worst case for padding from a factor of $2$ to a factor of $1.5$ – now $2^{k}+1$ can be padded to $12\cdot 2^{k-3}=1.5\cdot 2^{k}$. The other desirable properties of the Hadamard matrices are also retained.

A third solution is to move from the reals to complex numbers and use the discrete Fourier transform. Our real vector of length $d$ can be encoded as a complex vector of length $d/2$ (two real entries become the real and imaginary components of one complex entry). Instead of $D$ being a diagonal matrix with random signs, the diagonal entries are $e^{\sqrt{-1}\cdot\theta}$ for a uniformly random $\theta\in[0,2\pi)$. (In fact, it suffices to have $\theta\in\{0,\pi/2,\pi,3\pi/2\}$ uniform. This only requires one bit of shared randomness per coordinate. Note that $\theta\in\{0,\pi/2,\pi,3\pi/2\}$ corresponds to $e^{i\theta}\in\{1,i,-1,-i\}$ and, in Equation 57, to R_{\theta}\in\left\{\left(\begin{array}[]{cc}1&0\\ 0&1\end{array}\right),\left(\begin{array}[]{cc}0&-1\\ 1&0\end{array}\right),\left(\begin{array}[]{cc}-1&0\\ 0&-1\end{array}\right),\left(\begin{array}[]{cc}0&1\\ -1&0\end{array}\right)\right\}.) Then $H$ is the discrete Fourier transform matrix. This gives us a complex vector of length $d/2$ that can be decoded back to a real vector of length $d$. This transformation is unitary and linear and attains the optimal subgaussian flatness constant $\rho=1$ (i.e., matches the guarantee of a random rotation or unitary matrix from Lemma 28). The only requirement is that the dimension must be even – i.e., we must pad at most one zero.

If we wish to avoid thinking about complex numbers, the complex numbers can be replaced with $2\times 2$ rotation matrices. That is

Let $x=\lambda\cos\psi$ and $y=\lambda\cos(\psi+\pi/2)$. Then $\lambda\cos(\psi+\pi)=-x$ and $\lambda\cos(\psi+3\pi/2)=-y$. Note $x^{2}+y^{2}=\lambda^{2}$. Thus

The inequality follows from the fact that $x^{2k}+y^{2k}\leq(x^{2}+y^{2})^{k}=(\lambda^{2}\cos^{2}\psi+\lambda^{2}\sin^{2}\psi)^{k}=\lambda^{2k}$ and $2\cdot(2k)!\geq 4^{k}\cdot k!$ for all integers $k\geq 1$. The last fact can be easily verified by induction: For $k=1$ both sides are equal to $4$. Moving from $k$ to $k+1$ multiplies the right side by $4(k+1)$ and the left side by $(2k+1)(2k+2)=4(k+1)(k+1/2)>4(k+1)$. ∎

We emphasize that the discrete fourier transform (i.e., matrix-vector multiplications with $H_{2d}^{\prime\prime}$ from Equation 56) can be computed in $O(d\log d)$ operations for any $d$ – not just powers of $2$. Although the exact efficiency (i.e., constants) depends on $d$ [Wik21].

3 Modular Clipping

In this section we cover third and final source of error – modular arithmetic. This is introduced by the secure aggregation procedure.

We first define the modular clipping operation in a convenient form for real numbers.

Note that definition 33 does not specify whether $M_{[a,b]}(a)=a$ or $M_{[a,b]}(a)=b$ (and likewise for $M_{[a,b]}(b)$). Thus our analysis does not depend on how this choice is made.

A key property of the modular operation is that it is homomorphic:

Our goal is to analyze $M_{[a,b]}(A(x))$, where $A$ is as in Proposition 26. The modular clipping arises from the secure aggregation step, which works over a finite group. Note that $A$ discretizes the values (although this is not crucial for this part of the analysis).

We want to ensure that $M_{[a,b]}(A(x))\approx x$. We have already established that $A(x)\approx x$ and our goal is now to analyze the modular clipping operation. If $A(x)\in[a,b]^{d}$, then $M_{[a,b]}(A(x))=A(x)$ and we are in good shape; thus our analysis centers on ensuring that this is the case.

We will use the fact that the flattening operation, as well as the randomized rounding and noise addition, result in each coordinate being a centered subgaussian random variable. This allows us to bound the probability of straying outside $[a,b]$.

Now we have our bound on the error of modular clipping:

Set $t=(b-a)^{2}/2\sigma^{2}\geq\log 2$ to obtain the first part of the result.

Set $t=(b-a)^{2}/4\sigma^{2}\geq\log 2$ to obtain the second part of the result. ∎

4 Putting Everything Together

We have now analyzed the three sources of error – randomized rounding, privacy-preserving noise, and modular arithmetic. It remains to combine these results. This yields our main result:

There is a lot to unpack in Theorem 36. Let us work through the parameters:

$n$ is the number of individuals and $d$ is the dimension of the data.

$c$ is the bound on $2$-norm of the individual data vectors.

$\sigma^{2}$ is the variance of the individual discrete Gaussian noise that we add; the sum will have variance $n\sigma^{2}$. This determines the privacy; specifically $\varepsilon\approx\frac{c}{\sqrt{n}\sigma}$ and we attain $\frac{1}{2}\varepsilon^{2}$-concentrated differential privacy.

$\beta$ is a parameter that controls the conditional randomized rounding. $\beta=0$ yields unconditional randomized rounding, and larger $\beta$ entails more aggressive conditioning. It will be helpful to think of $\beta=\sqrt{\gamma/n}$; although, in practice, slightly larger $\beta$ may be preferable.

$\rho$ measures how good the flattening matrix $U$ is (cf. Lemma 29). Think of $\rho=1$ or at most $\rho\leq 2$.

The other parameters – $\Delta_{2}$, $G$, $\tau$, $\hat{\sigma}$ – are not important, as they are determined by the previous parameters. $\Delta_{2}$ and $G$ determine how much the conditional randomized rounding can increase the norm (initially the norm is $c$). $\tau$ quantifies how far the sum of discrete Gaussians is from just a single discrete Gaussian and how this affects the differential privacy guarantee. The ratio $\hat{\sigma}/r$ measures how much error the modular clipping contributes. $\hat{\sigma}$ is determined by other parameters, but note that $\left\|\sum_{i}^{n}x_{i}\right\|\leq\sum_{i}^{n}\|x_{i}\|\leq cn$ may be a loose upper bound, in which case, the clipping error is less.

Now we look at the error bound. If we assume $\beta\leq 1/\sqrt{n}$ and $\hat{\sigma}^{2}(x)\leq r^{2}/4\log(r\sqrt{n}/\gamma^{2})$, then the guarantee (69) is simply

The first term is roughly the cost of privacy – $dn\sigma^{2}\approx d\frac{c^{2}}{\varepsilon^{2}}$. The second term, $dn\gamma^{2}$, is the cost of randomized rounding and modular clipping. (We have assumed $\beta$ and $\hat{\sigma}$ are sufficiently small to avoid any additional terms.)

The differential privacy guarantee follows from the postprocessing property of differential privacy and Proposition 26 (which, in turn, applies Proposition 14).

By our assumption on $U$ (and independence) we have

Recall $\hat{\sigma}^{2}(x)=\frac{\rho}{d}\left\|\sum_{i}^{n}x_{i}\right\|_{2}^{2}+\left(\frac{\gamma^{2}}{4}+\sigma^{2}\right)\cdot n$. By Proposition 35, for all $j\in[d]$,

where $a=-r$ and $b=r$ here. Summing over $j\in[d]$ yields

We gave an asymptotic version of Theorem 36 in the introduction.

Finally, we analyse how to set the parameters to obtain this bound. Note that we do not attempt to optimize constants here at all.

Theorem 36 gives the following parameters.

Note that $r=\frac{1}{2}\gamma m$. All we must do is verify that setting the parameters as specified in Theorem 2 yields $\frac{1}{2}\varepsilon^{2}$-concentrated DP and the desired accuracy. First,

Thus the privacy requirement is satisfied as long as $\sigma\geq 2c/\varepsilon\sqrt{n}$ and $(\sigma/\gamma)^{2}\geq 8d/\varepsilon^{2}n$, and $20nde^{\pi^{2}(\sigma/\gamma)^{2}}\leq\varepsilon^{2}/4$. So we can set

We set $\beta=\min\{1/n,1/2\}=\Theta\left(\frac{1}{n}\right)$.

Now we work out the asymptotics of the accuracy guarantee:

Now we wish to set $\gamma$ so that $\frac{m^{2}}{n}\exp\left(\frac{-\gamma^{2}m^{2}}{8\hat{\sigma}^{2}}\right)\leq 1$ – i.e., $\gamma\geq\frac{\hat{\sigma}}{m}\sqrt{8\log(1+m^{2}/n)}$. However, simply setting $\gamma=\frac{\hat{\sigma}^{*}}{m}\sqrt{8\log(1+m^{2}/n)}$, where $\hat{\sigma}^{*}$ is our upper bound on $\hat{\sigma}$, is cyclic, because our bound on $\hat{\sigma}$ depends on $\gamma$. Fortunately, we can resolve this as long as the coefficient in this cycle is $\leq 1-\Omega(1)$. That coefficient is $O\left(n+\frac{d}{\varepsilon^{2}}+n\log^{2}\left(\frac{nd}{\varepsilon^{2}}\right)\right)\cdot\frac{\log(1+m^{2}/n)}{m^{2}}$. A sufficient condition for this is

then the mean squared error is $O(c^{2}d/\varepsilon^{2})$, as required. ∎

Experiments

In Figure 2, we additionally investigate the trade-off between quantization errors and modular clipping errors by trying different values of $k$. Here, we use the optimistic norm bound on the vector sum as the general norm bound could be loose (thus $\gamma$ would be chosen conservatively such that modular wrap-around rarely happens). At $k=2$, the effect of modular clipping is now evident (the gap between DDGauss and Gaussian). With increasingly larger $k$ (larger $\gamma$), we incur more quantization errors (thus worse low bit-width performance) but less modular wrapping and can close the utility gap to Gaussian at high bit-widths.

2 Federated Learning

We evaluate on three public FL benchmarks: Federated EMNIST [CATVS17, CDWLKMST18], Stack Overflow Tag Prediction (SO-TP, [Aut19]), and Stack Overflow Next Word Prediction (SO-NWP, [Aut19]).

Federated EMNIST is an image classification dataset containing 671,585 training hand-written digit/letter images over 62 classes grouped into $N=3400$ clients by their writer. Stack Overflow is a large-scale text dataset based on the question answering site Stack Overflow. It contains over $10^{8}$ training sentences extracted from the site grouped by the $N=342477$ users, and each sentence has associated metadata such as tags. The task of SO-TP involves predicting the tags of a given sentence, while the task of SO-NWP involves predicting the next words given the preceding words in a sentence. For more details on the datasets and tasks, we refer the reader to [RCZGRKKM20]. We note that these datasets differ from those commonly used in related work (e.g. MNIST [LCB10] and CIFAR-10 [Kri+09]) in that they are substantially larger, more challenging, and involve user-level (instead of example-level) DP with real-world client heterogeneity and label/size imbalance. Obtaining a small $\varepsilon$ on EMNIST is also harder due to the relatively large sampling rate $q=n/N$ needed for stable convergence under noising.

2.2 Models

For EMNIST, We train a small convolutional net with two 3$\times$3 conv layers with 32/64 channels followed by two fully connected layers with 128/62 output units; a 2$\times$2 max pooling layer and two dropout layers with drop rate 0.25/0.5 are added after the first 3 trainable layers, respectively. The total number of parameters is $d=1018174$, which is slightly under $2^{20}$ to avoid excessive zero padding for the Walsh-Hadamard transform. For SO-TP, we follow [RCZGRKKM20] and train a simple logistic regression model for tag prediction. The vocabulary size is limited to $10000$ for word tokens and 500 for tags, and each sentence is represented as a bag-of-words vector. The resulting model size is $d=5000500$, which incurs a significant amount of zero padding. For SO-NWP, we use the LSTM architecture defined in [RCZGRKKM20] directly, which has a model size of $d=4050748$ parameters (slightly under $2^{22}$).

2.3 Setup

For all benchmarks, we used the standard dataset split provided by TensorFlow. For EMNIST, the dataset is split into training and test set and performance is reported on the test set. For Stack Overflow (SO-TP and SO-NWP), the dataset is split into training, validation, and test sets. Validation accuracies and test accuracies are reported on the validation and test sets respectively. Note that using the dataset splits from TensorFlow is standard practice as in previous work (e.g. [RCZGRKKM20, MRTZ18, ASGXR21]) and it allows our results to be comparable in similar settings. Note also that validation techniques such as $k$-fold validation can incur additional privacy costs.

We adopt most hyperparameters from previous work [RCZGRKKM20, ATMR19, KMSTTX21]. For all tasks, we train with federated averaging with server momentum of 0.9 [MMRHA17, HQB19]. In each round, we uniformly sample $n=100$ clients for EMNIST and SO-NWP following [ATMR19] and $n=60$ clients for SO-TP due to memory limit. We train 1 epoch over clients’ local datasets. Each client’s model updates are weighted uniformly (instead of by their number of samples) to maintain privacy. Clients are sampled without replacement within each round, and with replacement across rounds. For EMNIST, SO-TP, and SO-NWP respectively, we set the number of rounds $T$ to 1500, 1500, and 1600, $c$ to 0.03, 2.0, and 0.3, client learning rate $\eta_{c}$ to 0.032, 316, and 0.5, and client batch size to 20, 100, and 16. Server LR $\eta_{s}$ is set to 1 for EMNIST and 0.56 for SO-TP; for SO-NWP, $\eta_{s}$ is selected from a small grid {0.3, 1} and the best performance (according to validation accuracy) is reported. Tuning is limited to $c$ (to tradeoff between the bias from clipping and the noise from privacy) and $\eta_{s}$ (to match the selected $c$ and $n$). For SO-NWP, we limit the max number of examples per client to 256.

The reported privacy guarantees $\varepsilon$ rely on privacy amplification via sampling [KLNRS11, BST14, ACGMMTZ16], which is necessary to obtain reasonable privacy-accuracy tradeoffs in differentially private deep learning. This assumes that the identities of the users sampled in every round are hidden from the adversary. This does not hold for the entity initiating connection with the clients (typically the server running the FL protocol) but is applicable to the analysts that have requested the model. We adopt the tight amplification bound from [MTZ19] for the Gaussian baseline and use the generic upper bound from [ZW19] for DDGauss (we do not explore a precise analysis in this work). The generic amplification upper bound could lead to more noise being added for DDGauss to achieve the same privacy as Gaussian.

2.4 Results

For EMNIST, Figure 4 summarizes the test accuracies across different values of $\varepsilon$ and $B$ for $k=3$, and Figure 4 shows the accuracies during training. For Stack Overflow, Figure 6 summarizes the test performance on SO-TP (recall@5) and SO-NWP (accuracy), and Figure 6 shows the validation accuracies on SO-NWP.

Overall, with more communication bits ($B$) and privacy budget ($\varepsilon$), DDGauss achieves a better utility both relative to the Gaussian baseline and in absolute performance, and it can match the continuous Gaussian as long as $B$ is sufficient.

In particular, we can again observe the trade-off between quantization and modular clipping from Figure 4 and 6: a small $k$ can be sub-optimal for learning as the cost of modular wrap-around is more pronounced than quantization errors; using a larger $k$ allows DDGauss to match the Gaussian baseline at the expense of worse low bit-width performance (as $\gamma$ is larger).

Note also that for EMNIST (Figure 4), there is a slight performance gap between Gaussian and DDGauss in the extreme setting with $\varepsilon=3$ and $k=4$. We believe this minor mismatch, on top of the errors from rounding and modular clipping, is due to the use of the generic upper bound for privacy amplification via subsampling as discussed earlier in this section.

3 Additional Results

We additionally consider scaling up the SO-NWP experiments to $n=1000$ clients per round (similar to production settings described in [HRMRBAEKR18, MRTZ18, RMRB19]), and we show the validation accuracies during training across different noise multipliers $z=\widehat{\sigma}/c$ where $\widehat{\sigma}$ is the equivalent central noise standard deviation (i.e. $\sqrt{n}\sigma$ for DDGauss). The values of $z$ are aligned on privacy budgets and thus $z$ is in fact slightly larger for DDGauss compared to Gaussian due to effects of rounding, generic amplification, etc. in Figure 7. We set $c=1$ and $\eta_{s}=1$ for $z\approx 0.3$ and $z\approx 0.5$, and we set $\eta_{s}=3$ otherwise. $z\approx 0.07$ gives a target test accuracy of around 25.2% (e.g. a utility-first approach to limit performance degradation from DP [KMSTTX21]) while $z\approx 0.5$ and $z\approx 0.3$ give $\varepsilon$ of around 10 and 234 respectively. The results bear significant practical relevance as they indicate that as long as DDGauss is parameterized properly, it can perform as good as the continuous Gaussian in real-world settings (with large $n$, large model size $d$, and natural client heterogeneity from Stack Overflow).

Recall from Section 4.1 that the hyperparameter $\beta$ controls the growth of the client vector norm from conditional randomized rounding. Here, we are interested to know how $\beta$ and the bias and variance it introduces influence the communication-utility trade-off in practice. Figure 8 shows the results on Federated EMNIST with $\beta\in\{0,\frac{1}{\sqrt{n}},e^{-1/2}\}$ across $B\in\{14,16,18\}$ and $k\in\{2,4\}$ with user-level privacy budget fixed at $\varepsilon=3$; other parameters follow those described earlier. $\beta=0$ leads to unconditional rounding, in which case we use the worst case bound $\Delta_{2}\leq\|x\|_{2}+\gamma\sqrt{d}$. We note that when the communication budget is tight (i.e. large $k$ and small $B$, where the “room” for larger norm and noise variance is limited), the bounded norm growth from conditional rounding can be pivotal to model learning and convergence. When the communication budget is sufficient (i.e. small $k$ and large $B$, where we can afford unconditional rounding), the bias introduced by $\beta>0$ have insignificant impact on the model utility (e.g. $\beta=e^{-1/2}\approx 0.607$ and $\beta=1/\sqrt{n}=0.1$ give similar performance and convergence speed).

Figure 9 shows the privacy degradation as observed by the server if a certain percentage of the clients drops out during aggregation (thus there would be missing local noise shares). Note that for the external analyst, the server can always add the missing shares of noise onto the aggregate to prevent this degradation. Note also that the values of the parameters ($\gamma,\beta,B,c,d,k,n,T$) does not affect the degradation as they influence each other to arrive at the same initial $\varepsilon$. The sampling rate $q$ is also fixed at 1.0 as subsampling does not apply from the server’s perspective. Results indicate that the privacy guarantees degrade gracefully as clients drop out.

Concluding Remarks

We have presented an complete end-to-end protocol for federated learning with distributed DP and secure aggregation. Our solution relies on efficiently flattening and discretizing the client model updates before adding discrete Gaussian noise and applying secure aggregation. A significant advantage of this approach is that it allows an untrusted server to perform complex learning tasks on decentralized and privacy-sensitive data while achieving the accuracy of a trusted server. Our theoretical guarantees highlight the complex tension between communication, privacy, and accuracy. Our experimental results demonstrate that our solution is essentially able to match the accuracy of central differential privacy with 16 or fewer bits of precision per value.

Acknowledgments

We thank Naman Agarwal and Kallista Bonawitz for helpful discussions and comments on drafts of this paper. We thank Andrea La Mantia for pointing out an error in one of our calculations.

References