DP-REC: Private & Communication-Efficient Federated Learning
Authors: Aleksei Triastcyn
Matthias Reisser
Christos Louizos
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated learning
differential privacy
compression
communication efficiency

Abstract: Privacy and communication efficiency are important challenges in federated training of neural networks, and combining them is still an open problem. In this work, we develop a method that unifies highly compressed communication and differential privacy (DP). We introduce a compression technique based on Relative Entropy Coding (REC) to the federated setting. With a minor modification to REC, we obtain a provably differentially private learning algorithm, DP-REC, and show how to compute its privacy guarantees. Our experiments demonstrate that DP-REC drastically reduces communication costs while providing privacy guarantees comparable to the state-of-the-art.

Under review as a conference paper at ICLR 2022
DP-REC: PRIVATE & COMMUNICATION- FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Privacy and communication efficiency are important challenges in federated train- ing of neural networks, and combining them still an open problem. In this work, we develop a method that unifies highly compressed communication and differential privacy (DP). We introduce a compression technique based on Relative Entropy Coding (REC) to the federated setting. With minor modification to REC, we obtain a provably differentially private learning algorithm, DP-REC, and show how to compute its privacy guarantees. Our experiments demonstrate that DP-REC drastically reduces communication costs while providing privacy guarantees comparable to the state-of -art
INTRODUCTION
The performance of modern neural-network-basee machine learning models scales exceptionally well with the amount of data that they are trained on (Kaplan et al. Henighan et al. 2020). At the same time, industry (Xiao & Karlin), legislators (Dwork 2019 Voigt & Von dem Bussche 2017) and consumers (Laziuk] 2021) have become more conscious about the need to protect the privacy of the data that might be used in training such models. Federated learning (FL) describes machine learning principle that enables learning on decentralized data by computing updates on-device. Instead of sending its data a central location, a "client" in federation of devices sends model updates computed on its data to the central server. Such an approach to learning from decentralized data promises to unlock the computing capabilities of billions of edge devices, enable personalized models and new applications in e.g. healthcare due to the inherently more private nature of the approach.
On the other hand, the federated paradigm brings challenges along many dimensions such as learning devices, heterogeneous compute and communication
from non-i.i.d. data, eesource-constraiie capabilities, questions of fairness and representation, as well as the focus of our paper: communication overhead and characterization of privacy. Neural network training requires many passes over the data, resulting repeated transfer of the model and updates between the server and the clients, potentially making communication a primary bottleneck (Kairouz et al. 2019 Wang et al. (222I). Compressing updates is an active area of research in FL and an essential step in "untethering" edge devices from WiFi. Moreover, while FL is intuitively more private through keeping data on-device, client updates have been shown to reveal sensitive information, even allowing to reconstruct a client's training data (Geiping al. 2020). To truly protect client privacy, more rigorous mathematical notion of Differential Privacy (DP) is widely adopted as the de-facto standard in FL. More specifically, DP for client-level, which provides plausible deniability of an individual client's
FL is usually defined contribution to the federated model. Both aspects of FL. communication efficiency and differential privacy, have been extensively studied separation. Effective combination of the two, however, an open problem and an active area of research (Kairouz et al.) 2021 Chen et al.) 2020 Girgis et al. 2020). Some methods offer very limited compression capabilities for comparable utility (Kairouz) al. 2021). whereas others (Girgis et al., 2020) offer significant compression but require additional compromises, due to a looser privacy composition.
In this work, we present Differentially Private Relative Entropy Coding (DP-REC), a unified approach to jointly tackle privacy and communication efficiency. DP-REC makes use of the information limiting constraints of DP to encode the client updates in FL with extremely short messages. First, build our method based on compression without quantization; namely, the lossy variant of Relative Entropy Coding (REC), recently proposed by Flamich et al. (2020). Second, show that it can be

---

Under review as a conference paper at ICLR 2022
modified to satisfy DP, and provide proof of its privacy guarantees along with the appropriate accounting technique. Third, we run extensive evaluation on datasets and 3 types of models to demonstrate that our algorithm achieves extreme compression of client-to-server updates (down to 7 bits per tensor) at privacy levels & < 1 with a small impact on utility (< 6.5% accuracy reduction on FEMNIST compared to DP-FedAvg). Additionally, we show how reduce server-to-client communication by sending a history of updates accumulated since the client's 's last participation.
2 DP-REC FOR PRIVATE AND EFFICIENT COMMUNICATION IN FL
Federated learning has been described by McMahan et al. (2016) in the form of the FedAvg algorithm. At each communication round I, the server sends the current model parameters w()) to subset (*(t) of all clients S. Each chosen client e updates the server-provided model w(()) e.g., via stochastic gradient descent, to better fit its local dataset D, = (d with a given loss function
1 N.
(D w)
U(dx.))
After E epochs of optimization on the local dataset, the client-side optimization procedure results in an updated model w!!) based on which the client computes its update to the global model
(t)
w (t);
(2)
and sends it to the server. The server then aggregates client-specific updates to get the new global model ((+1) w(1) + [stei] E. A |ster E. w! Outside the context of differential privacy, client updates are usually weighted by the size N, of the local dataset. A generalization of this server- side scheme (Reddi et al. 2020) interprets |stt]] EeEst (!) as a "gradient" for the server-side model and introduces more advanced updating schemes, such as Adam (Kingma & Ba 2014).
Federated training involves repeated communication of model updates from clients to the server and vice versa. These updates can reveal sensitive information about the client data, there is need for formal privacy guarantees. The total communication cost can be significant, thus constraining FL to the use of unmetered channels, such as WiFi. Hence, compressing the update messages in a privacy- preserving way plays an important role in moving FL to a truly mobile use-case. In the following sections, we first describe the lossy version of Relative Entropy Coding (REC) (Flamich et al.) 2020)) then show how to extend it to the FL scenario before discussing it in the context of differential privacy. Finally, we show how DP-REC can be used to additionally compress server-to-client messages.
2.1 REC FOR EFFICIENT COMMUNICATION
Lossy REC, and its predecessor minimal random code learning (MIRACLE) (Havasi al. 2018). 8). have been originally proposed as a way to compress a random sample w from a distribution qo (w) parameterized with Φ, i.e,, (w()), by using information that is "shared" between the sender and the receiver. This information is given in terms of a shared prior distribution (w) with parameters 0 along with a shared random seed R. The sender proceeds by generating K independent random samples, WI...., Wk, from the prior distribution pe (w) according to the random seed R. Subsequently, it forms a categorical distribution q (W1:k) over the K samples with the probability of each sample being proportional to the likelihood ratio it draws random sample Wx- from ( (W1.k) ), corresponding to the k 't sample drawn from the shared prior. The sender can then communicate to the receiver the index ks with log, K bits. On the receiver side, Wi- can be reconstructed by initializing the random number generator with R and sampling the first A" samples from pe pww).. These procedures are described in Algorithms aan 2
l (w- = ww)/po
-w). Finally,
Havasi et al. (0088) set K to the exponential the Kullback-Leibler (KL) divergence of qo (w) to the prior Pe( w) with an extra constant i.e., K (KL(KL(gs ( (w)]lpo(( (w]])))())) (w)) + c). In this case, the message length is at least OKL ( (w)lpe (w))). This can be theoretically motivated based on the work by Harsha et al. (2007); when the sender and the receiver share source of randomness, under some assumptions, this KL divergence is lower bound on the expected message length (Flamich al. 2020). This brings forth intuitive notion of compression that connects the compression rate
2

---

