Federated Learning with Sparsification-Amplified Privacy and Adaptive Optimization

1 Introduction

Federated learning (FL) is a new distributed learning paradigm that enables multiple agents to collaboratively learn a shared model under the orchestration of the cloud without sharing their local data [McMahan et al., 2017]. By keeping data locally, FL is advantageous in privacy and communication efficiency compared with traditional centralized learning paradigm. However, recent inference attacks [Fredrikson et al., 2015; Shokri et al., 2017] show that the local model updates shared between agents could also lead to privacy leakage, and it is desirable to protect the shared local model updates with rigorous privacy guarantee 1 .

∗Contact Author

1 The full version is available at https://arxiv.org/abs/2008.01558

To address this issue, several privacy-preserving framework have been proposed, among which differential privacy (DP) [Dwork and Roth, 2014] has become the de-facto standard due to its rigorous privacy guarantee and effectiveness in data analysis tasks [Abadi et al., 2016; Hu et al., 2020; Huang et al., 2019; Guo and Gong, 2018; Gong et al., 2016]. General DP mechanisms, such as Gaussian or Laplacian mechanism, rely on the injection of carefully calibrated noise to the output of an algorithm directly. This poses new challenges to achieving DP in FL because the added noise is proportional to the model size which can be very large with modern deep learning neural networks (e.g., millions of model parameter), resulting in significantly degraded model accuracy. Under the local DP setting where the cloud is not fully trusted, the challenges become more prominent as all the local updates shared with the cloud need to be protected.

Existing works on differentially-private machine learning either consider centralized DP [Abadi et al., 2016], or rely on costly techniques such as secure multi-party computation [Truex et al., 2019] and shuffling via anonymous channels [Liu et al., 2020; Erlingsson et al., 2019] to remove the requirement of a trusted cloud and improve the model accuracy in local DP. How to better balance the model accuracy and privacy protection in FL efficiently remains largely unknown.

In this paper, we propose a novel differentially-private FL scheme, called Fed-SPA, to provide strong privacy guarantee in the local DP setting while maintaining high model accuracy. In light of the observation that local model updates in FL are largely sparse, we design a sparsification-coded DP mechanism that integrates gradient perturbation with random sparsification to amplify the privacy guarantee with little sacrifice on the model accuracy. Random sparsification transforms a large vector into a sparse one by keeping only a random subset of coordinates while setting other coordinates to zeros. As we will show in this paper, random sparsification not only introduces randomness to the scheme, but also reduces the sensitivity of the shared model updates with respect to raw data, thus resulting in smaller privacy loss at every communication round. Furthermore, as sparsification can slow down the convergence speed of learning algorithms and increase the total number of communication rounds, we propose to further reduce the end-to-end privacy loss by using convergence acceleration techniques to offset the negative impact of sparsification. We provide theoretical analysis to demonstrate the convergence of our scheme and rigorous privacy guarantee.

The main contributions of this paper are summarized below.

• We propose to use sparsification for privacy amplification in FL while also improving communication efficiency. Previous works that consider both communication efficiency and DP treat them as two separate goals and solve them in an uncoordinated manner. Unlike previous approaches, we focus on the interplay of those two goals and aim to kill two birds with one stone in this paper, i.e., use sparsification as a tool to improve DP and achieve communication efficiency at the same time. We theoretically analyze the impacts of sparsification on the utility-privacy trade-off and design a sparsificationcoded DP mechanism for FL that provides stronger privacy guarantee with the same amount of random noise.
• To further improve the utility-privacy trade-off, we integrate the sparsification-coded DP mechanisms with convergence acceleration techniques, which can reduce the number of required communication rounds and ensure faster convergence. Specifically, we adapt an acceleration strategy similar to that of Adam optimizer to the FL setting and design an adaptive aggregation strategy on the cloud to reduce the number of communication rounds. The resulting scheme called Fed-SPA provides a better utility-privacy trade-off than the state-of-art differentially private FL methods.
• We empirically evaluate our scheme on several benchmark datasets. The experiment results show that FedSPA significantly boosts the model accuracy, and at the same time saves more than 80% of the bandwidth cost compared to the state-of-art approaches under the same DP guarantee.

