Title: DIFFERENTIALLY PRIVATE FEDERATED LEARNING: A CLIENT LEVEL PERSPECTIVE

Abstract: Federated learning is a recent advance in privacy protection. In this context, a trusted curator aggregates parameters optimized in decentralized fashion by multiple clients. The resulting model is then distributed back to all clients, ultimately converging to a joint representative model without explicitly having to share the data. However, the protocol is vulnerable to differential attacks, which could originate from any party contributing during federated optimization. In such an attack, a client's contribution during training and information about their data set is revealed through analyzing the distributed model. We tackle this problem and propose an algorithm for client sided differential privacy preserving federated optimization. The aim is to hide clients' contributions during training, balancing the trade-off between privacy loss and model performance. Empirical studies suggest that given a sufficiently large number of participating clients, our proposed procedure can maintain client-level differential privacy at only a minor cost in model performance.

1. INTRODUCTION:

Lately, the topic of security in machine learning is enjoying increased interest. This can be largely attributed to the success of big data in conjunction with deep learning and the urge for creating and processing ever larger data sets for data mining. However, with the emergence of more and more machine learning services becoming part of our daily lives, making use of our data, special measures must be taken to protect privacy. Unfortunately, anonymization alone often is not sufficient Narayanan & Shmatikov (2008) ; Backstrom et al. (2007) and standard machine learning approaches largely disregard privacy aspects and are susceptible to a variety of adversarial attacks Melis et al. (2018) . In this regard, machine learning can be analyzed to recover private information about the participating user or employed data as well Oh et al. (2018) ; Shokri et al. (2017) ; Dang et al. (2017) ; Fredrikson et al. (2015) . Carlini et al. (2018) propose a measure for to assess the memorization of privacy related data. All the aspects of privacy-preserving machine learning are aggravated when further restrictions apply such as a limited number of participating clients or restricted communication bandwidth such as mobile devices Google (2017) .

In order to alleviate the need of explicitly sharing data for training machine learning models, decentralized approaches have been proposed, sometimes referred to as collaborative Shokri & Shmatikov (2015) or federated learning McMahan et al. (2017) . In federated learning McMahan et al. (2017) a model is learned by multiple clients in decentralized fashion. Learning is shifted to the clients and only learned parameters are centralized by a trusted curator. This curator then distributes an aggregated model back to the clients. However, this alone is not sufficent to preserve privacy. In Orekondy et al. (2018) it is shown that clients be identified in a federated learning setting by the model updates alone, necessitating further steps.

Clients not revealing their data is an advance in privacy protection. However, when a model is learned in conventional way, its parameters reveal information about the data that was used during training. In order to solve this issue, the concept of differential privacy (dp) Dwork (2006) for learning algorithms was proposed by Abadi et al. (2016) . The aim is to ensure a learned model does not reveal whether a certain data point was used during training.

We propose an algorithm that incorporates a dp-preserving mechanism into federated learning. However, opposed to Abadi et al. (2016) we do not aim at protecting w.r.t. a single data point only. Rather, we want to ensure that a learned model does not reveal whether a client participated during decentralized training. This implies a client's whole data set is protected against differential attacks from other clients.

Our main contributions: First, we show that a client's participation can be hidden while model performance is kept high in federated learning. We demonstrate that our proposed algorithm can achieve client level differential privacy at a minor loss in model performance. An independent study McMahan et al. (2018) , published at the same time, proposed a similar procedure for client level-dp. Experimental setups however differ and McMahan et al. (2018) also includes elementlevel privacy measures. Second, we propose to dynamically adapt the dp-preserving mechanism during decentralized training. Empirical studies suggest that model performance is increased that way. This stands in contrast to latest advances in centralized training with differential privacy, were such adaptation was not beneficial. We can link this discrepancy to the fact that, compared to centralized learning, gradients in federated learning exhibit different sensibilities to noise and batch size throughout the course of training.

2. BACKGROUND:



2.1. FEDERATED LEARNING:

In federated learning McMahan et al. (2017) , communication between curator and clients might be limited (e.g. mobile phones) and/or vulnerable to interception. The challenge of federated optimization is to learn a model with minimal information overhead between clients and curator. In addition, clients' data might be non-IID, unbalanced and massively distributed. 

2.2. LEARNING WITH DIFFERENTIAL PRIVACY:

A lot of research has been conducted in protecting differential privacy on data level when a model is learned in a centralized manner. This can be done by incorporating a dp-preserving randomized mechanism (e.g. the Gaussian mechanism) into the learning process.

We use the same definition for differential privacy in randomized mechanisms as Abadi et al. (2016) :

A randomized mechanism M : D → R, with domain D and range R satisfies ( , δ)-differential privacy, if for any two adjacent inputs d, d ∈ D and for any subset of outputs S ⊆ R it holds that P [M (d) ∈ S] ≤ e P r[M (d ) ∈ S] + δ. In this definition, δ accounts for the probability that plain -differential privacy is broken.

The Gaussian mechanism (GM) approximates a real valued function f : D → R with a differentially private mechanism. Specifically, a GM adds Gaussian noise calibrated to the functions data set sensitivity S f . This sensitivity is defined as the maximum of the absolute distance

f (d) -f (d ) 2 ,

where d and d are two adjacent inputs. A GM is then defined as

M (d) = f (d) + N (0, σ 2 S 2 f ).

In the following we assume that σ and are fixed and evaluate an inquiry to the GM about a single approximation of f (d). We can then bound the probability that -dp is broken according to: δ ≤ 5 4 exp(-(σ ) 2 /2) (Theorem 3.22 in Dwork & Roth (2014) ). It should be noted that δ is accumulative and grows if the consecutive inquiries to the GM. Therefore, to protect privacy, an accountant keeps track of δ. Once a certain threshold for δ is reached, the GM shall not answer any new inquires.

Recently, Abadi et al. (2016) proposed a differentially private stochastic gradient descent algorithm (dp-SGD). dp-SGD works similar to mini-batch gradient descent but the gradient averaging step is approximated by a GM. In addition, the mini-batches are allocated through random sampling of the data. For being fixed, a privacy accountant keeps track of δ and stops training once a threshold is reached. Intuitively, this means training is stopped once the probability that the learned model reveals whether a certain data point is part of the training set exceeds a certain threshold.

2.3. CLIENT-SIDED DIFFERENTIAL PRIVACY IN FEDERATED OPTIMIZATION:

We propose to incorporate a randomized mechanism into federated learning. However, opposed to Abadi et al. (2016) we do not aim at protecting a single data point's contribution in learning a model. Instead, we aim at protecting a whole client's data set. That is, we want to ensure that a learned model does not reveal whether a client participated during decentralized training while maintaining high model performance.

3. PROPOSED METHOD:

In the framework of federated optimization McMahan et al. (2017) , the central curator averages client models (i.e. weight matrices) after each communication round. In our proposed algorithm, we will alter and approximate this averaging with a randomized mechanism. This is done to hide a single client's contribution within the aggregation and thus within the entire decentralized learning procedure.

The randomized mechanism we use to approximate the average consists of :

• Random sub-sampling (step 1 in Fig. 1 ): Let K be the total number of clients. In each communication round a random subset Z t of size m t ≤ K is sampled. The curator then distributes the central model w t to only these clients. The central model is optimized by the clients' on their data. The clients in Z t now hold distinct local models {w k } mt k=0 . The difference between the optimized local model and the central model will be referred to as client k's update ∆w k = w kw t . The updates are sent back to the central curator at the end of each communication round.

• Distorting (step 3 and 4 in Fig. 1 ): A Gaussian mechanism is used to distort the sum of all updates. This requires knowledge about the set's sensitivity with respect to the summing operation. We can enforce a certain sensitivity by using scaled versions instead of the true updates:

wk = w k /max(1, w k 2 S

). Scaling ensures that the second norm is limited ∀k, wk 2 < S. The sensitivity of the scaled updates with respect to the summing operation is thus upper bounded by S. The GM now adds noise (scaled to sensitivity S) to the sum of all scaled updates. Dividing the GM's output by m t yields an approximation to the true average of all client's updates, while preventing leakage of crucial information about an individual.