Under review as a conference paper at ICLR 2022
Algorithm I The sender-side algorithm for lossy REC with the shared random seed R. the shared prior Po (w(w) and the number of prior samples K.
Algorithm The receiver-side algorithm for lossy REC.
Receive k* from the sender Set state of pseudo-RNG R
Set state of pseudo-RNC RNG to R
Draw WI.... WK Ltd. (w(
Draw Wi..... W pe (w) Use Wg- for downstream task
iid.
OK < l0 W wx) (w Ww)
TT 0k Σj 0j
Wk- Jr (w:k))
return k- encoded with log, K bits
with the amount of additional information encoded in gø (w) relative to the information in pe (w): the smaller the amount of extra information the shorter the message length will be and, in the extreme case where g (w) Po (w), the message length will be ((1). Of course, achieving this efficiency is meaningless if the bias of this procedure is high; fortunately, Havvai et al. (2018) show that for appropriate values of and under mild assumptions, the bias, namely [
( [f]] for arbitrary functions f. can be sufficiently small. In all of our subsequent discussions, parametrize K as a function of a binary bit-width b, i.e., K 2h, and treat b as the hyperparameter.
2.2 REC FOR EFFICIENT COMMUNICATION IN FL
We can adapt this procedure to FL by appropriately choosing distributions client-to-server messages (model updates), g0.
(+) (t) along with the prior distribution Pe (A (t) on each round t:
Po (A == I"),
(1) == ((A
o²I),
(3)
i.e., for the prior we use Gaussian distribution centered zero with appropriately chosen and for the message distribution we opt for a Gaussian with the same standard deviation centered at the model update. The form of q is chosen provide plug-in solution to potentially resource constrained devices, as well as to readily satisfy the differential privacy constrains discussed in Section 2.3 Note
that, as opposed to the FedAvg client update definition in 2 here consider A (8) to be random variable and the difference w w(') to be the mean of the client-update distribution q over A
Let us now see how communication efficiency is realized in the FL pipeline. The length of the message will be a function of how much "extra" information about the local dataset D, is encoded in (") measured by KL divergence. As we show later, this has a nice interplay with DP: the DP constraints bound the amount information encoded in each update, resulting highly compressible messages. It is also worth noting that this procedure can be done parameter-wiss (i.e., communicate log, K bits per parameter), layer-wise (log, K bits for each layer in the network) or even network-wise (logg K bits in total). Any arbitrary intermediate vector size is also possible. This is done by splitting A (t) into M independent groups (which possible due to our assumption of factorial distributions over the dimensions of the vector) and applying compression independently to each group (see also Theorem 3). If we have many groups (e.g., when we perform per-parameter compression), we can boost the compression even further by entropy coding the indices with their empirical distribution.
2.3 PRIVATE & EFFICIENT COMMUNICATION FOR FL WITH DE-REC
In order to make the compression procedure described in Section 2.2 differentially private, we need to bound the sensitivity of the mechanism and quantify the noise inherent to it. Similarly to DP-FedAvg, bounding the sensitivity consists of clipping the norm of client updates (() (()) In
the context of REC, this means that the client message distribution 4x cannot be too different from
the server prior Pe in any given round After this step, instead of explicitly injecting additional noise to the updates, we make use of the fact that the procedure in itself stochastic. Two sources of randomness play role in each round t: (1) drawing K samples from the prior (t), (2) drawing an update from the importance sampling distribution o(") We coin the name Differentialll-Piie Privatee Relative Entropy Coding (DP-REC) for the resulting mechanism, outlined in Algorithms and 4
3

---

Under review as a conference paper at ICLR 2022
Algorithm The client-side algorithm for DP-REC at given round t. R! is the client-chosen shared random seed, w(O) is the server model, w!") is the fine-tuned model of client s, K is the number of prior samples, C' is the clipping threshold and the prior standard deviation.
Algorithm The server side algo- rithm for D2-REC.
Receive h", R!! from client e Set state of Essuud-RNNG to R( A..... Ag- iid. \(A ! 0 o²1)
R choose and set client-specific seed for round
Use A for downstream task
6 (t)
((t)
A A A....: Ag iid.
((A (0
0, I2)
@ Φ!" min(1,C//|))) //
ag 6 N(A, (6) A 2 IIN(NA -Ax0,
201)
-
0K// Σj aj
A k. Qn (A1:k)
(t)
return k- encoded with logg K bits, R2(()
Finally, to prove that DP-REC is differentially private and calculate the corresponding s, 6, we build upon prior work in privacy accounting for ML and FL; particularly, on Rényi differential privacy (RDP) (Mironov 2017) and the moments accountant (Abadi et al. 2016). Our analysis in the next section follows the established approach based on tail bounds of the privacy loss random variable, ((1) addressing such important differences as sources of randomness and non-Gaussianity of qx Additional discussion on other aspects of our method can be found in Appendices B.T and D.2
2.4 PRIVACY ANALYSIS OF REC
possible avenue to analyze privacy for DF-REC is derive DP bounds relying on Theorem 3.2 of Havasi et al. (2018). However, obtaining reasonable guarantees can be challenging, as the probability bound (Havasi et al. 2018 Theorem 3.2) has to be incorporated in ó and it least e -..12 Iu K As such, a fairly common value 8 10-5 would require ~e samples from the prior. To overcome this issue, we consider an importance sampling bound by [Aaaiiuu et al. (2017 Section 2.2). It scales (inversely) linearly with the number of samples, helping for smaller sample sizes.
Let us restate the bound for completeness. For some test function Ç, one can characterize the bound between the true expectation and the importance sampling estimate in the following way:
1r N (5) m(Sill 12 e Pa(nollps),
sup K <I
E
K
where K is the number of samples, 1 (.) - E F., u(-) = Eg and D2(-I1-) denotes the Rényi divergence of order 2 between the target 9s and the proposal pa- Our choice of ( (cf. Appendix A..I A. guarantees [<] < for any input and enables the use of this bound.
Theorem I summarizes our main theoretical result. It enables DE-REC to combine the server-side privacy accounting in the central model of DP with extreme model update compression, while allowing clients to privatize their updates locally and protect against honest-but-curious server. Theorem 1. After T rounds, with the client-to-served serverr bitrate b, DP-REC is differentially private with
5 min -
II
(A
(0
12
where the constant 6 D2
(10
(1) 1110
is the upper bound the Rényi divergence of order X
between the client model update distribution 2
(t) and the server prior Pg in any given round t.
(t)
Proof. See Appendix A.I
An attentive reader may notice a strong resemblance between Theorem I and the moments accoun- tant (Abadi al. 2016) and Rényi DP (Mironov 2017) results. Indeed, it turns out that the DP- DP-REC
4

---

Under review as a conference paper at ICLR 2022
compression procedure yields the privacy loss that can be bound by almost the double of the normal continuous Gaussian mechanism loss, plus a small overhead, and composed in a very similar manner.
Shared random seed Prior work relying shared random seeds has been shown to be vulnerable to attacks due to the possibility of "inverting" the noise (Kairouz et al.] 202T). DP-REC is not susceptible to this for two reasons. First, the randomness of the method comes from two sources instead of one, and knowing one seed does not permit to fully reconstruct the un-noised sample. In our guarantee, ô corresponds randomness, making it as secure as the standard Gaussian mechanism even when one of the seeds shared. However, this alone is not sufficient because the shared seed R could be manipulated to generate a set of samples on which to encode the update such that the guarantee would not hold (e.g., the tails of the privacy loss distribution). Hence, we add the second line of defense as we shift the task of picking R to client, who then transmits the seed along with the index ' for decoding. This way, neither the server nor any other entity can manipulate the seed to break the privacy guarantee.
the probability of the mechanism failure w.r.t. both sources of
Privacy amplification Like many recent approaches, including (Kairouz et al. 2021), DP-RECC- can be seen as a hybrid method. privatizing updates locally and providing an amplified central guarantee. A key difference, however, is that our method does not calibrate noise to the aggregate. Namely, the scale of noise and the guarantee do not depend on whether a thousand, a hundred, or just one client is sampled in round. This is due to non-additive nature of our mechanism, which does not let us casily benefit from the variance reduction as the Gaussian mechanism does. As a result, we always calibrate to an "aggregate" of one client. While this property increases the necessary noise, it has upside of allowing stronger privacy amplification. Substituting the typical sampling without replacement by sampling with replacement, we can use the amplification factor of 1/|5| while accounting for [ rounds, instead of |SS|/|S| while accounting for T rounds, and obtain a tighter overall guarantee.
Secure aggregation One of the considerations in FL is that the server might be honest-bur conest-but-curiee but-curious rather than fully trusted. In DP-F edvvg (McMahan et al. (0177), the noise addition is delegated to the server, and thus, secure aggregation (Bonawitz al. 2017 is necessary to prevent the server from receiving client updates in the clear. DDGauss (airruuz et al., 2021) and analogous methods mitigate this problem by shifting the noise addition to the client side, but still use secure aggregation for the reasons stated in the previous paragraph: noise is calibrated to the aggregate and may be insufficient to protect some clients, In REC, because of the noise calibration to individual updates, we believe that the provided local guarantee (which can be computed by removing subsampling amplification) is sufficient against non- malicious servers. To further boost privacy protection, an important future work direction is integrating the DP-REC compression scheme with secure aggregation.
Interplay of privacy and compression Theorem relates privacy to our compression scheme in an intuitive manner. In order to get meaningful privacy guarantees, we have to bound the Rényi divergence in any given round t for any > 2 1, which limits the amount of information encoded (t) As result, enforcing DP guarantees also implics that our scheme will have highly compressible messages. We formalize this interplay in the following lemma.
(t) relative to pg
in 2s
Lemma 2. Consider compressing the expected value of Ç under the qo. (A.) (3) and let & be desired average compression bias of REC Ç. To achieve this target, a sufficient bitrate b is at most
&
b < logg 12 + log2
D2 (20,11p0) logg G
where |C| S G and Di (go. llpo), and thus the maximum bitrate b, is controlled by the chosen (c, 5).
Proof. The proof follows from 4 by setting K = 24, rearranging the terms and adjusting for G.
We also verify the claim empirically (Figure 2) fixing the bound on the Rényi divergence and showing that the performance with extreme compression (i.e, 7 bits/ cits/tensor) and no compression is similar. Finally, to confirm that various granularity of compression (per-parameter, per-layer, per-network, etc.) does not interfere with our privacy analysis, we introduce and prove the following theorem.
Theorem 3 (Compression-by-poet bartts.).. Expectation of an arbitrary function ((Al)...., A [M)) over
the importance sampling distributions q= :.... ....)) built for M non-intersecting parameter groups
[1] [Md]
5

---

Under review as a conference paper at ICLR 2022
independently. is equivalent the expectation over the joint distribution on built on 2 samples:
E All [...B AlMingg "IAA",,.,,A.
E BAILMN
[((A ([]l
Proof. See Appendix A.2
2.5 COMPRESSING SERVER-TO-CLIEN TOLCLIENT MESSAGES
The compression procedure described in Section 2.2 specific example of (stochastic) vector quantization where the shared codebook is determined by a shared random seed. Here we show how the principle of communicating indices into such a shared codebook additionally allows for the compression of the cerver-to-llient communication. Instead of sending the full server-side model to a specific client, the server can choose to collect all updates to the global model in-between two subsequent rounds that the client participates in. Based on this history of codebook indices, the client can deterministically reconstruct the current state of the server model before beginning local optimization. Clearly, the expected length of the history is proportional to the total number of clients and the amount of client subsampling we perform during training. At the beginning of round, the server can therefore compare the bit-size of the history and choose send the full cill--eeeiioon model ((()) instead. Taking a model with 1k parameters as an example, a single uncompressed model update is approximately equal to 4k communicated indices when using 8-bit codebook compression of the whole model. Crucially, compressing server-to-cliee messages this way has no influence on the DP nature of DP-REC since the local model of DP ensures privacy of client information (and the stronger central guarantee applies as long as the secrecy of the sample preserved within the updates history).
For clients participating in their first round of training, the first seed without accompanying indices can be understood as seeding the random initialization of the server-side model. Algorithms 5 and (in Appendix (..2) describe this scheme. It is important to note that the client-side update rule must be equal to the server-side update rule, i.e. in generalized FedAvg (Reddi et al. 2020) it might be necessary to additionally send the optimizer state when sending the current global model wt(").
RELATED WORK
The privacy promise of federated learning relies heavily on the use of additional techniques. such as differential privacy and secure multi-party computation, to provide rigorous theoretical guarantees. Without these techniques, FI. has been shown be vulnerable to attacks (Geiping et al. (020)) and unintended leakage of sensitive information (Thakkar et al.) 2020). One of the main open challenges is to reduce the communication cost while preserving DP guarantees (Kairouz et al. 2019).
McMahan et al. (017)) outlined DP-FedAvg, which has since been the staple of DP federated learning. this default scheme, clients clip norms of their updates before submitting them to the server (preferably, using secure aggregation protocol (Bonawitz al. (017)). The server then completes the DP mechanism by adding Gaussian noise to the aggregate of multiple clients. Without secure aggregation, this method allows clients compress their updates and reduce communication, but becomes vulnerable to a malicious or honest-but-curione server. One could use the local model of DP (Dwork al. 2014) instead of the central model to address this issue: clients would add noise locally before sending the updates. But this leads to a pronounced drop in accuracy due to the larger scale of noise necessary in the local model (Kairouz al. 2019). The few existing examples that use the local model operate on very large numbers of clients and updates (Pihur et al. 2018).
To overcome this problem of excessive noise, researchers are increasingly looking in the direction of hybrid solutions (Shi et al., 2011; Rastogi & Nath 2010 Agarwal et al.) 2018: TTuex et al. 2019). The key idea of these techniques is to reduce the variance of the locally added noise by taking into account the larger global number of clients and accounting DP in the central model. Since the smaller noise variance insufficient to protect individual updates, secure aggregation is necessary for these methods. In this context, the local noise distributions have to be discrete, such that their sum after secure aggregation is also discrete and is of known shape, allowing the server to compute guarantees centrally. As a result, until recently, most of these methods relied on the binomial distribution. Compared to the traditional Gaussian mechanisms, is at a disadvantage because it does not yield Renyi concentrated DP, and thus cannot benefit from tighter adaptive composition and

---

Under review as a conference paper at ICLR 2022
amplification through sampling, which is particularly important in ML applications (Kairouz et al. 2021). Kairouz et al. (2021) presented a novel analysis of the discrete Gaussian mechanism (Canonne) et al. 2020) in terms of concentrated DP. Their mechanism, named Discrete Distributed Gaussian (DDGauss), is adapted to the context of FL., can provide accuracy comparable to the centralized Gaussian mechanism, and enables parameter-wise quantization. However, higher compression rates (e.g., 12 bits per parameter), DDGauss fails to train a model for reasonable s values.
Finally, there is recent work featuring extreme compression rates for DP algorithms, bearing resemblance to our solution. Girgis et al. (2020) proposed to use a locally private mechanism along with a secure shuffler to communicate models one (privatized) parameter at a time. compresses client messages to log d bits for a model of d parameters. This approach, however, seems to require a large number of clients to participate in a single round (10k for their MNIST experiment), which is impractical in realistic scenarios and detrimental to the total communication cost (upload + download). Chen et al. (020) achieve similarly high compression rates as (Girgis et al. 2020μ; however, they do not consider the context of federated learning but rather focus on frequency and mean estimation. As we did not have an FL baseline for (Chen et al, 2020) and could not reliably reproduce the results of comparison with these methods on mean estimation. Details can be found in Appendix [D2] In short, we find that the method Chen et al. (2020) has an edge over DP-REC if good prior is lacking, making it preferable for low-information, "one-shot" scenarios, such as mean estimation. On the other hand, with a good prior (or one that is learned during training),
Girgis et al. (2020), we focused
DP-REC performs better and thus is more appropriate in federated settings.
4 EXPERIMENTS
We evaluate DP-REC on several non-i.idd. FL. tasks that provide client-level privacy guarantees: image classification on a non-i.i.d. split of MNIST (LeCun et al. 1998) into 100 clients and FEM- NIST (Caldas et al. 2018) into 3.5k clients, along with next character prediction on the Shakespeare dataset (Caldas et al. 2018)) with LSTMs (Hochreiter & Schmidhuber 1997) and 660 clients as well as tag prediction on the StackOverflow (SO-LR) dataset (TFF Authors, (019) with a logistic regres- sion model (Kairouz al. 2021) and 342477 clients. For baselines, we consider DP DP-FedAvg the gold standard without compression and DDGauss as a baseline that involves parameter quantization. Both of these methods target central DP guarantees and employ secure aggregation. All exeriments were implemented in Py'Torch (Paszke et al. 2019). We provide experimental details in Appendix C
4.1 RESULTS AND DISCUSSION
We plot the global model accuracy for different privacy budgets E as function of the total communi- cation cost in Figure T this highlights how efficiently each method spends bits of communication in order to reach a target accuracy. Due to the substantial compression by DP-REC relative to the baselines, Appendix shows the accuracy achieved as a function of the privacy budget e; this highlights how efficiently each method spends its privacy budget in order to reach specific target accuracy. Note that in certain cases the training is stopped before convergence, due to exhausted privacy budget.
log-scale for the x-axis of communication costs. Additionally, Figure in
In Table D we report the final model performance and total communication costs for different privacy budgets. It should be mentioned that the evaluation loop for StackOverflow is prohibitively expensive to be done in each round due having ~ ~1.6M datapoints. We thus pick 10k random datapoints for evaluation during training to plot the learning curves (not necessarily the same for each run), following (Reddi et al. 2020 The numbers in Table refer to the model performance at the end of training, where we evaluate on the entire test set for DP DP-FedAvg and DP-REC. For DDGauss, since Kairouz et al. (202T) do not report the model performance on the full test set, we use the numbers shown at the end of their plot. Finally, results for some settings either (i) convergence issues for stricter privacy budgets (a typical phenomenon for e < on smaller federations); (ii) not being reported by the related work we compare with; or (iii) not being necessary in light of sufficient performance under better privacy guarantees (e.g., on StackOverflow).
omitted because of
Observing the experimental results, we clearly see the trade-offs. DP-REC can drastically reduce the total communication costs (download and upload) of federated training depending on the subsampling rate and amount of clients in federation. For certain cases, can get extreme reduction, such
7

---

Under review as a conference paper at ICLR 2022
Table 1: Performance (+ standard error obtained via multiple runs) and total communication (in GB), achieved for different privacy guarantees e. Results for DDGauss (marked DDGr for z bits) are taken from (Kairouz et al. 2021), which uses slightly smaller version of the FEMNIST dataset (3.4k clients instead of 3.5k).
MNIST
DP DP-FedAvg DP-REC
FEMNIST
DP-FedAvg DDG16
DDG12
DP-REC
Acc. (==3)
82.1 + 0.8
66.5 + 1.5
Acc. (s=11 1)
65.7 + 0.3
59.3 + 0.1
Acc. (6=
90.0 + 0.4
79.0 1.9
Acc. (s=3)
0.1
-72
-5
67.0 + 0.1
Comm.
43
0.01
Acc. (s=6)
0.2
~77
~71
69.1 + 0.1
Comm.
259
194
178
14.2
Shakespeare DP-FedAvg
DP-REC
SO LR
DP-Fedåvg DDG16
DDG12
DP-REC
Acc. (==3)
39.0 1 0.1
29.0 1 0.1
R@5 (x=1)
19.3 1 0.0
-14
-10
18.4 1 0.7
Comm.
81
0.1
Comm
3356
2517
2307
32
3.3,2
5.7
3.8
5,4
Comp.
80
1533.4x Comp.
70
60
Accurscy
60
Accuracy
UP- DIFFedAvg
40
40
De-Fed E<
30
Dr-FedAvg, <<6 DIYREC, c
DP FedAug. <
UPAREC,
20
DP-REC, <<6
DA-REC,
10"
10"
16
10
10"1
10"
communicated
communicated
(a) MNIST
(b) FEMNIST
40
105.1x 1x Comp
35
20
263.8x Comp.
Rocal Rocal-85x1 150
15
Accursc)
20
10
15
10
5
5
redAvg. <
DP. <<]
OP-REC, <
DP REC, 1<1
10"
10"
10" -2
10"
10'
10"
10"
10
10
10
10*
CB communicated
communicated
(c) Shakespeare
(d) SteckOvrrflow
Figure Test accuracy (%) with +1 standard error as function of communication (in GB, in log-scule). For SteckOverflow, we report compression at the end of training, the learning curves are based on different subsets of the validation set.
as MNIST with 4300x compression. But even for other cases, the reduction is still several orders of magnitude (105x for SO-LR and 18x on FEMNIST). Nevertheless, DP-FedAvg and DDGauss (depending on the task) can reach better model performance for given privacy budget. This is primarily due to two reasons. Firstly, both DP DP-FedAvg and DDGauss add noise calibrated the number of clients in given round to get a central DP guarantee on the aggregate; in contrast, DP-REC calibrates noise to the contribution of individual updates (see Section 2.4 The signal-to-noise-ras for the model updates is thus worse for DP-REC. Secondly, in DP-REC we have to clip client updates more aggressively to account for the privacy loss overhead incurred from the REC compression (roughly double for each iteration compared to Gaussian mechanism). This can be mitigated in larger federations, since the clipping can be reduced based on stronger privacy amplification for the central model of DP. For example, observe the StackOverflow experiment, where the accuracy delta between DP-REC and DP-Fee -FddAg is smaller. Furthermore, it is precisely in those cases that reducing the communication cost is important from practical perspective. When we target specific accuracy
8

---

Under review as a conference paper at ICLR 2022
within the reach of both DP-REC and DP DP-FedAve, compress between 8.3x (FEMNIST) to 1533x (MNIST), at the additional cost of 1.9 to 2.2 in E, relative to DP-FedAvg.
Comparison with local DP guarantees The nature of the DP-REC privacy mechanism requires calibrating noise to individual client updates rather than their contribution to the aggregate. This property warrants different kind of comparison: equalizing local guarantees for each individual update (i.e., as seen when the secrecy of the sample in client sampling is not preserved). We use our non-i.i.d. FEMNIST setting with 1.5k rounds and tune the noise of DP-FedAvg such that a single client update, without any privacy amplification. has the same Elocal guarantee. When training -eFFedvv with a local-DP guarantee that DP-REC obtains when targeting central-DP with ş = 3. we see that DP-F DP-FedAvg obtains 68.9% accuracy, whereas DP-REC gets 63.4%. On a setting where we target the local-DP guarantee that DP-REC gets when aiming for central-DP with I, DP-FedAve achieves 60.1% accuracy compared to OP-REC's 57.4%. In both cases, OP-REC achieves an overall compression rate of 72.5x with 7-bits per tensor, while losing 2.7% to 5.5% in accuracy compared to DF-FedAve (depending on the privacy target) due to more aggressive clipping. It is also worth noting that the performance delta relative to the results shown in Table Iis smaller, highlighting the negative effects of calibrating the noise to "aggregate" of a single chiett.
Compressibility of differentially private updates As we noted in Section 2.4 differential privacy has a positive inter- play with the REC compression scheme. DP upper-bounds the Rényi divergence for any order À between the proposal distribution ( and the model update distribution lø and, 2 this limits the maximum bitrate b of in-
65
60
Accuvary
(t)
65
bts per tensor bits por-tansor
according to lemma formation to be communicated. In order to empirically verify this claim, we consider the non-i.i.d. FEMNIST classification with ROP, and hyperparameters that target a model with E = 3 after 1.5k rounds. We then maintain the same bound on Rényi divergence and vary the number of bits per tensor from 4 to 7. We also include variant without compression, which directly communicates a random sample from the clipped up- date distribution L/ (f) The results appear to verify our claim and can be seen in Figure - After 4 bits, we see very small improvements with adding additional bits and, with bits, the performance is very similar to the uncompressed baseline.
bis per-enso No compression
200
400
800
800
1000
1200
1400
Figure 2: Effeec of the bit-width on model performance with DP-RES for clipping targeting ε after 1.5k rounds. The "no-compression" variant communicates a random sam- ple directly from 9 instead of com- pressing it via DP-REC.
5 CONCLUSION
With DE-REC, we formalized the intuitive notion that s, differentially private messages necessarily contain small amount of information and can therefore be compressed significantly. A bound on the Rényi divergence between the server-side prior p and the locally optimized q implics a small message size for REC, elegantly tying together DP and communication efficiency for federated learning. The nature of our bound in Theorem T reveals the flipside of DP-REC. As opposed to the standard Gaussian mechanism in central DP. requires stronger clipping, effectively redueing the utility of models trained with DP-REC for a given privacy budget. Our experiments with the StackOverflow dataset show that these limitations can be mitigated by the stronger privacy amplification in situations with large numbers of clients. Contrary to intuition, spending more bits to communicate updates from clients to the server cannot recover this utility as the necessary information is lost in clipping, i.e.. before forming the importance sampling distribution q.
There are several important directions left for future work. The first would be to investigate the convergence of DP-REC. Intuitively, we can expect the algorithm to be convergent if DP-FedAvg convergent. The main difference of DP-REC is that the gradient is sampled using importance weights rather than the true Gaussian probabilities. Asymptotically, these two distributions should be close, and the bias of the compressed gradients would be bounded by a small value (as discussed in Section Empirically, secure shuffling, similarly to Girgis et al. (2020) as a way to amplify our privacy further; this can lead to less aggressive clipping and thus improved performance for a given privacy budget.
observe no issues with convergence. The second would be to investigate

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
This paper addresses significant, present-day problem and provides clear, detailed explanation of our solution facilitate reproducibility and promote research integrity. We expect our work to have an overall beneficial societal impact through its main contributions of communication reduction and differential privacy. One potential concern worth mentioning is the interplay between differential privacy and fairness in FL. actively researched open problem. [Baddasaryan al. (2019) demonstrate that DP training can have a disproportionate effect on underrepresented and more complex sub cot-pouulations, resulting in disparate accuracy reduction. At the same time, Hooker et al. 2020) showed that compression of models can have negative impacts by amplifying biases. In the context of FL., compression is performed model updates instead of final model, therefore requiring further research on its influence on bias amplification.
REPRODUCIBILITY STATEMENT
For the theoretical results, clearly state assumptions and present complete proofs in the appendix. For experimental evaluation, although we cannot provide the source code at the time the submission because it is proprietary, include extensive information algorithms and settings in the appendix, and repeat our experiments with multiple random seeds to aid reproducibility.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMAhan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
Sergios Agapiou, Omiros Papaspiliopoulos, Daniel Sanz-Alonso, and AM Stuart. Importance sampling: Intrinsic dimension and computational cost. Statistical Science, pp. 405-431, 2017.
Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and H Brendan Mema- han. cpsgd: Communication-effia and differentially-privee distributed sgd. arXiv preprint arXiv:1805. 10559, 2018. 2018.
Galen Andrew, Om Thakkar, H Brendan McMahan, and Swaroop Ramaswamy, Differentially private learning with adaptive clipping, arXiv preprint arXiv: wrXiv:1905.03871 2019.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact model accuracy. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran As- sociates, Inc., 2019. URL EcCde4400396 wtw.:/eee.e2222222222222223
nwwrips wallsscccceee http:/pppr/2111//555 Paper .ddf
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint 11X1v:1812.01097, 2018
Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. arXiv preprint wrXiv:2004.000111 2020.
Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur. Breaking the communicaiion-piiacyycccommm trilemma. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 3312-3324 Curran Asso- ciates, Inc., 2020. URL 222 aet
neurips ec wttp:/p///cppppp/////////////// file//
10

---

Under review as a conference paper at ICLR 2022
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference on Neural Networks (IJCNN), pP- 2921-2926. IEEE, 2017.
Cynthia Dwork. Differential privacy and the us census. In Proceedings of the 38th ACM SIGMOD- SIGACT-SIGAL Symposium Principles of Database Systems, pp. 2019.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, (0-4):211-407,, 2014.
Gergely Flamich, Marton Havasi, and José Miguel Hernández-Lobute Compressing images by encoding their latent representations with relative entropy coding. Advances in Neural Information Processing Systems, 33, 2020.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients how easy is to break privacy in federated learning? In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 16937-16947. Curran Associates, Inc., 2020. URL / neurpp
Antonious M Girgis. Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of federated learning: Privacy, communication and accuracy trade-offs. arXiv preprint arXiv:2008.0711 2020.
Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. The communica- tion complexity of correlation. In Twenty-Second Annual IEEE Conference on Computational Complexity (C)C'07), pp. 10-23. IEEE, 2007.
Marton Havasi, Robert Peharz, and José Miguel Herúáneez-Lobtto. Minimal random code learning: Getting bits back from compressed model parameters. arXiv preprint 1XXv:18100004400 2018.
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B. Brown, Prafulla Dhariwal, Scott Gray, Chris Hallacy, Benjamin Mann, Alec Rad- ford, Aditya Ramesh, Nick Ryder, Daniel M. Ziegler, John Schulman, Dario Amodei, and Sam McCandlish. Scaling laws for autoregressive generative modeling, 2020.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Sara Hooker, Nyalleng Moorosi, Gregory Clark, Samy Bengio, and Emily Denton. Characterising bias in compressed models. arXiv preprint arXiv:2010.03058, 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint wrXiv:1909.000. 06335, 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977 2019.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. arXiv preprint arXiv:2102.06387, 2021.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.084 000361, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 142.:91412.6980, 2014.
Estelle Laziuk. ios 14.5 in rate, 2021. /ttp://///ttss///....i.....
w

---

Under review as a conference paper at ICLR 2022
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2) 23244, 1998.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication--fficicenn learning of deep networks from decentralized data. arXiv preprint arXiv:1602.0562, 2016.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:/710.066
2017.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEEE, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv:/908 10530, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. H. Wallach, H. Larochelle, Beygelzimer, F. d' d'Alché- Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024 8035.003...2 Curran Associates, Inc., 2019. URL OBL/Ateee//aapee..a.erpssscaappp
9015 pytorhhhcppthhhhhhohoooooo ao--ipeerttive-styy oet.pppptttteeeeeeeeeereccoooooe
Vasyl Pihur, Aleksandra Korolova, Frederick Liu, Subhash Sankuratripati, Moti Yung, Dachuan Huang, and Ruogu Zeng. Differentially-privttt" draw and discard" machine learning. arXiv preprint arXiv:1807.04388 2018.
Vibhor Rastogi and Suman Nath. Differentially private aggregation of distributed time-series with transformation and encryption. In Proceedings of the 2010 ACM SIGMOD International Confer- ence on Management of data, pp. 735-746, 2010.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.0029) 2020.
Elaine Shi. TH Hubert Chan, Eleanor Rieffel, Richard Chow, and Dawn Song. aggregation of time-series data. Proc. NDSS, volume pp. 1-17. Citeseer, 2011.
TFF Authors. http://wwww....ooeee/e////////// datasetss/ttaccooverloo 2019.
Tensorflow federated stack overflow dataset. Online: https
Om Thakkar, Swaroop Ramaswamy, Rajiv Mathews, and Françoise Beaufays. Understanding
unintended memorization in federated learning. arXiv preprint arXiv:2006.074: 2020.
Stacey Truex, Nathalic Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pp. 1-11, 2019.
Yi Zhou. A hybrid approach to privacy-presee
Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10:3152676,2017 2017.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint wwXiv:2107006111 2021.
Yao Xiao and Josh Karlin, Federated learning of cohorts. URL htw.https://// /wtp:::://www..oo wwwh.ggihgg........ 1o/ floc/]
12

---

Under review as a conference paper at ICLR 2022
APPENDIX
A PROOFS
A. PROOF OF THEOREM 1
Theorem 1. After T rounds, with the client-to-server bitrate b, DP-REC differentially private with
8 S min
As A 1-1
12
26
1=1
where the constant o
Dx (11 is the upper bound the Rényí divergence of order
(t) between the client model update distribution Lob and the server prior Pg in any given round t.
(t)
Proof. Consider privacy mechanism RRd mapping dataset E TD to a d-dimensional model update A E Rd Recall that mechanism features two sources of randomness: drawing from distributions pa and then र (which is based on Gø and po).
Similarly to the derivations for the moments accountant (Abadi et al. 2016), can write
Pr(A(D) e Ω] = Pr(A(D) O Pr(A(()) S] I e Pr(A(D)) e Ω Pr(A(D) E S].
(5)
(6)
where C Rd is an arbitrary set of outcomes, S 1A T.g, (A D, D') > o} is the set of outcomes where the bound on privacy loss is violated, and S denotes complement. For multiple iterations, k' can be viewed the multi-index picked from the importance sampling distribution across all iterations.
First, let make brief side-note the privacy loss. As pursue the goal of client-level privacy, we consider two clients with different local datasets and D'_ Their update distributions are parameterized by & for one client and ø' for another: g (1:T") (-) and Lo (1:T) We will denote the (().T)())
corresponding importance sampling distributions j/t (1:TT) these two clients is
(.) and 9x" (-). Then the privacy loss for
(1:2")
(1:7))
L (1
(1:T) D.D')
log
(1:T)
(1:7)
(177
(1-T)
On
log
+ log
px (:T)
(.)
Px
(::T)
(1:)) (.)
(1:7) (-)
log
+ log
(9)
Pr
(1:7) ((:))()) (.)
Px
-1:7)
(.)
L (-) +
(1.T)
(+),
(10)
where _(1:2) -p is the uniform distribution over K samples from pa (1:2' Thus. it is sufficient to bound the privacy loss L Lgn.r (.) for the worst-case with some E, For the centralized guarantee. would correspond to bounding the influence of adding or removing one client. guarantee, bounding the influence of substituting a client, is necessary, it will be given by 2s (and correspondingly. 26). This is consistent with prior work where bounds on substitution are also double the bounds addition/removal.
the local
13

---

Under review as a conference paper at ICLR 2022
Consider the second term of Eq.
6 for T rounds of training:
Pr
L L
>
(II)
= S
Po
(1:T)
( A
l:K
(1)
A
(T)
1:
Σ
A
k
K
Σ
a(T)
kr
(T)
(1T--1)
(1:T
1:K
")
(Low
d4
(1:T)
(12)
kp=1
where
@r A
(1:T) 1:K
I. (1:T)
log
(13)
(1:2')
Px
1:K
is the total privacy loss across all samples from all iterations. Note also that by (-) we denote an importance sampling distribution formed when the proposal and the target are the same, which is essentially uniform over the K samples.
Since (.) S 1, we can employ the bound (4) directly. However, due to the iterative importance sampling over rounds and possible dependencies between rounds, we have to the law of total
expectation and apply the bound recursively. Namely, denoting < ((T)) (1:7), = [Laa De}
Pr([.gn:) > (n:2))
1
Po
(1)
(1)
(1)
(14)
K
f Pg
(T)
A
(T)
(1:T
(T)
A KT
(1:T-1) 1) ((T) (A
(A
(1:2)
da
(1:T)
1:K
IK
I:K
I:K
K
Pg
(1)
(A
(1)
1:K
ki
(1)
(15)
Po
(T)
A
1:K
(T)
1:K
(1T-11)
L
(
A (T)
A
- ((2) A (1:T)
dA (T)
12
K
PT
da
1:K
(1:T)
Po
(1)
1:K
(1)
(1)
(1)
(16)
k1=1
Pg
(T')
1:K
(1:T-1)
1:K
(T)
A (T)
(1:-11)
I:K
(T)
(1:7)
1:K
dA (T) dA (T)
1:K
dA
dA
(1:T-1)
1:K
((--1)
(1: 11
LK
12
+
K PT,
(17)
where we can pull out due its independence from the rest of the expectation.
16 one can then treat the inner expectations (over the distributions from round 7) As noted in line
as new function TT (A (A( (1:T-1)), which still bounded by because it's an expectation of an indicator function. Repeating the procedure, we get
Pr[L (1T))
12 Pt.
< E
Pe
(LIT)
E (1/7)
48
log
Am
dm (A(17T)
(1.T)
2b
1=1
(18)
p(1:T)
14

---

Under review as a conference paper at ICLR 2022
with Pr p== D2 11p))) It is worth noting one more time that go and Pa are conditional distribu-
tions, depending rounds 1...t 1, and that do not assume independence between rounds.
Applying Chernoff incquality to (18)
Pr[L ( > E]
dn (~ (I
(A
S E (1:2)
E (1:27
log
(r (A
+
2h p (1:7)
12
(19)
Pg
0g
(1:2))
Ar
B (1:7)
E (1:7)
1:K
26 p (1:))
12
(20)
Pe
(1:7)
Px
1:K
As we have done above in
14). we re-arrange expectations using the law of total expectation:
(1:7)
A7
12
E
A
Pg
a E (1)
Pe
(1:2")
+
2
p (.:T.
(21)
Per
l:K
Analogously, let us apply the chain rule the inner expression:
A
(1:T)
(1)
(7)
(1:T -
k-
(22)
A (1:1))
(1)
(1:2
pT
P
f'
k-
K+
k+
(2)
(TT
Continuing on 18)
12
E (1)
E (1)
E (3)
(7)
(
(1:T)
(23)
4
9
25
12
X (1)
E (1)
8 (0)
E
(T)
E (T)
+ 2 p (1:T)
(24)
Ph
4m
I. (T)
If we bound the quantity (T)) 2 by some constant RA, independent of all the previous samples A (1:T-1) we can bring it in front of the rest of the expectation. Note that this quantity is not exactly the privacy loss of the mechanism in round T, and the slight abuse of notation for simplicity purposes.
By again performing this operation recursively,
Se de N
12 25
(LT)
(25)
Let us therefore consider any of such terms in isolation. To proceed, observe that can switch from importance sampling to the original continuous distributions inside the expectation in the following way:
(4
(2) 1
po
(1) 1.a
Σx po 1
(0) 4
/ A (2)
(
Po(A
3/Po ( A (C)
Ee aos
/PO A (1)
q A (t) pe
k
pe
Σn k 9s
(1)
(AP (1)
4s
A (0)
(A AA k'
(0)
E
(26)
Pe(A
Th
9 A (0)
15

---

Under review as a conference paper at ICLR 2022
Hence, keeping in mind that expectations and distributions conditioned on the previous - 1 rounds,
(((1)
Pa
(1)
EE
E
log
re
a1))
B
14
(7)
(27)
Pb
9a (1))))
vo (2
A log
2 log B
E
Po aie)
IE
1i (1 (3)
(28)
4
P
A (t)
lsb (A (2)
Po
=
E 4
E
(29)
po
A (r)
A (t)
The first expectation is equivalent to the one in DP-SGD and is basically moment nooment-generating function of the privacy loss random variable between two sequences of Gaussian distributions (or mixtures when subsampling is used) over T rounds.
Let us consider the second expectation, which requires further manipulation to avoid using the privacy sensitive importance weights. We cannot employ the bound by Agapiou al. (017) because the
16

---

Under review as a conference paper at ICLR 2022
function inside not bounded. However, utilize the special form of this function:
(e)
A
P6
EE P0
E 4m
(30)
(4)
4
A7
E, Col (A, (4))
\/pol (1)) (t))
K
P8
E
E
(31)
(t)
163
K
E, 1 (A)
(1)
pol A (8))
9s
(e)
(4 ) Pa A )
A
E, Gol (A, 3/DO A (2)
pe
E
Po
EE x())
(32)
(t) (8)
K
Σ1 40
(2)
1/po
94
E, Gol ( (1)
Po
K
(1))
(33)
1: m
(t) (6)
K
9s
A+17
Σ 2090(A (A
)/po
(2)
(1) K'
E 21
(34)
(t) (6)
K
1K 1K P
Σr 2ol (
(1)
1/PO( 1,00)
(2)
/PO A (t)
pa (1 (3)
A+17
E
(35)
(t) (
PPo
K
1/1o (0)
(A K
(2)
A+17
1
E
(36)
(1)
K
Pe
A (9)
( (0)
(
Po A (0)
X+17
E
(37)
K
AA
2 A (0)
k
l:K
~P
A+17
A
E
(38)
K
(6(A(1)
(POA(()) (1))
X+17
E A0)g
(39)
As(A()) (9))
= ADA+ (palla))
(40)
Putting everything together, we have
(8) < (a I Ax. 1
(41)
where yλ does not depend any of the previous rounds, since we can bound Rényi divergences (c.g., by clipping the model updates), and is defined as
Hx = max
loo).
(42)
0.0
It then satisfies the conditions to obtain Eq. 25 and consequently, proves the theorem with
maxo.0
D2(1
(0) (t)
= max
(6) (t)
(43)
maxo.0 Dx(20 11
17

---

Under review as a conference paper at ICLR 2022
A.2 COMPRESSION BY PARTS
Let us consider the setting where parts of the model (such as tensors, or even individual parameters) compressed independently. Assume all model parameters A split into M non-intersecting groups A (1) A [M) and are encoded using b1 bI..... .b bits correspondingly. We use square brackets to distinguish these indices from the round indices. The following holds.
Theorem 3. Expectation of an arbitrary function C( A (M]) over the importance sampling distributioos qı ..... q built according to the outlined procedure for each parameter group independently, is equivalent to the expectation over the joint importance sampling distribution 4n built on 2 2 samples, i.e.
E A1l
11 .... E ....BAMMWg
M ag
<(A 11
A 1M)
]..]
BAIMMI ((AAL))))
Proof.
To show that the above true it is sufficient to write down these expectations:
E A Aiiingh (((A))
E Alling
(44)
2
k,
\/PO !1
242
2
IΦ
RM
[M
)/Po
[M/]]
<(A
[1]
[M]
En, Is
po
Eler 9 (A
)/po
(x/))
[M]
ky
RM
1
11
12=1
Ax==1
las
(45)
2 Σ
26 ) 1 A (
Lo A
[Mr1]
kM
[Md]]
C(
[1]
[M]
Ei, LΦb
ppl(
Eie 2o (A Jar )/Pp)
kM
1==12=1
kx==1
1x
(46)
(A [3]
G. A [M
Σ
2 2
2rM
(A) k1
)...Po
KM
M
((4
[1]
[M
(47)
kq
kM
k==1
=x==1 Σn
Els
2o )a...0
pa )... Pa
A
20(A k.
(1:M1)
2b1 1.l...11p.) 16M
Pe [1:37]]
<(A R.
[:M]]
(48)
241 I... bar
go( A B:M]
11=11
Pof
-EAD:: (1:
(49)
where ki (ki,k2,- ........ kM) and 1, =
are multi-indexes. The line 48) is because
[M] [1] [M]
distributions 9
..... Lop and Pg P. for diffeerent parts of the model are parameterized by the model updates learnt parameters, and hence, independent given these updates parameters. O
B ADDITIONAL DISCUSSION AND ALGORITHMS
B. ADDITIONAL DISCUSSION
Computational overhead DP-REC does introduce additional computational requirements compared to standard FedAvg and compared DF-FedAvg. Every line in Algorithm 3 involves some additional computation due to the REC compression. More specifically, REC involves locally sampling K i.i.d. normal samples of dimensionality of the update. After clipping updates, REC computes the importance samples ag,, essentially calculating oog-probabilities of the samples under two Gaussian distributions. Finally, sampling from the categorical distribution दn. which relatively cheap since we perform per-tensor compression. It is difficult to benchmark the real-workd impact of this additional computational overhead given heterogeneous hardware. A practical implementation would sample the Handard-normal samples during training (or even during idle-times as well as the Gumbel-sampler for the categorical distribution. The log- probabiilitiss of the prior can equally be pre-computed. The index-selection procedure can be parallelized if the hardware supports it. In simulated
18

---

Under review as a conference paper at ICLR 2022
environment RTX2080 GPU, which runs everything sequentially (training, then per-tensor Gaussian sampling, per-tensor a computation and index- selextsel for the Cifar10 experiment with K = 2", single-client's epoch has roughly 70%:30% ratio of caaning-tt-copprsssinnn with some variance due to the different local data-set sizes.
Increasing accuracy the cost of communication There is noticeable accuracy gap between DP-REC and De-ved A reasonable question to ask is whether possible to trade higher communication spending for better accuracy? Unfortunately, it is not simple. The reason for observing the gap lies not in compression but rather in privacy accounting. Figure 2 shows empirically that increasing bit-width has marginal returns, up until doing no compression all. Any configuration in terms of higher bit-widths or more fine-gre the-grained vector quantization can be expected to perform between 7-bit per-tensor quantization and no-compression. Compression-only experiments in Ap- pendix als corroborate this point, the non-private compressed model achieves performance much closer to FedAvg. Expressing the divergence bound of discrete distributions through continu- ous distributions leads to nearly double the amount of noise necessary for an equivalent guarantee compared to the normal continuous Gaussian mechanism. Thus, we would need to relax privacy to close the accuracy gap. This bound with overhead appears to be tight too, judging by some of our synthetic experiments measuring how close it comes to the divergence computed from actual discrete distributions. However, there is still a possible way reduce the accuracy difference by employing stronger privacy amplification (e.g. adding secure shuffler), which will counter the overhead of the bound. This effect seen in StackOverflow dataset, where subsampling amplification is stronger due to large number of users and the accuracy gap between DP-F DP-FedAvg and DP-RED P-RCCC is drastically smaller.
19

---

Under review as a conference paper at ICLR 2022
B.2
ADDITIONAL ALGORIHHMS
B.2.1
SERVER-TO-CLIENT MESSAGE COMPRESSION
Algorithm
5
and
Algorithm
formalize
the
process described
in
Section
2.5
Algorithm 5 The server side algorithm for the com-
Algorithm 6 The client side algorithm for the decompression of server-to-client com- munication. dec. describes Alg. 4
pression of server-to-client communication. R! is the client-chosen shared random seed for round t. dec. describes Alg. O describes the sever-side opti- mizer including its state (e.g. momenta)
msg. = (w(*), O) then
((t) t w(()
H, = {(R', O())) {(I')(())) Vs E initial seed R'
History with model
0 O(1)
else
for t E { T do
msgs
Sample set 5' of participating clients Round memory
w(t) t ws (pree) > Last-known server model
M + 0
for 8 S' in parallel do
for M E H do
msg. + create e-reate_messt message_for client(s, frrssage_fo__cleen((sst_ H.) Send msg, client
if M (R', 00) then
w initialize (R') O, O())
Receive kn, R! > client-chosen index, seed M M ((kt, ) end for
else
A
M Me dec.
for 8 do
w (t)
w(() (A(A)
H. s- Ipplore_isstoryys, S' M))
end
end for
end for
A
Σx- EM dec. (R(t)
end
((++)
(()) 000) (1)
return w((
end for
procedure CREATE MESSAGE FOR CLIENT(s, H.,) if size H&) > size (w(()) + size(((t)) then msgs f (w 0())
else
msg= + H end if
He < 0
> Reset client history
return msgs end procedure
procedure UPDATE HISTORY(s,S'.. H",, if S' then
H. + H. U (T! else
H. <- H. U (M))
end if
return H, end procedure
B.2.2 ALGORRITM FOR ACCOUNTING PRIVACY IN DP-REC
Algorithm describes how we compute for target in DP-REC in general. More specifically, in our experiments, p (00 I² and d N(d,,, I2). For such distributions, the Rényi divergence between them evaluates to
Dx
(1) (1) 16
|
(50)
2
20

---

AC Under review as a conference paper at ICLR 2022
Thus, for given À and o, bounding this divergence corresponds to clipping the norm of Φg. i.e., clipping || to C' corresponds to Dx U (e)
T Vob 0. In order to allow for privacy I
amplification with subsampling, we also need to bound the Rényi divergence between the prior Pe and the mixture y + NN Po where N corresponds to the number participants in the federation and B/ B/N to the subsampling rate (Abadi et al. 2016 Mironov et al. 2019). the general case, we have to consider the maximum over the two possible directions:
Dx
N
--2 B
Pe
(2)
B
96
(1)
Po
(t)
DA
(0) Pe
N
B
Pe
(8)
N 96
B (1)
(51)
N
However, the calculation be simplified. at least for certain choices of the distributions Pe 96 as (Mironov et al. 2019) show that
(t)
Dx
Pe
(8)
B N
(6) 96
Pe
2
DA
Pe
N
B
Pe
96
(8)
(52)
N
N
N
allowing us to focus on the first term. Furthermore, again following (Abadi et al. 2016 Mironov al. 2019), this divergence be simplified for general mixture with weights and
ax, our
specific choice of (t) and Po and for integer A:
(t)
(1 a:)r
+ co (e)
)7)
Dx (11 a)pg + aq (1) (8)
=
A log
(c) Pd
((1)
(53)
A
4
A log
Ea-B(ho)
E (1)
(54)
P0
Pe
1 log
) )
Oz
BA-B(A,B/N)
e 202
(55)
This allows us to readily calculate of the terms in Algorithm
Algorithm Privacy accounting for DP-REC with subsampling for privacy amplification. A are Rényi orders À > 1 that will be considered and are the total number of bits used to represent the neural network update. Furthermore, T are the total communication rounds for training, B is the number of users considered each round and N is the total number of users in the federation. d is the target probability of DP failing to provide a guarantee.
(
A(00 + 0, AA A
A
m) (0) 0, AλεA
for t + 1,...,TTh TB do
Dz (2(2 11(6))
((0) (!1-1) + maxo
for À E A do
200 - 11(-1) + max
maxe, db Dx
N-1
N
Pg
+ N 96 Pe
(1) (8)
maxo. DA
(t)
N P0
-
+ N 9
(t)
(t) t m
(t-1) max
maxo DX+1
N-1
N Po
(t)
N 44
P0
m
(t)
N- (4)
(t)
maxe.6 Dx+1
Pg
N
Po
N 4
end for end for
f- min
(TB) 1
m
(TB)
log
12
p (TTB)
A
π
25
21

---

Under review as a conference paper at ICLR 2022
B.2.3 OVERALL ALGORITHM FOR FEDERATED TRAINING WITH DF-REC
Algorithm 8 Overall federated training pipeline when using DP-REC, S corresponds to all clients in the federation and to a specific client. C' corrrsponnss to the desired sensitivity.
procedure SERVER TRAINING(I;
H3 = {[I', 3 E for E (0... T} do
>> History with model initial seed It'
S' + Sample set of participating clients with replacement
M + 0
Round memory
for E S' in parallel do
msg. t create saseee_essageee_ee ftt__fforoeoeeeee ciient(s, He)
k, Rs + clien__rrainnng(mess.
M + MU[(k R3
end for
for s E do
H, t- update hinutt__isttrssss_ H.. M))
end for
A
E dec. k*)
(1+1) (()) 010 (9)
end for E + compute E guarantee for given 8.
Using Alg.
end procedure
procedure CLIENT TRAINING(MSg.)
(()) + receive_messageepee
> Refers to Alg.
(())
for local epoch e {I..... E} do
for batch b B do
w. w. Ve(w! b))
> corresponds to the local loss
end for end for Φ.
w(t)
d Φ= min(1, " (2)
R( + Choose a random seed
k < enc. (1 R!!))
Using Alg.
return R ((()) end procedure
C EXPERIMENTAL DETAILS
The experiments in the main text were performed on two Nvidia RTX 2080Ti GPUs, as well on several Nvidia Tesla V100 GPU's available on internal cluster over the span of weeks.
C.1 DATASETS & MODELS
MNIST For MNIST, we consider a LeNet-5 (LeCun et al. 1998) model trained on federated version of the original 50k training images. We split the data across 100 clients non-i.i.d. way where the label proportions on each client are determined by sampling Dirichlet distribution with concentration a = 1.0 (Hsu et al., 2019). For evaluation, we assume the standard validation split of MNIST to be available at the server. We run all experiments four times with different seeds, except the one with DP-REC and & = 3 which we run with eleven seeds, as had an "outlier" run which skewed the average and increased considerably the standard error.
FEMNIST
FEMNIST is a federated version of the extended MNIST (EMNIST) dataset (Cohen
al. 2017 It consists of MNIST-like images of handwritten letters and digits belonging one
22

---

Under review as a conference paper at ICLR 2022
Table 2: Federated training sets
Dataset
Number of devices
Total samples
Samples per device
mean
std
MNIST
100
50, 000
500.00
73.10
FEMNIST
3500
705, 595
201.60
78.92
Shakespeare
660
3, 678, 451
5573.41
6460.77
StackOverflow
342,
135, 818, 730
396.58
1278.94
of 62 classes. The federated nature of the dataset naturally determined by the writer for given datapoint. Additionally, the size of the individual clients' datasets differ significantly. In the literature, there are two versions this dataset used for experimentation. Originally published by (Caldas et al.. 2018), their published code code"ppro provides recipe pre- pre-process the dataset into the federated version. Unfortunately, however, the statistics reported in the paper do not align with the result of this recipe. We repeat the statisties as we use them for our experiments in Table 2 As mentioned in the main text, some works such as DDGauss (Kairouz et al. 2021 use the FEMNIST version provided by tensorflow federated It consists of smaller subset of 3400 clients. For the model architecture, we consider the convolutional network described in (Kairouz et al.) 2021). albeit without dropout regularization. We run four seeds for DP DP-FedAvg and DP REC with E 1,3, 6.
Shakespeare For the Shakespeare dataset we closely follow (Caldas et al. 2018). Each client corresponds to a unique character across the collection of Shakespeare's plays with a minimum number of spoken lines. The non-i.i.d. characteristics of this dataset are due the different "speaking" styles of the resulting 660 roles. We use the same 2-layer LSTM model as in (Caldas et al. 2018) for this next-character-pree preddction task (considering library of 80 characters). Each client predicts the next character following the LSTM encoding of the previous 80 characters. For Table 2 we consider each pair of 80 character plus next character as a single sample. The statisties we report differ markedly from the statistics in (Caldas et al. 2018), reported on corresponding issue raised We run four seeds for both DP FedAvg and DP-REC.
in their code base
SverkOverflow The StackOverflow dataset (TF Authors 2019) consists of collection of ques- tions and answers posted on the StackOverflow website during a certain time window. Each user of that website who posted there that time-frame is considered client with their aggregated posts as the client's dataset. Here, we consider the task of tag prediction described in (Reddi et al. (2020). Associated with each posting (irrespective of whether it a question or an answer) is associated at least one of 500 tags. Each client is therefore performing one-vs-all classification corresponding to 500 binary classifications. We pre-process each post by creating a bag-of-worde representation the 10, 000 most frequent words, normalized to 1. As model, we consider logistic regression. Learning curves in the main paper were created by selecting the first 10, 000 data-poina when iterating over shuffled list of hold out clients. As noted in the main text, each run selected different seed for shuffling, resulting in non directly comparable learning curves. For the results in Table the final model was evaluated on all 16, 586, 035 datapoints across all hold out client. Note that with 1, 500 communication rounds and 60 clients per round, only ~ 26% of all clients participate in training. We run two seeds for both DP- FedAvg and DP RERE
C.2 HYPERPARAMETERS
For all of the experiments in the main text we used 7-bit per tensor quantization for DP-REC. This was determined after the ablation study on the FEMNIST dataset, shown at Figure 2 The only difference was at the StackOverflow experiment where, to have reasonable æ DP guarantee, we used 5 quantization groups for the weight matrix of the logistic regression model (each with 106 entries) and did per-tensor quantization for the biases (i.e., we had 6 quantization groups in total). As we
on/
dat datasets//mm)
23

---

Under review as a conference paper at ICLR 2022
mentioned in the main text, for DP-REC we performed sampling with replacement to select clients for each round on all tasks, since the improved privacy amplification was beneficial. For DP- -Feevd we use the traditional sampling without replacement on each round but with replacement across rounds.
Tuning privacy hyperparameters Privacy guarantees depend essentially the ratio of the clipping threshold and the prior noise scale a. For all experiments, we fixed the ratio, determined by our accounting upfront, in order ensure a chosen at the end of the experiment. More specifically, for DF-FedAvg we tune the clipping threshold for each task and pick the appropriate noise scale for a given E guarantee. For DP-REC the clipping threshold was multiplicative factor of the standard deviation of the prior over the deltas, i.c., CO, and c was tuned in order to yield a specific & guarantee. The free parameter that we thus optimize is a. For Ø, we considered values ranging from 10-5 up to 1, finding the right order of magnitude and then fine-tuning within that order if necessary (e.g. considering 0.001, 0.003, 0.005, etc.), based on validation performance. Of course, in practical deployment such tuning would need to be taken into account when computing final privacy parameters, as discussed by Abadi et al. (2016) Appendix D).
MNIST For this task we used SGD with learning rate of 0.01 for the client optimizer and Adam (Kingma & Ba 2014) with a learning rate of 2e - 3 for the server optimizer for all of the experiments. The 31, B2 parameters of Adam were kept at the default values (0.9 and 0.999) and we trained for 1 glohal communication rounds rounds. We used 10 clients on each round, where each client performed 1 local epoch with batch size of 20. For DP-FedAvg the clipping threshold was 0.01 whereas for DP REC the prior standard deviation was fixed to a = 0.005. In order to get E 3.6 for DP FedAvg we used noise scale of 3.8 and 2.15, whereas for DP RE- we used C 0.5 and c = 0.7625 respectively.
FEMNIST For optimization we used SGD with learning rate of 0.05 locally and SGD with learning rate of 1.0 globally, i.c., we averaged the local parameters. For all of the methods we sampled 100 clients for each round and each client performed 1 local epoch with batch size of 20. For DF-FedAvg we trained for 1.5k rounds with a clipping threshold of 0.1 and for DP-REC we found it beneficial to train for 4k rounds (and thus we had to clip more aggressively on each round) and the was fixed to 0.03. In order to get of 1, 3 and 6 we used noise scale of 5, 1.85 and 1.15 for DP DF-Fedg and a c 0.75, 1.35 and 1.66 for REC.
Shakespeare Both the global and local optimizers for this task were SGD with learning rate of 1.0. We trained for 200 rounds where on each round we sampled 66 clients and each client performed the clipping threshold was 0.3 whereas for DP-REC the prior standard deviation was fixed to a = 0.1. In order to get a e of 3 we used a noise scale of 2.15 for DP-FedAvg and c of 1.36 for DP-REC.
1 local epoch with batch size of 10. For
StackOverflow For this task we mainly used the hyperparameters provided at (Andrew et al., 2019). More specifically, for the local optimizer used SGD with a learning rate of 10 whereas for the global optimizer we used SGD with a learning rate of 10-0.25 and a momentum of 0.9. We sampled 60 clients per round and each client performed 1 local epoch with a batch size of 100. We trained the logistic regression model for 1.5k rounds. For DP-FedAvg the clipping threshold was 0.05 whereas for DP REC the prior standard deviation was 0.05. For of we used noise scale of 0.957 for DP-FedAvg and of 1.227 for DP-REC
D ADDITIONAL RESULTS
D.1 ACCURACY FOR A FIXED PRIVACY BUDGET
Figure 3 shows the accuracy achieved as function of the privacy budget e. For a discussion of these results refer to the main text.
D.2 PRIVATE MEAN ESTIMATION
We ran experiment compare DP-REC with the method of Chen et al. (2020) and see the effects of
Kashin's 's representation and shared randomness. Removing privacy from the equation and comparing compression methods head-to-head with 1-bit communication (+ bits for shared randomness,
24

---

Under review as a conference paper at ICLR 2022
70
Accursey
Accuracy
DP-FedAvg <
DF-FedAvg. <<3 DP.FedAvg.
DF-FedAvg. E
30
DP-FedAvg,
DP-REC,
20
20
OP-REC, <
DP-REC, E <
OP-REC, c<6
10
DP-REC, <
0
3 Privacy budgel
6
0
Privacy budget
(a) MNIST
(b) Femnist
40
DP-FedAvg. e <
35
DP.REC, 3
Recaligex111 100
Accuracy
25
20
10
DP-FedAvg. DP-REC, <<1
5
0.5
1.0
1.5
2.0
2.5
3.0
0.88
Privacy budget
Privacy budget
(c) Shakespeare
(d) StackOverflow
Figure 3: Test accuracy (%) as a function the privacy budget e (for a fixed 5 1/N11).
explain below), we find that (Chen et al. 2020) performs slightly better than DP DP-REC in terms of mean squared error (MSE), when the latter uses poorly informed prior (e.g. zero-mean Gaussian). When DP-REC is equipped with better prior (e.g. Gaussian with the mean 1/vd in all dimensions), it is comparable or outperforms (Chen et al. 2020 For example, estimating a 200-dimensional mean from 10k samples, MSE of (Chen al. 2020 is 0.07, for DP-REC with a poor prior it is ~0.3, and for DP-REC with a better prior is 0.03. There are a few points to elaborate on:
Shared randomness. Similarly to DP-REC, (Chen et al. 2020) have a choice between public randomness (defined by the server) shared randomness (defined by clients). As explained in our paper, the latter is preferred choice in terms of privacy, but adds a few bits client-server communication (for the random seed). We found that also improves performance and that the method of Chen et al, (2020) did not work well in few-bit bit settings with public randomness (MSE 10.0 in the above example).
Prior. DP-REC a method that's more dependent on a good prior. With a poor choice, in one-shot settings like mean estimation. performance be compromised. However, it makes it more suitable for FL scenarios where prior is gradually improved with every round.
Adding privacy to the mix. somewhat penalized due to the overhead term in our Theorem 1, which for the above setting requires at least 21 bits per message to achieve å < 10-5, Nonetheless, this is not problem in FL, since practical communication bit-width would be larger in any case. Moreover, DP-REC privacy can be further amplified by implementing the secure shuffler, similarly to Girgis et al. (2020), resulting even tighter privacy guarantees.
important to note that DP-REC communication gets
D.3 ADDITIONAL BASELINES
curious reader may wonder how would a simple baseline of compressed gradients combined with DP-FedAvg fare against our method. Unfortunately, combining DP-FedAvg (or differential
25

---

server (since adding noise Under review as a conference paper at ICLR 2022
privacy in general) with compression is not straightforward task. which is why it motivates paper. There are two options: (i) ensure DP, then compress the update; (ii) compress, then ensure DP. Each option has its challenges.
First, consider (i). Adding noise at the client and then compressing the update before transmission, might not allow calibrate noise the aggregate and the use tighter composition theorems (e.g., Rényi accountant), degrading the privacy guarantee. This is what essentially led to the development of hybrid methods such as cpSGD and DDGauss. As this direction was researched in the line of work leading up to DDGauss, we take their method as the best representation of such approach. Let us now consider (ii). Once updates are compressed by the client, we cannot add noise directly, because it would negate any compression. Therefore, the client needs to transmit the update first, using secure aggregation to protect against konest-but-curious server. We can compress updates using scalar quantization, but secure aggregation might add communication overhead countering some of the effects of compression (see Bonawitz et al. (2017)) Even without the additional communication overhead of secure aggregation, we empirically observed that such method can have both worse accuracy and worse communication efficiency than OP-REC and represents a rather weak baseline. We ran experiment on MNIST task and combined 8-bit scalar quantization of the client updates (in a way that satisfies the desired sensitivity) with DP-FedAvg with & = 3; there we observed that the global accuracy reached 58% after I rounds, which is both smaller than the DP-REA result and significantly more expensive in terms of communication. Lastly, we were to consider vector quantization to get ahead in terms of compression ratios, would hinder application of secure aggregation, leaving us without any protection against not possible either, it would nullify compression).
Of course, there exists a number of diverse gradient compression methods that could be considered, and that could be more easily combined with either SecAgg or DP, but leave exploration of these methods for future work.
D.4 COMPRESSION-ONIA PERFORMANCE OF OUR METHOD
In order to investigate the behaviour of the compression part DP-REC, we performed some experiments our 4k round FEMNIST task where omit the clipping part of DP-REC. We consider three runs:
A baseline of vanilla FedAvg on this task without compression,
2. REC compression with the same hyperparameters as for the with-DP experiments but without clipping,
3. REC compression but with quantization of groups of size 64 (instead of per-tensor guantization).
The results can found at Table 3
where we also include the results from DP REC for reference. We that the compression part of DP-REC performs quite well, reaching performance similar to FedAvg while significantly reducing the total communication costs. It is worthwhile to note that there is multitude of other hyperparameters that could be tuned further refine the compression- only performance, such as: tuning the prior a; varying the vector-size over which is computed; the bit-width b; additional application of entropy-coding for the larger number of indices; adaptive K per round. We leave a more detailed compression-only evaluation of our method to future work.
26

---

Under review as a conference paper at ICLR 2022
Method
Accuracy
GB
DP-REC (==1) 1)
59.3 = 0.1
14.2
DP-REC (==3) 3)
67.0 + 0.1
14.2
DP-REC (s=6) 6)
69.1 + 0.1
14.2
FedAvg (no DP compression)
86.28
690.6
REC (no DP clipping) REC (no DP clipping, 64)
80.69
14.2
84.14
332.2
Table 3: Compression-only (i.e., no DP) ablation studies, all run for 4k rounds. "was still improving after 4k rounds.
27


Reviews:
[{"review_id": "widCFNdLjH5", "reviewer": "Reviewer_Kc1E", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n1) The Bayesian approach taken by this paper is different from the worst-case guarantees provided in many papers studying a similar problem (Agarwal 18, Chen 20, Girgis 20). The promising results in this paper could therefore a inspire a new line of research in this area.\n2) The paper introduces plenty of new ideas to the federated learning community, both in the main algorithm and its analysis.\n3) Experiments validate that the proposed algorithm provides very high compression in the high privacy regime ($\\varepsilon < 1$).\n\n**Weaknesses**\n1) Computational complexity: The algorithm in its general form requires $b$ samples to be drawn from a high-dimensional distribution. This is computationally costlier than many other known methods.\n\n2) Given that Chen 2020 is known to be optimal under joint privacy and communication constraints, a *theoretical* comparison with results in Chen would have to theory of this paper. This could have been done for both *good* and *bad* prior. ", "summary_of_the_paper": "The paper proposes a differentially private and communication-efficient method to aggregate the client updates in federated learning. The method is based on a recently proposed compression technique relative entropy coding. The authors further modify this technique to satisfy differential privacy guarantees and perform various experiments to back their claims.", "summary_of_the_review": "Overall, I like this paper and recommend it be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "pwJFW3fjsg1", "reviewer": "Reviewer_Uy67", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\nThe idea of applying REC to compress a (distributed) DP mechanism is novel and elegant, and the connection between the communication budges and the privacy guarantees are also interesting. The comparisons with previous works and the experiments, in my opinion, are adequate. I also appreciate the authors' discussions on whether DP-REC is compatible with other privacy amplification techniques.\n\nCons:\n\n\n1. My major concern is the correctness of \"per-parameter compression\". All of the theorems, including the privacy guarantee and the communication bound, are derived for the network-wise compression, and the authors claim that one can directly apply these results to parameter-wise compression since both the prior distribution $p_\\theta$ and the target distribution $q_\\phi$ are product measures. However, I am not very sure about this statement. Though the target distribution $q_\\phi$ is a product measure, the law of the outcome of DP-REC (Algorithm 3) $q_{\\tilde{\\pi}}$ may not be of a product form. Similarly, I don't see how $\\pi_k$ in Algorithm 3 can be decomposed into a product form.  Therefore, in general, I am not so sure about whether equation (4) will still hold if we decompose it coordinate-wisely. \n\nSince the main theorem is based on equation (4) and all experiments are carried out with per-tensor compression, I think it is important to give a formal statement and proof to show that the results also hold for per-parameter compression.\n\n\n2. It would be good if the authors can provide a detailed end-to-end algorithm for the overall FL framework, including how to pick parameters such as $b$ and $\\sigma$.\n\n\n3. When comparing with DDG on the FMNIST dataset, it seems that the accuracy of DP_REC is still significantly lower than the accuracy of DDG. Is it possible to increase the communication budgets and reduce the gap?", "summary_of_the_paper": "This paper introduces a compression and privatization technique to federated learning based on Relative Entropy Coding (REC). For each round, client $s$ aims to privatize its local model update $w_s$ by releasing $\\Delta_s = w_s + N(0, \\sigma I)$. However, instead of directly adding Gaussian noise, the client first picks $K$ random vectors from a prior distribution (which is independent of $w_s$) with shared randomness and then performs importance sampling according to the law of $w_s + N(0, \\sigma I)$. It can be shown that as long as $K$ large enough (i.e., when $\\log_2 K$ is much larger than the Renyi divergence of the prior and the target distributions), the sample obtained from importance sampling has a law close to the target distribution (i.e. the Gaussian perturbation) and thus can potentially preserve privacy. Moreover, the communication needed is $\\log_2 K$ bits per round per client. By accounting the privacy loss over $T$ rounds, the authors characterize the overall privacy guarantees, which have a clean form and connect to the communication budgets nicely.", "summary_of_the_review": "The paper is well-written and the proposed idea is novel. Discussion and comparison with related works are adequate. However, my major concern is the correctness of the per-parameter compression. If the authors can clarify this point, I am happy to further increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XCwix4ZY0-Y", "reviewer": "Reviewer_5TiV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have a few questions that I hope the authors can help clarify. \n- How is sensitivity controlled? It seems not quite clear to me the sensitivity control over \\phi_s can transfer to \\Delta_k*.  \n- It is a bit hard to interpret Table 1 and Figure 1 as both communication cost and accuracy are different. And it seems that aggressive compression will cause more accuracy drop. Since the communication-accuracy tradeoff of DP-REC can be tuned by K, or for different numbers of parameters/layers, can DP-REC match DP-FedAvg accuracy with less aggressive compression?\n- Could the authors provide the clip norm and noise for both DP-FedAvg and DP-REC with some explanation? Appendix C.2 provides some, but I would appreciate an “apple-to-apple” comparison and some explanation on why from a first glance, the noise in DP-REC can be much smaller. \n- Is it possible to provide more baselines? For example, DP-FedAvg with compression?\n- The two versions of EMNIST (3.4K vs 3.5K) may have different numbers of labels, probably want to double check that the comparison is correct for table 1. Or even better, try to reproduce DDG with the same setting. \n", "summary_of_the_paper": "This paper studies differentially private algorithms in federated learning, and proposes to take advantage of the randomness in Relative Entropy Coding (REC) to achieve good privacy-utility trade offs while significantly saving the communication costs. On four benchmark datasets (MNIST, FEMNIST, Shakespeare, Stack Overflow linear regression), under same privacy epsilon, the proposed method can save communication for ~(4000, 20, 800, 100)  times with accuracy loss ~(15, 6, 10, 1) compared to DP-FedAvg. \n\n\n\n\n======= after rebuttal ============\nI appreciate all the clarification and improvement on the draft. This paper is a borderline to me for the remaining concerns.\n\nI want to be more specific here on \"apples-to-apples\" comparison. There are three things considered: differential privacy, communication and accuracy. It would be useful to show how this method can help achieve a reasonably good metric by tuning the other two metrics. Only working in the low accuracy regime sounds like a big limitation, and did not compare with other stronger compression method further weaken the claim (as also mentioned by other reviewers).\n\nThe authors mention secure aggregation in their rebuttal. IIUC, secure aggregation is future work in this draft. It is not very convincing.\n\nThat being said, The idea seems to be interesting, and I will raise the score from borderline reject to borderline accept.\n\n", "summary_of_the_review": "It is a bit hard to justify the significance as it is not an apples to apples comparison as both communication and accuracy are different. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2MkwjHDdKWw", "reviewer": "Reviewer_qyw3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the most interesting part of this paper is that it leverages the randomness in the sampling process to achieve differential privacy, and gives privacy bounds. I didn't check the proof in the appendix in detail, but the analysis makes sense to me at the high level.\n\nThis work also considers local privacy in addition to client-level privacy. It describes the relations with previous works and the experimental setups reasonably well.\n\nMy major concerns are that (1) the recovered model updates at the server side (even without clipping for privacy) are biased wrt the true model updates; (2) the algorithm doesn't support selecting multiple clients at each round, and (3) experiments can be improved.\n\nRegarding (1), I think it is probably fine (and not difficult) to give a convergence bound with a small error term. Regarding (2), if there are many clients in the entire network, picking only one of them at each communication round can make the convergence unstable, or reach a lower accuracy. I am wondering if it is possible to extend the current algorithm by selecting a subset of clients, allowing each of them to run Alg 3 independently (with their own random seeds), and aggregating these model updates at the server (after the server recovers each update with the corresponding random seed)? This will affect both privacy and convergence.\n\nAccuracy drops significantly under the same privacy budget in the experiments (e.g., on the simple MNIST dataset, the accuracy is 10% lower than DP-FedAvg for a large epsilon value), but the compression ratio is very high. DP-REC allows for different compression granularities such as per-parameter clipping. Is it possible that such kind of more fined-grained compression can increase the final accuracy, although transmitting more bits each round?\n\nI think there are multiple potential baselines on compression + DP. E.g., apply DP on top of any gradient compression method. These should be considered or at least discussed in the experiments. The goal of DDGauss is not compression (though it results in quantized model updates). Therefore it may not be a strong compression baseline.\ncpSGD, ATOMO (https://arxiv.org/abs/1806.04090) + DP, selecting top-k coordinates (measured by magnitudes)+DP are all reasonable baselines.\n\n\nMinor:\n\n* I think some notations might be a bit confusing, e.g., w \\sim q_{\\phi}(w) (the third line in Sec 2.1). It would be more clear to use different notations for random variables and samples. In algorithm 3, can note k \\in {1, ..., K}.\n\n* Moving the discussions on the choice of sigma values to the main text could be better.\n\n* Experiments: It would be helpful for readers to further understand the behavior of the proposed method if it also includes results on applying compression alone with a good \\sigma without clipping (i.e., not considering privacy budgets). That will demonstrate how good the (biased) compression itself can be.\n\n* What does 'tensor'(generally understood as multi-dimensional arrays) mean in the context of this work? Does it refer to different sets of named parameters in the model? ", "summary_of_the_paper": "This paper proposes a compression scheme for federated learning built upon previous relative entropy encoding works. It then proves that with some small modification (clipping the model updates), the algorithm is inherently differentially private. Empirical evaluation shows that the proposed method can achieve much more communication reduction at the cost of accuracy degradation.", "summary_of_the_review": "I think the most interesting part of this paper is that it leverages the randomness in the sampling process to achieve differential privacy. My major concerns are that (1) the recovered model updates at the server side (even without clipping for privacy) are biased wrt the true model updates; (2) the algorithm doesn't support selecting multiple clients at each round, and (3) experiments can be improved.\n\n\n=== update ===\n\nAfter reading the authors' responses, some of my concerns have been addressed. Therefore, I increase my score to 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission describes an approach to compressing the communication in federated learning. The key idea is using a set of random samples from a prior distribution and then performing importance weighed sampling. The work performs an analysis of the privacy guarantees of this process and experimental evaluation.
The main issue with this work is the authors appear to be unaware that the basic problem they pose is solved in a more comprehensive and lossless way in a recent work https://arxiv.org/abs/2102.12099 (Feldman and Talwar, ICML 2021). That work shows that any differentially private randomizer can be compressed via a simpler algorithm that performs rejection sampling using a PRG. The algorithm does not loose privacy or utility (under standard cryptographic assumptions) while guaranteeing low communication. In contrast this work loses significantly in utility and provides opaque privacy guarantees.
This submission analyzes  a randomized that adds Gaussian distribution and, in particular, the compression technique in (Feldman and Talwar) applies to it. The technique proposed in this work is very similar in spirit (with prior distribution corresponding to reference distribution in the earlier work.
In light of the earlier work I do not think the contributions in this submission are sufficient for publication.
Decision: Reject