It is worth noting that our scheme aims to improve the utility-privacy trade-off while achieving communication efficiency. This distinguishes our paper from previous studies on communication efficient and differentially-private distributed learning that focus on ensuring privacy protection and achieving communication efficiency at the same time. For example, cpSGD [Agarwal et al., 2018] is a modified distributed SGD scheme which is private and communication-efficient via gradient quantization and binomial mechanism. However, since quantization does not provide any privacy amplification effects as sparsification, the utility-privacy trade-off is not improved in that approach.

2 Preliminaries

DP is a rigorous notion of privacy that has become the defacto standard for measuring privacy risk. In the context of FL, DP ensures that the exchanged model updates are nearly the same regardless of the usage of a data sample. In this paper, we consider a relaxed DP definition called R´enyi differential privacy (RDP), which is strictly stronger than (ϵ, δ)-DP for δ > 0 and allows tighter composition analysis.

Definition 1 ((α, ρ)-RDP). Given a real number α ∈ (1,+∞) and privacy parameter ρ ≥ 0, a randomized mechanismM satisfies (α, ρ)-RDP if for any two neighboring datasets D,D′ that differs in one record, the R´enyi αdivergence betweenM(D) andM(D′ ) satisfies

where the expectation is taken over the output of M(D′ ).

Lemma 1 (RDP Composition [Mironov, 2017]). If M1 satisfies (α, ρ1)-RDP and M2 satisfies (α, ρ2)-RDP, then their composition M1 ◦ M2 satisfies (α, ρ1 + ρ2)-RDP.

Lemma 2 (Gaussian Mechanism [Mironov, 2017]). Let h : D → Rd be a vector-valued function over datasets. The Gaussian mechanism M = h(D) + b with b ∼ N (0, σ2 Id) satisfies (α, αφ2 (h)/2σ2 )-RDP, where φ(h) is the L2 sensitivity of h defined by φ(h) = supD,D′ ‖h(D)-h(D′ )‖2 with D,D′ being two neighboring datasets in D.

3 Fed-SPA: Federated Learning with Sparsification-Amplified Privacy and Adaptive Optimization

Notation. We use [n] to denote the set of integers {1, 2, . . . , n} with any positive integer n, and [·]j to denote the j-th coordinate of a vector. Let ‖·‖ be the ℓ2 vector norm.

3.1 ProblemFormulation

A typical FL system consists of n agents and a central server (e.g., the cloud). Each agent i ∈ [n] has a local dataset with m data samples, and all agents collaboratively train a global model θ on the collection of their local datasets under the orchestration of the central server. The agents in FL aim to find the optimal global model θ by solving the following empirical risk minimization problem while keeping their data locally:

where fi(θ) = Ez∼Di [li(θ; z)] represents the loss function of i-th agent (possibly non-convex), Di is the data distribution of i-th agent, and z represents a data sampled from Di. For i ̸= j, the data distributions Di and Dj may be very different.

Threat Model. Before elaborating the proposed solutions, we first define the following threat model considered in this paper. The adversary considered here can be the "honestbut-curious" aggregation server or agents in the system. The aggregation server will honestly follow the designed training protocol but are curious about agents' private data and may infer it from the shared messages. Furthermore, some agents can collude with the aggregation server or each other to infer private information about a specific victim agent. Besides, the adversary could also be the passive outside attacker. These attackers can eavesdrop all shared messages in the execution of the training protocol but will not actively inject false messages into or interrupt message transmissions.

3.2 Classic FL Algorithm: Federated Averaging