A new central model w t+1 is allocated by adding this approximation to the current central model w t .

w t+1 = w t + 1 m t Sum of updates clipped at S mt k=0 w k /max(1, w k 2 S ) + Noise scaled to S N (0, σ 2 S 2 )

Gaussian mechanism approximating sum of updates

When factorizing 1/m t into the Gaussian mechanism, we notice that the average's distortion is governed by the noise variance S 2 σ 2 /m. However, this distortion should not exceed a certain limit.

Otherwise too much information from the sub-sampled average is destroyed by the added noise and there will not be any learning progress. GM and random sub-sampling are both randomized mechanisms. (Indeed, Abadi et al. (2016) used exactly this kind of average approximation in dp-SGD. However, there it is used for gradient averaging, hiding a single data point's gradient at every iteration). Thus, σ and m also define the privacy loss incurred when the randomized mechanism provides an average approximation.

In order to keep track of this privacy loss, we make use of the moments accountant as proposed by Abadi et al. Abadi et al. (2016) . This accounting method provides much tighter bounds on the incurred privacy loss than the standard composition theorem (3.14 in Dwork & Roth (2014) ). Each time the curator allocates a new model, the accountant evaluates δ given , σ and m. Training shall be stopped once δ reaches a certain threshold, i.e. the likelihood, that a clients contribution is revealed gets too high. The choice of a threshold for depends on the total amount of clients K. To ascertain that privacy for many is not preserved at the expense of revealing total information about a few, we have to ensure that δ 1 K , refer to Dwork & Roth (2014) chapter 2.3 for more details. Choosing S: When clipping the contributions, there is a trade-off. On the one hand, S should be chosen small such that the noise variance stays small. On the other hand, one wants to maintain as much of the original contributions as possible. Following a procedure proposed by Abadi et al. (2016) , in each communication round we calculate the median norm of all unclipped contributions and use this as the clipping bound S = median{ w k } k∈Zt . We do not use a randomized mechanism for computing the median, which, strictly speaking, is a violation of privacy. However, the information leakage through the median is small (Future work will contain such a privacy measure).

Choosing σ and m: for fixed S, the ratio r = σ 2 /m governs distortion and privacy loss. It follows that the higher σ and the lower m, the higher the privacy loss. The privacy accountant tells us that for fixed r = σ 2 /m, i.e. for the same level of distortion, privacy loss is smaller for σ and m both being small. An upper bound on the distortion rate r and a lower bound on the number of sub-sampled clients m would thus lead to a choice of σ. A lower bound on m is, however, hard to estimate. That is, because data in federated settings is non-IID and contributions from clients might be very distinct. We therefore define the between clients variance V c as a measure of similarity between clients' updates.

Definition. Let w i,j define the (i, j)-th parameter in an update of the form w ∈ R q×p , at some communication round t. For the sake of clarity, we will drop specific indexing of communication rounds for now. The variance of parameter (i, j) throughout all K clients is defined as,

VAR[ w i,j ] = 1 K K k=0 ( w k i,j -µ i,j ) 2 ,

where

µ i,j = 1 K K k=1 w k i,j .

We then define V c as the sum over all parameter variances in the update matrix as,

V c = 1 q × p q i=0 p j=0 VAR[ w i,j ].

Further, the Update scale U s is defined as,

U s = 1 q × p q i=0 p j=0 µ 2 i,j .

Algorithm 1 Client-side differentially private federated optimization. K is the number of participating clients; B is the local mini-batch size, E the number of local epochs, η is the learning rate, {σ} T t=0 is the set of variances for the GM. {m t } T t=0 determines the number of participating clients at each communication round. defines the dp we aim for. Q is the threshold for δ, the probability that -dp is broken. T is the number of communication rounds after which δ surpasses Q. B is a set holding client's data sliced into batches of size B 1: procedure SERVER EXECUTION 2:

Initialize: w 0 , Accountant( , K) initialize weights and the priv. accountant 

w t+1 ← w t + 1 m ( K k=1 w k t+1 /max(1, ζ k S ) + N (0, S 2 • σ 2 )) Update central

4. EXPERIMENTS:

In order to test our proposed algorithm we simulate a federated setting. For the sake of comparability, we choose a similar experimental setup as McMahan et al. (2017) did. We divide the sorted MNIST set into shards. Consequently, each client gets two shards. This way most clients will have samples from two digits only. A single client could thus never train a model on their data such that it reaches high classification accuracy for all ten digits.

We are investigating differential privacy in the federated setting for scenarios of K ∈ {100, 1000, 10000}. In each setting the clients get exactly 600 data points. For K ∈ {1000, 10000}, data points are repeated.

For all three scenarios K ∈ {100, 1000, 10000} we performed a cross-validation grid search on the following parameters: In accordance to Abadi et al. (2016) we fixed to the value of 8. During training we keep track of privacy loss using the privacy accountant. Training is stopped once δ reaches e -3, e -5, e -6 for 100, 1000 and 10000 clients, respectively. In addition, we also analyze the between clients variance over the course of training.

5. RESULTS:

In the cross validation grid search we look for those models that reach the highest accuracy while staying below the respective bound on δ. In addition, when multiple models reach the same accuracy, the one with fewer needed communication rounds is preferred.

Table 1 holds the best models found for K ∈ {100, 1000, 10000}. We list the accuracy (ACC), the number of communication rounds (CR) needed and the arising communication costs (CC).

Communication costs are defined as the number of times a model gets send by a client over the course of training, i.e.

T t=0 m t . In addition, as a benchmark, Table 1 also holds the ACC, CR and CC of the best performing non-differentially private model for K = 100. In Fig. 2 , the accuracy of all four best performing models is depicted over the course of training.

In Fig. 3 , the accuracy of non-differentially private federated optimization for K = 100 is depicted again together with the between clients variance and the update scale over the course of training. 

6. DISCUSSION:

As intuitively expected, the number of participating clients has a major impact on the achieved model performance. For 100 and 1000 clients, model accuracy does not converge and stays significantly below the non-differentially private performance. However, 78% and 92% accuracy for K ∈ {100, 1000} are still substantially better than anything clients would be able to achieve when only training on their own data. In domains where K lays in this order of magnitude and differential privacy is of utmost importance, such models would still substantially benefit any client participating. An example for such a domain are hospitals. Several hundred could jointly learn a model, while information about a specific hospital stays hidden. In addition, the jointly learned model could be used as an initialization for further client-side training.

For K = 10000, the differentially private model almost reaches accuracies of the non-differential private one. This suggests that for scenarios where many parties are involved, differential privacy comes at almost no cost in model performance. These scenarios include mobile phones and other consumer devices.

In the cross-validation grid search we also found that raising m t over the course of training improves model performance. When looking at a single early communication round, lowering both m t and σ t in a fashion such that σ 2 t /m t stays constant, has almost no impact on the accuracy gain during that round. however, privacy loss is reduced when both parameters are lowered. This means more communication rounds can be performed later on in training, before the privacy budget is drained. In subsequent communication rounds, a large m t is unavoidable to gain accuracy, and a higher privacy cost has to be embraced in order to improve the model. This observation can be linked to recent advances of information theory in learning algorithms. As observable in Fig. 3 , Shwartz-Ziv and Tishby Shwartz-Ziv & Tishby (2017) suggest, we can distinguish two different phases of training: label fitting and data fitting phase.

During label fitting phase, updates by clients are similar and thus V c is low, as Fig. 3 shows. U c , however, is high during this initial phase, as big updates to the randomly initialized weights are performed. During data fitting phase V c rises. The individual updates w k look less alike, as each client optimizes on their data set. U c however drastically shrinks, as a local optima of the global model is approached, accuracy converges and the contributions cancel each other out to a certain extend. Figure 3 shows these dependencies of V c and U c .

We can conclude: i) At early communication rounds, small subsets of clients might still contribute an average update w t representative of the true data distribution ii) At later stages a balanced (and therefore bigger) fraction of clients is needed to reach a certain representativity for an update. iii) High U c makes early updates less vulnerable to noise.