As the most widely-used algorithm in the FL setting, Federated Averaging (FedAvg) [McMahan et al., 2017] solves (1) by selecting and distributing the current global model to a subset of agents, running multiple steps of SGD in parallel on the selected agents, and then aggregating the model updates from those agents to improve the global model iteratively. Specifically, FedAvg involves T communication rounds, and each round consists of four stages: First, at the beginning of round t ∈ {0, . . . , T -1}, the server selects a subset of agents W ⊆ [n] to participate and sends them the latest global model θt. Second, each agent i ∈ W initializes its local model θt,0 i to be the global model θt and then performs τ iterations of SGD on its local dataset as follows:

where ηl is the local learning rate. Here, gt,s i := (1/B) ∑z∈ξt,s i ∇l(θt,s i , z) represents the stochastic gradient computed on a mini-batch ξ t,s i of B samples, which a unbiased estimate of ∇fi(θt,s i ). Third, each agent i ∈W uploads the final local model update θt,τ i - θt to the server. Fourth, the server aggregates the local model updates from all participating agents and improves the global model as

The same procedure repeats for the next round.

Privacy and Communication Drawbacks. Although FedAvg avoids the direct information leakage by keeping data locally, the intermediate updates exchanged during the collaboration process such as θt,τ i - θt and θt could still leak private information about the local data as demonstrated in recent advanced attacks such as model inversion attacks [Fredrikson et al., 2015] and membership attacks [Shokri et al., 2017]. Furthermore, in FedAvg, agents need to repeatedly upload local model updates (i.e., θt -θt,τ i ) of large size (e.g., millions of model parameters for modern deep neural network models) to the server and download the newly-updated global model (i.e., θt) from the server in order to learn an accurate global model (e.g., ∼ 1000 rounds for running CNN on MINIST dataset or ∼ 4000 for LSTM on Shakespeare dataset to reach 99% accuracy [McMahan et al., 2017]). Since the privacy loss is proportional to the model dimension and the number of communication rounds, the size of added DP noise could be very large in order to provide a strong local DP guarantee, which will degrade the model accuracy heavily. Besides, as the bandwidth between the server and agents could be rather limited in practice (e.g., wireless connection between the cloud and smartphones), especially for uplink transmissions, the overall communication cost could be very high. The above drawbacks motivate us to develop a new privacy-preserving and communication-efficient FL scheme.

3.3 Proposed Fed-SPAAlgorithm

In this subsection, we present Fed-SPA, our proposed FL scheme with the goal of improving user privacy protection and also communication efficiency while maintaining high model accuracy. To ensure easy integration into existing packages/systems, Fed-SPA follows the same overall structure of FedAvg but differs in the following two key aspects: 1) local models are updated at each agent using a variant of SGD, where the gradients are perturbed by our proposed sparsification-coded DP mechanism; and 2) the global model is updated adaptively instead of simple averaging to accelerate convergence at the server. The entire process of Fed-SPA is summarized in Algorithm 1.

User-Side Sparsification-Coded DP Mechanism. To address privacy and communication aspects simultaneously, we design a sparsification-coded DP mechanism, which integrates Gaussian mechanism and sparsification to reduce the privacy loss of each local iteration and the size of transmitted local model updates at each communication round. Specifically, we use the randk sparsifier to reduce the message size by a factor of d/k, which is defined as follows:

Definition 2 (randk Sparsifier). For parameter k ∈ [d], the operator randk : Rd × Ωk → Rd is defined for a vector x ∈ Rd as

where Ωk = ([d] k ) denotes the set of all k-element subsets of [d]. We omit the second argument whenever it is chosen uniformly at random, i.e., ω ∼u.a.r Ωk.

With the randk sparsifier, our sparsification-coded DP mechanism works as follows: at communication round t, each selected agent i ∈ W first generates its own sparsifier randk(·) by randomly sampling a set of k active coordinates ωt i before performing τ SGD updates, and then, at s-th local iteration, perturbs and sparsifies the stochastic gradient using Gaussian noise and the generated sparsifier randk(·). We use the same sparsifier (with active set ωt i ) across all local iterations of communication round t on agent i so that the transmitted model update (θt,τ i -θt) is still a sparse vector (which has active coordinates ωt i ), preserving the communication efficiency benefit of sparsification. Let p = k/d represent the compression ratio, the update rule at each agent is:

where St i (·) := (1/p) randk(·) is a scaled variant of randk(·), and bt,s i is the noise sampled from the Gaussian distribution N(0, σ2 Id). We use the scaled sparsifier St i (·) so that the sparsified noisy gradient is an unbiased estimate of the true gradient.

Server-Side Adaptive Update. The sparsification-coded DP mechanism will inevitably slow down the convergence speed due to the increased variance of the stochastic gradient used in each iteration, and the privacy loss of each agent increases proportionally with the number of iterations according to the composition property of DP in Lemma 1. To improve the privacy, we speed up the convergence by updating the model in an adaptive manner similar as Adam [Kingma and Ba, 2014] on the server. The adaptive optimizer like

Algorithm 1 The Fed-SPA Algorithm

Require: Initial model θ0, initial momentums [v-1]j ≥ κ2 , ∀j ∈ [d], u-1 = 0d, noise magnitude σ, number of rounds T, number of local iterations τ, compression ratio p, momentum parameters β1, β2, learning rates ηl, ηg, and batch size B.

1: for t = 0 to T -1 do 2: Randomly selects a set of agents W 3: Broadcasts θt to all agents inW 4: for each agent i ∈ W in parallel do 5: Generate a new sparsifier St i (·) 6: θt,0 i ← θt 7: for s = 0 to τ - 1 do 8: Compute a stochastic gradient gt,s i over a minibatch ξ t,s i of B samples 9: θt,s+1 i ← θt,s i - ηlSt i (gt,s i + bt,s i ) where bt,s i ∼ N (0, σ2 Id) 10: end for 11: ∆ti ← θt,τ i -θt and upload ∆ti to the server 12: end for 13: ut ← β1ut-1 + (1 -β1) ∑i∈W ∆ti /|W| 14: vt ← β2vt-1 + (1 -β2)u2t 15: θt+1 ← θt + ηgut/(√vt +κ) 16: end for

Adam can be modified by adding noise to their gradients to provide better DP guarantee, in terms of reducing the iterations needed to achieve a target model accuracy [Yu et al., 2018]. However, there are two main constraints unique to deploying the adaptive optimizer on each agent in the FL setting. First, it is often the case that each agent participate only once or several times intermittently during the entire training process, and hence, replacing SGD with an adaptive optimizer at each agent during the local update stage will perform poorly due to the stale historical information such as the momentum in Adam. Second, maintaining the historical information on resource-constrained agents (e.g. smartphones) is costly for computation and storage resource. To address the above issues, in Fed-SPA, the server, rather than the agents, will carry out the adaptive update without any additional communication. The server maintains two momentum vectors u, v ∈ Rd which get updated at each round. Specifically, at round t, after τ local iterations, each agent i ∈ W uploads its model update ∆ti := θt,τ i -θt to the server to improve the global model as follows:

where β1, β2 ∈ [0, 1) are momentum parameters, ηg is the global learning rate, and κ controls the degree of adaptivity. Note that the math operations in (6) are element-wise.

4 Main Theoretical Results

In this section, we give the formal privacy guarantee and rigorous convergence analysis of Fed-SPA. Before stating our results, we make the following assumptions:

Assumption 1 (Smoothness). The local objective function fi is L-smooth, i.e., for any i ∈ [n] and x, y ∈ Rd , we have fi(y) ≤ fi(x) + 〈∇fi(x), y - x〉 + (L/2)‖y - x‖2 .

Assumption 2 (Bounded Variance). Let gi be the stochastic gradient over the mini-batch sampled from the distribution Di. The function fi has a bounded local variance, i.e., E‖[gi]j - [∇fi(x)]j‖2 ≤ ζ 2 l,j for all x ∈ Rd , j ∈ [d] and i ∈ [n]. Moreover, the global variance is bounded, i.e., (1/n) ∑ni=1 E‖[∇fi(x)]j - [∇f(x)]j‖2 ≤ ζ 2 g,j for all x ∈ Rd , j ∈ [d] and i ∈ [n]. We also denote ζ 2 l := ∑dj=1 ζ 2 l,j and ζ 2 g := ∑dj=1 ζ 2 g,j for convenience.