7. CONCLUSION:

We were able to show through first empirical studies that differential privacy on a client level is feasible and high model accuracies can be reached when sufficiently many parties are involved. Furthermore, we showed that careful investigation of the data and update distribution can lead to optimized privacy budgeting. For future work, we plan to derive optimal bounds in terms of signal to noise ratio in dependence of communication round, data representativity and between-client variance as well as further investigate the connection to information theory. Additionally, we plan to further investigate the dataset dependency of the bounds. For assessing further applicability in bandwith-limited settings, we plan to investigate the applicability of proposed approach in context of compressed gradients such as proposed by Lin et al. (2018) .

:



Figures and Tables:

The algorithm 'federated averaging' recently proposed by McMahan et al. (2017), tackles these challenges. During multiple rounds of communication between curator and clients, a central model is trained. At each communication round, the curator distributes the current central model to a fraction of clients. The clients then perform local optimization. To minimize communication, clients might take several steps of mini-batch gradient descent during a single communication round. Next, the optimized models are sent back to the curator, who aggregates them (e.g. averaging) to allocate a new central model. Depending on the performance of the new central model, training is either stopped or a new communication round starts. In federated learning, clients never share data, only model parameters.

Figure 1: Illustration of differentially private federated learning on a client level. Step 1: At each communication round t, m t out of total K clients are sampled uniformly at random. The central model w t is distributed to the sampled clients. Step 2: The selected clients optimize w t on their local data, leading to w k . Clients centralize their local updates: w k = w kw t . Step 3: The updates are clipped such that their sensitivity can be upper bounded. The clipped updates are averaged. Step 4: The central model is updated adding the averaged, clipped updates and distorting them with Gaussian noise tuned to the sensitivity's upper bound. Having allocated the new central model, the procedure can be repeated. However, before starting step 1, a privacy accountant evaluates the privacy loss that would arise through performing another communication round. If that privacy loss is acceptable, a new round may start.