Assumption 3 (Bounded Gradient). The loss function li(x, z) has G/√d-bounded gradients, i.e., for any data sample z from Di, we have |[∇li(x, z)]j| ≤ G/√d for all x ∈ Rd , j ∈ [d] and i ∈ [n].

Assumption 1 is standard and implies that the global loss function f is also L-smooth. Assumption 2 and Assumption 3 are fairly standard in non-convex optimization literature [Reddi et al., 2020; Kingma and Ba, 2014]. Assumption 3 characterizes the sensitivity of each coordinate of gradient ∇l(x, z) and implies E‖∇l(x, z)‖2 ≤ G2 , which can be enforced by the gradient clipping technique.

4.1 Privacy Analysis

In this subsection, we discuss how the sparsification in our sparsification-coded DP mechanism amplifies the privacy and provide the end-to-end privacy guarantee of Fed-SPA.

In our sparsification-coded DP mechanism, the randk sparsifier does not provide any DP guarantee by itself, but it amplifies the privacy guarantee provided by additive Gaussian noises. To analyze the end-to-end privacy, we first need to analyze the sensitivity of the sparsified gradient in Line 9, Algorithm 1. With the randk sparsifier, the active coordinate set ω is chosen independent of data and does not leak privacy, and only the values of active coordinates {[x]j, j ∈ ω} contain private data information and need to be protected. Therefore, in our sparsification-coded DP mechanism, only values of active coordinates of the gradient are actually perturbed by the Gaussian noise. More precisely, let ωt i denote the active coordinate set for participating agent i at round t, the sparsified noisy gradient at each local iteration can be represented as St i (gt,s i + bt,s i ) = [gt,s i +bt,s i ]ωt i /p = [gt,s i ]ωt i /p + [bt,s i ]ωt i /p, where we can observe that the amount of added noise is proportional to k, the number of active coordinates, and is reduced by a factor of d/k compared with the standard Gaussian mechanism. In the following, we analyze the sensitivity of [gt,s i ]ωt i and then compute the privacy guarantee after adding noise [bt,s i ]ωt i . For agent i, given any two neighboring datasets ξ t,s i and ` ξ t,s i that have the same size B but differ in one data sample (e.g., z ∈ ξ t,s i and ` z ∈ ` ξ t,s i ). The L2 sensitivity of [gt,s i ]ωt i can be denoted as φ2ωt i = max ‖[gt,s i ]ωt i - [∇fi(θt,s i , ` ξ t,s i )]ωt i ‖2 = max ‖(1/B)[∇l(θt,s i , z) - ∇l(θt,s i , ` z)]ωt i ‖2 and is upperbounded by 2pG2 /B2 following Assumption 3. We observe that the sensitivity of [gt,s i ]ωt i is proportional to the compression ratio p, reducing the privacy loss according to Lemma 2.

Then, we give the end-to-end DP guarantee of Fed-SPA in Theorem 1 and provide the proof in Appendix E. Given a fixed value of δ, ϵ is computed numerically by searching an optimal α that minimizes ϵ. We observe that the noise magnitude σ is proportional to p, which implies that sparsification, i.e., when p < 1, can reduce the magnitude of Gaussian noise and hence improve the model accuracy.

Theorem 1 (Privacy Guarantee). Suppose the mini-batch ξ t,s i is sampled without replacement at each iteration. Let q := B/m be the data sampling rate. Let Ii represent the number of rounds agent i participates during the training. Under Assumption 3, if σ′2 = σ2B2 /2pG2 ≥ 0.7, Fed-SPA achieves (ϵ, δ)-DP for agent i, where

for any α ≤ (2/3)σ2 log (1/qα(1 + σ′2 ))+1 and δ ∈ (0, 1).

4.2 Convergence Analysis

In this subsection, we present the convergence results of FedSPA for general loss functions satisfying Assumptions 1-3. For ease of illustration, we assume full participation, i.e., |W| = n, and β1 = 0, though our analysis can be easily extended to β1 > 0 and partial participation (i.e., |W| < n, see Appendix H for details). As f(·) may be non-convex, we study the gradient of the global model θt as t increases. We give the result in Theorem 2 and the proof in the full version.

Theorem 2 (Convergence Result). Let Assumptions 1-3 hold, and L,G, ζl, ζg be as defined therein. Suppose the local learning rate satisfies ηl ≤ min{1/8Lτ, (1/8τ ) min{κ√d/G, (κ2√d/GηgL)1/2 }}. Let ζ 2 dp = (G2 + ζ 2 l )/p + pdσ2 , then the iterates of

Algorithm 1 satisfy:

where f ∗ is the optimal objective value.

We restate the above result for a specific choice of ηl, ηg and κ in Lemma 3 to highlight the dependence on τ and T. Note that when T is sufficiently large compared to τ, O(1/√nτT) is the dominant term in Lemma 3. Therefore, Fed-SPA converges at a rate of O(1/√nτT ), which matches the best known rate for the general non-convex setting of our interest [Reddi et al., 2020]. We also note that both sparsification and Gaussian noise will slow down the convergence. However, a small compression ratio p can reduce the amount of added noise (i.e., the term pdσ2 ) by a factor of 1/p, which implies the privacy amplification effect of sparsification.

Lemma 3. Choose the local learning rate ηl = Θ(1/Lτ √T) that satisfies the condition in Theorem 2. Suppose ηg = Θ(√nτ) and κ = G/√dL, then the iterates of Algorithm 1 satisfy

when T is sufficiently large.

5 Experimental Evaluation

The goal of this section is to evaluate the performance of FedSPA on several benchmark datasets. We aim at evaluating the performance of Fed-SPA with different levels of compression and comparing them with the performance of the following three schemes: 1) FedAvg: the classic FL algorithm; 2) DPFed: this baseline follows the algorithm of FedAvg except that the stochastic gradient is perturbed by adding Gaussian noise N(0, σ2 Id); 3) cpSGD [Agarwal et al., 2018]: this baseline follows the algorithm of classic distributed SGD except that the stochastic gradient is quantized into some discrete domain and then perturbed using Binomial mechanism.

5.1 Experimental Setup

We explore two widely-used benchmark datasets in FL: MNIST [LeCun et al., 1998] and CIFAR-10 [Krizhevsky et al., 2009]. The MNIST dataset consists of 10 classes of 28 × 28 handwritten digit images. There are 60K training examples and 10K testing examples, which are partitioned among 100 agents, each containing 600 training and 100 testing examples. The CIFAR-10 dataset consists of 10 classes of 32 × 32 images. There are 50K training examples and 10K testing examples in the dataset, which are partitioned into 100 agents, each containing 500 training and 100 testing examples. We use a CNN model for the MNIST dataset, which has two 5 × 5 convolutional layers (the first with 10 filters, the second with 20 filters, each followed with 2 × 2 max pooling and ReLu activation), a fully connected layer with 50 units and ReLu activation, and a final softmax output layer. For the CIFAR-10 dataset, we use a CNN model that consists of three 3 × 3 convolution layers (the first with 64 filters, the second with 128 filters, the third with 256 filters, each followed with 2 × 2 max pooling and ReLu activation), two fully connected layers (the first with 128 units, the second with 256 units, each followed with ReLu activation), and a final softmax output layer.

We set the privacy failure probability δ = 10-3 and the sampling ratio of agents r = |W|/n = 0.1 for all experiments by default. Since cpSGD follows the classic distributed SGD scheme, we have τ = 1 and r = 1.0 for cpSGD. We tune the hyperparameters using grid-search. We set the number of local iterations τ = 300 for MNIST and τ = 50 for CIFAR-10. The details of other hyperparameter settings are given in the full version. The per-coordinate sensitivity G/√d is selected during an initialization round for each scheme by taking the median value over N absolute values.

5.2 Experimental Results

Table 1 shows the best accuracy over 45 communication rounds for each scheme on the MNIST dataset, and Table 2 represents the best accuracy over 200 rounds for each scheme on the CIFAR-10 dataset. Assume each value of the model parameter is represented by a 32-bit floating number. The Compression ratio for Fed-SPA is calculated as p = k/d. For cpSGD, p = log2(m+ b)/32, where b implies the b-bit quantization and m is the parameter for the Binomial distribution Bin(m, 0.5). For FedAvg and DP-Fed, we have p = 1.0. Cost is the average bandwidth consumption calculated as p×d×32×T ×r, where r is the sampling probability of devices and T is the communication rounds. Note that since how to analyze Binomial mechanism in cpSGD using RDP is still unknown, we account the privacy loss ϵ of cpSGD using the standard subsampling amplification [Balle et al., 2018] and advanced composition [Dwork et al., 2010].

Without compression, i.e., when p = 1.0, Fed-SPA outperforms cpSGD and DP-Fed on both datasets as the server in Fed-SPA updates the global model adaptively to speed up the convergence, and its best accuracy to achieve (1.0, 10-3 )- DP is close to the best accuracy of FedAvg under the same communication cost. Note that since the Binomial noise used in cpSGD is not as concentrated as the Gaussian noise used in Fed-SPA and DP-Fed, the model accuracy of cpSGD degrades heavily, and hence to achieve a target accuracy, the privacy loss of cpSGD is very large. As the compression ratio p decreases, the performance of Fed-SPA on both datasets does not degrade much, compared with cpSGD which cannot achieve a reasonable privacy guarantee when p ≤ 0.1. More importantly, Fed-SPA for MNIST achieves a higher accuracy than DP-Fed under the same privacy cost, while saving 86% communication cost when p = 0.05. The reason is that decreasing p also lowers the sensitivity of the sparsified gradient which has a direct impact on the noise magnitude to achieve a target privacy guarantee, as explain in Section 4.1. We observe a similar trend for CIFAR-10 from Table 2: Fed-SPA performs better when the compression ratio is small, e.g., when p ≤ 0.4, as the sensitivity in this case is small.

Then, we show the privacy-accuracy trade-off of Fed-SPA for both datasets with different levels of compression in Figure 1. As we mentioned above, a small compression ratio results in a smaller sensitivity, and hence less Gaussian noise will be added to the model. On the other hand, the compression ratio cannot be arbitrarily small as it will increase the variance of gradient as explained in Section 4.2. Therefore, we should find an optimal p that is small enough to reduce the size of additive Gaussian noise but large enough to avoid large compression error. For both datasets, we can observe that when the privacy budget ϵ is limited (e.g., ϵ < 1.0), a small enough p (e.g., p = 0.8 for MNIST and p = 0.2 for CIFAR-10) achieves higher accuracy as it reduces the size of Gaussian noise. As ϵ increases, the size of Gaussian noise decreases, and hence Fed-SPA with larger p performs better due to the smaller compression error.

6 Conclusion

This paper has proposed Fed-SPA, a new FL scheme based on sparsification-coded DP mechanism and server-side adaptive update, to improve privacy-accuracy trade-off and achieve communication efficiency at the same time. We have provided rigorous convergence and privacy analysis of Fed-SPA. Extensive experiments based on benchmark datasets have been conducted to verify the effectiveness of the proposed scheme and numerically show the trade-off between privacy guarantee and model accuracy. For future work, we plan to investigate the interplay of privacy protection with other communication-efficient techniques in FL.

Acknowledgements

The work of R. Hu and Y. Gong was supported by the U.S. National Science Foundation under grants US CNS-2029685 and CNS-1850523. The work of Y. Guo was supported by the U.S. National Science Foundation under grant US CNS2029685.