model 11: function CLIENTUPDATE(k, w t ) w t+1 , ζ return clipped update and norm of update

Figure 2: Accuracy of digit classification from non-IID MNIST-data held by clients over the course of decentralized training. For differentially private federated optimization, dots at the end of accuracy curves indicate that the δ-threshold was reached and training therefore stopped.

Figure 3: Scenario of 100 clients, non-differentially private: accuracy, between clients variance and update scale over the course of federated optimization.

Experimental results for differentially private federated learning and comparison to nondifferentially private federated learning (Non-DP). Scenarios of 100, 1000 and 10000 clients for a privacy budget of = 8. δ is the highest acceptable probability of -differential privacy being broken. Once δ is reached, training is stopped. Accuracy denoted as 'ACC', number of communication as 'CR' and communication costs as 'CC'.

Table content: <table><tr><td>CLIENTS</td><td>δ</td><td>ACC</td><td>CR</td><td>CC</td></tr><tr><td>100</td><td colspan="3">NON-DP 0.97 380</td><td>38000</td></tr><tr><td>100</td><td>e -3</td><td>0.78</td><td>11</td><td>550</td></tr><tr><td>1000</td><td>e -5</td><td>0.92</td><td>54</td><td>11880</td></tr><tr><td>10000</td><td>e -6</td><td colspan="3">0.96 412 209500</td></tr></table>

Peer review (iclr2019):
 The main claim the authors make is that providing privacy in learning should go beyond just privacy for individual records to providing privacy for data contributors which could be an entire hospital. Adding privacy by design to the machine learning pipe-line is an important topic. Unfortunately, the presentation of this paper makes it hard to follow. Some of the issues in this paper are technical and easy to resolve, such as citation format (see below) or consistency of notation (see below). Another example is that although the method presented here is suitable only for gradient based learning this is not stated clearly. However, other issues are more fundamental: 1. The main motivation for this work is providing privacy to a client which could be a hospital as opposed to providing privacy to a single record – why is that an important task? Moreover, there are standard ways to extend differential privacy from a single record to a set of r records (see dwork & Rote, 2014 Theorem 2.2), in what sense the method presented here different than these methods? 2. Another issue with the hospitals motivation is that the results show that when the number of parties is 10,000 the accuracy is close to the baseline. However, there are only 5534 registered hospitals in the US in 2018 according to the American Hospital Association (AHA): https://www.aha.org/statistics/fast-facts-us-hospitals. Therefore, are the sizes used in the experiments reasonable? 3. In the presentation of the methods, it is not clear what is novel and what was already done by Abadi et al., 2016 4. The theoretical analysis of the algorithm is only implied and not stated clearly 5. In reporting the experiment setup key pieces of information are missing which makes the experiment irreproducible. For example, what is the leaning algorithm used? If it is a neural network, what was its layout? What type of cross validation was used to tune parameters? 6. In describing the experiment it says that “For K.in.{1000,10000} data points are repeated.” This could mean that a single client holds the same point multiple times or that multiple clients hold the same data point. Which one of them is correct? What are the implications of that on the results of the experiment? 7. Since grid search is used to tune parameters, more information is leaking which is not compensated for by, for example, composition bounds 8. The results of the experiments are not contrasted against prior art, for example the results of Abadi et al., 2016. Additional comments 9. The introduction is confusing since it uses the term “federated learning” as a privacy technology. However federated learning discusses the scenario where the data is distributed between several parties. It is not necessarily the case that there are also privacy concerns associated, in many cases the need for federated learning is due to performance constraints. 10. In the abstract the term “differential attacks” is used – what does it mean? 11. “An independent study McMahan et al. (2018), published at the same time”- since you refer to the work of McMahan et al before your paper was reviewed, it means that the work of McMahan et al came out earlier. 12. In the section “Choosing and ” it is stated that the higher .sigma and the lower m, the higher the privacy loss. Isn’t the privacy loss reduced when .sigma is larger? Moreover, since you divide the gradients by m_t then the sensitivity of each party is of the order of S/m and therefore it reduces as m gets larger, hence, the privacy loss is smaller when m is large. 13. At the bottom of page 4 and top of page 5 you introduce variance related terms that are never used in the algorithm or any analysis (they are presented in Figure 3). The variance between clients can be a function of how the data is split between them. If, for example, each client represents a different demography then the variance may be larger from the beginning. 14. In the experiments (Table 1), what does it mean for .delta^.prime to be e-3, e-5 or e-6? Is it 10^{-3}, 10^{-5} and 10^{-6}? 15. The methods presented here apply only for gradient descent learning algorithms, but this is not stated clearly. For example, would the methods presented here apply for learning tree based models? 16. The citations are used incorrectly, for example “sometimes referred to as collaborative Shokri & Shmatikov (2015)” should be “sometimes referred to as collaborative (Shokri & Shmatikov, 2015)”. This can be achieved by using .citep in latex. This problem appears in many places in the paper, including, for example, “we make use of the moments accountant as proposed by Abadi et al. Abadi et al. (2016).” Which should be “we make use of the moments accountant as proposed by Abadi et al. (2016).” In which case you should use only .cite and not quote the name in the .tex file. 17. “We use the same deﬁnition for differential privacy in randomized mechanisms as Abadi et al. (2016):” – the definition of differential privacy is due to Dwork, McSherry, Nissim & Smith, 2006 18. Notation is followed loosely which makes it harder to follow at parts. For example, you use “m_t” for the number of participants in time t but in some cases, you use only m as in “Choosing and ”. 19. In algorithm 1 the function ClientUpdate receives two parameters however the first parameter is never used in this function. 20. Figure 2: I think it would be easier to see the results if you use log-log plot 21. Discussion: “For K=10000, the differrntially private model almost reaches accuracies of the non-differential private one.” – it is true that the model used in this experiment achieves an accuracy of 0.97 without DP and the reported number for K=10000 is 0.96 which is very close. However, the baseline accuracy of 0.97 is very low for MNIST. 22. In the bibliography you have Brendan McMahan appearing both as Brendan McMahan and H. Brendan McMahan It is possible that underneath that this work has some hidden jams, however, the presentation makes them hard to find.