Sparse Random Networks for Communication-Efficient Federated Learning
Authors: Berivan Isik
Francesco Pase
Deniz Gunduz
Tsachy Weissman
Zorzi Michele
Venue: ICLR 2023 poster (2023)
Keywords: communication-efficient federated learning
sparse networks with random weights
compression
sparsity.

Abstract: One main challenge in federated learning is the large communication cost of exchanging weight updates from clients to the server at each round. While prior work has made great progress in compressing the weight updates through gradient compression methods, we propose a radically different approach that does not update the weights at all. Instead, our method freezes the weights at their initial \emph{random} values and learns how to sparsify the random network for the best performance. To this end, the clients collaborate in training a \emph{stochastic} binary mask to find the optimal sparse random network within the original one. At the end of the training, the final model is a sparse network with random weights -- or a subnetwork inside the dense random network. We show improvements in accuracy, communication (less than $1$ bit per parameter (bpp)), convergence speed, and final model size (less than $1$ bpp) over relevant baselines on MNIST, EMNIST, CIFAR-10, and CIFAR-100 datasets, in the low bitrate regime.

Published as a conference paper at ICLR 2023
SPARSE RANDOM NETWORKS FOR COMMUNICATION-EFRICINNN FEDERATED LEARNING
Berivan Isik ;; Francesco P Deniz Gunduz', Tsachy Weissman Michele Zorzi Stanford University, University of Padova, *Imperial College London
berivan. isi isik@stanford edu, pasef wtw.eeddddiiidddddeee.e it
ABSTRACT
One main challenge in federated learning is the large communication cost of ex- changing weight updates from clients to the server at each round. While prior work has made great progress in compressing the weight updates through gradi- ent compression methods, we propose radically different approach that does not update the weights at all. Instead, our method freezes the weights at their initial random values and learns how to sparsify the random network for the best per- formance. To this end, the clients collaborate in training a stochastic binary mask to find the optimal sparse random network within the original one. At the end of the training, the final model is a sparse network with random weights - or a sub- network inside the dense random network. We show improvements in accuracy. communication (less than bit per parameter (bpp)), convergence speed, and final model size (less than 1 hpp) over relevant baselines MNIST, EMNIST, CIFAR- 10, and CIFAR-100 datasets, in the low bitrate regime.
INTRODUCTION
Federated learning (FL.) is a distributed learning framework where clients collaboratively train a model by performing local training their data and by sharing their local updates with every few iterations, which in turn aggregates the local updates to create a global model, that is then transmitted the clients for the next round of training. While being an appealing approach for enabling model training without the need to collect client data at the server, uplink communication of local updates significant bottleneck FL (aiiruuz al. [202T). This has motivated research (Kirrou
in communication-efficcie FL strategies (McMahan et al., 201 7a) and various gradient compres- sion schemes via sparsification (Lin et al., 2018 Wang et al. 2018, Barnes et al. 2020 Ozfatura
let al. 2021 Isik al. (002),, quantization Aliistrr et al.) 2017 Wen et al. 2017
Bernstein et al.
2018
Mitchell et al. 2022). and low-rank approximation (Konečný et al. 2016
Vargaftik et al.
2021
2022; Basat et al. 2022). In this work, while aiming for communication efficiency in FL
we take a radically different approach from prior work, and propose strategy that does not require communication of weight updates. To be more precise, instead of training the weights,
(1) the server initializes a dense random network with d weights, denoted by the weight vector iint (wititt w22 ...., i using a random seed SEED, and broadcasts SEED the clients enabling them to reproduce the same init locally,
(2) both the server and the clients keep the weights frozen at their initial values w init at all times,
(3) clients collaboratively train probability mask of d parameters 0 (01, .l..e................ 0a) [0,
(4) the server samples a binary mask from the trained probability mask and generates a sparse network with random weights subnetwork inside the initial dense random network as follows
final final Bern w init
w
where Bern(-) is the Bernoulli sampling operation and @ the element-wise multiplication.
We call the proposed framework Federated Probabilistic Mask Training (FedPM) and summarize it in Figure I At first glance, it may seem surprising that there exist subnetworks inside randomly
First two authors contributed equally. Work done while F.P. visiting Imperial College London.

---

Published as a conference paper at ICLR 2023
initialized networks that could perform well without modifying the weight values. This phe- nomenon has been explored to some extent in prior work (Zhou et al. 2019 Ramanujan et al. 2020
Pensia et al. 20200 Diffenderfer & Kailkhura 2020 Aladago & Torresani] (0221) with different strategies for finding the subnetworks. However, how to find these subnetworks in FT. setting has not attracted much attention far. Some exceptions this works by Li et al. (202T): Valla- puram et al. (2022); Mozaffari et al. (202I), which provide improvements in other FL challenges, such as personalization and poisoning attacks, while not being competitive with existing (dense) compression methods such as QSGD (Alistarh et al., 2017), DRIVE (Vargaftik et al., (021), and SignSGD (Bernstein et al., 2018) in terms of accuracy under the same communication budget. In this work, we propose stochastic way of finding such subnetworks while reaching higher accuracy at reduced communication cost less than bit per parameter (bpp).
Trainable Probabiility mask
Randomly weighted network
Stochastic
Randomly weighted sparse network
00,
m' Beru(f")
13*
Rd
by
itit
Figure Extracting a randomly weighted sparse network using the trainable probability mask Of in the forward-pass of round (for clients and the server). In practice, clients collabora- tively train continuous scores s E Rd, and then at inference time, the clients (or the server) find =²= Sigmoid(s*) E [0, 1]d. We skip this step in the figure for the sake of simplicity.
In addition to the accuracy and communication gains, our framework also provides an efficient representation of the final model post-training by requiring less than I bpp to represent (i) the random seed that generates the initial weights w init and (ii) a sampled binary vector Bern (computed with crucial feature
the trained 0). Therefore, the final model enjoys for machine learning at power-constrained edge devices. Another advantage our framework brings is the privacy amplification under some settings, thanks to the stochastic nature of our training strategy.
memory-efficien deployment
Our contributions can be summarized as follows:
(1) We propose FL framework, in which the clients do not train the model weights, but instead a stochastic binary mask to be used in sparsifying the dense network with random weights. This differs from the standard training approaches in the literature.
(2) Our framework provides efficient communication from clients to the server by requiring (less than) bpp per client while yielding faster convergence and higher accuracy than the baselines.
(3) We propose a Bayesian aggregation strategy at the server side to better deal with partial client participation and non-III data splits.
(4) The final model (a sparse network with random weights) can be efficiently represented with a random seed and binary mask which requires (less than) bpp at least 32x more efficient storage and communication of the final model with respect to standard FL strategies.
(5) We demonstrate the efficacy of our strategy MNIST, EMNSIT, CIFAR-1O, and CIFAR-100 datasets under both IID and non-IID data splits; and show improvements in accuracy, bitrate, con- vergence speed, and final model size over relevant baselines, under various system configurations.
2 RELATED WORK
In this section, we briefly discuss the related work in (1) communication-cfficiii FL (2) pruning for FL and (3) finding subnetworks in random network.
2

---

Published as a conference paper at ICLR 2023
Communication-Effieii FL. One way of improving communication efficiency in FL to com-
press the model updates using gradient compression methods like sparsification (Aji & Heafield
2017 Lin et al. 2018:] Wang et al. 2018: Barnes et al.
2020; Ozfatura et al.
2021 Isik al. 2022)
quantization (Alistarh et al. 2017; Wen et al. 2017; |Suresh et al. 2017 7 Bernstein et al. 2018
Mitchell et al. 2022), and low-rank approximation (Wang al. 2018: Vogels et al. V
ct al. 2021; 2022; Mohtashami et al. 2022| Basat et al. 2022
: or more FL-oriented compression
schemes such as (Konečný et al. 2016 McMahan al. 701 Sattler et al. 2019 Rothchild al.)
2020 Reisizadeh et 2020 Haddadpour et al. 2020; 2021). while training a dense network. Our
framework differs from these dense compression methods substantially due to the unconventional
stochastic mask training strategy; however, we take SignSGD (Bernstein et al. 2018). TernGrad
(Wen et al. 2017). QSGD (Alistarh et al. 2017), DRIVE (Vargaftik et al. 2021). and EDEN (Var-
gattik et al. 2022) as our baselines since they work in the same bitrate regime as ours (2/1 hpp).
Pruning for FL. Since the introduction of the Lottery Ticket Hypothesis (LTH) Frankle & Carbin 2018), there has been growing interest in finding sparse and trainable networks at initial- ization. The main hypothesis in this line of work is that there exist sparse networks (lottery tickets) inside randomly initialized dense networks such that those sparse networks can be trained to a sur- prisingly good performance. In the original paper, the strategy for finding these lottery tickets is to iteratively train the dense network, i.e., finding the lottery tickets is expensive. We distinguish
our approach from the FL papers that utilize the LTH (Li et al.] 2020: Ji et al. 22000; [Seo et al.
2021 and pruning (Lin al. 2020 Munir et al. [202]] Yu et al. 2022 2021 Liu et al. [022]] 202IJJiang et al.
2022 Babakniya et al. 2022 Dai et al. 2022; Lin et al. 2020 Bibikar et al. (022) for three mains
reasons: (i) These methods require training the weight values, and thus cannot provide an efficient representation of the final model as FedPM] does. Recall that we achieve at least 32x more efficient storage and communication of the final model by representing it with just a random seed and a bi- nary mask. (ii) Some of these works require finding the lottery tickets prior to FL "raaiiin (Li et al.) 2020j. While this could improve the communication cost during the [rrtiiig since they commu- nicate sparse networks, it increases the computation cost significantly due to the burden of finding lottery tickets via training. (iii) As opposed to the L or pruning-based FL works, our framework learns with what probability& a particular weight should stay in the final model, i.e., the final sparsity level is also a learned parameter optimized for the best performance. Overall, since [edPM] is not in the same bitrate regime as these works (they require higher bitrates to communicate continuous weight values), we do not compare against them.
Finding Subnetworks Inside a Random Network. Our work is closest recent works of Zhou et al. (2019); Ramanujan et al. (2020); Pensia et al. al. (2020); (Aladago & Torresani (202I), which find subnetworks (or supermasks) inside a dense network with random weights that perform surprisingly well without ever training the weights, but in a centralized scenario. In this work, we take advantage of the existence of such subnetworks to reduce the communication budget in FL to less than bpp with faster convergence and higher accuracy than our relevant baselines in the same bitrate regime, while further compressing the final model, all simultaneously. Prior works (Li et al.) 2021] Vallapuram et al. 2022] Mozaffari et al. 202T) also consider finding subnetworks inside dense random network in a setting, but they differ from our approach on several levels. For instance, they focus on different challenges in FL such as personalization and poisoning attacks, which limits their ability to improve over existing compression methods in accuracy couuracycoommuicatioon bitrate tradeoff. One fundamental reason for this is their deterministic mask training strategy, which involves hard thresholding or sign operations. On the other hand, the stochasticity in FndeedM allows us to (i) enjoy better cocurrcy-ommmunicatioo cost tradeoff, (ii) have an unbiased estimate of the true aggregate of the local masks with a provable upper bound on the error, (iii) design an improved aggregation strategy with a Bayesian approach so that the previous masks at the server are not hard replaced useful strategy specifically in unbalanced non-lID splits, and (iv) gain privacy benefits via amplification in the Bernoulli sampling step. To demonstrate these benefits over deterministic schemes, we compare our method against FedMask (Li et al.) 2021) by adapting it slightly to mainly focus on communication efficiency, rather than personalization, and to improve its eosurac-coomunicatte
efficiency performance. More specifically, we discard the initial pruning stage that was deployed for personalization. This change was necessary because (a) this paper does not study personalization, so this pruning step would put FedMask at disadvantage in our experimental setup, and (b) the initial pruning step requires extra training at client devices, which is computationally more expensive than FeddFe and the dense baselines.
3

---

Published as a conference paper at ICLR 2023
3 FEDERATED PROBABILISTIC MASK TRAINING (FedPM)
We first describe the simpler version of the FedPM framework in Section 3.1 which provides an unbiased estimation of the mean of the learned probability masks at the server with bounded error. Next, we propose a modification in our aggregation strategy by exploiting the underlying Bernoulli mechanism in Section 3.2 This helps boost the performance FedPMi the case of partial client participation. We then discuss the details of the distribution of the initial weights in Section [33 and finally describe the privacy benefits of FedPM in Section 3.4 We use capital letters for random variables. small letters for their realization and deterministic quantities, and bold letters for vectors. Moreover, we indicate with z the state of the local vector (e.g., the local mask) at client during round t, and with a its i-th component. Global values are denoted with æ and x and sets are indicated with calligraphic fonts. We denote neural network with weight vector p as fp-
3.1 FedPM
In this section, we present the general FaaneralFFedMiMiee FFedPMjrraining pipeline. First, the server randomly initializes neural network fu parameterized by the weight vector w (wffi, wh ..... w(")) E R. whose components are sampled IID according to a distribution P. using a randomly generated seed SEED. The random SEED value is then communicated to all the clients, which can locally sample the same pseudo-random vector w init which is kept fixed and never modified during training. The goal for the clients is to collaboratively train probability mask O [0, 1j which indicates the Bernoulli parameters for the global stochastic binary mask M ~ Bern( (0) E {0. 1]d, such that the function fw maximizes its performance on a given task, where W = M C will Specifically, FedPM learns the probabilities for the weights of being active, which are given by the probability mask 0- = (01, .,..... Oa) E [0, 11 To achieve this, at every round f, the server samples set Kr of [K2] K participants (out of the total clients), which individually train their local probability masks 0h.,, k E K,, by using their local datasets Dr. each composed of D2 = [Dx] samples. These local masks are then aggregated by the server in a communication-cfie -fffuffiiaaio-effiiennt way to estimate the optimal 0. At test time, at the server, the initial random network fuui is sparsified using the global probability mask 09.t, following the stochastic approach in Figure I In the following sections, we provide more details on each step of each round. We give the pseudocode For[FedPM in Appendix A
3.1.1 LOCAL TRAINING OF PROBABILITY MASKS
Upon receiving global probability mask 00.1-1 from the server at the beginning of round f, the client & performs local training and updates the mask via back-prooaaation.
First, however, we have to guarantee that the updated probability mask satisfies gh. E [0, 1]4. While this can be achieved with a regularization term the loss, this may require clipping 0².e E [o. 1] before taking Bernoulli sample, especially in the early training stages. Clipping would then make the estimate at the server biased and hence lead to a slower convergence and lower accuracy. Therefore, similarly to the work of Zhou et al. 2019), we introduce another mask, called score mask = ($1, 82, . sa) E Rd that has unbounded support and can be used to generate the probability masks through the one- to-one sigmoid function by setting 0- = Sigmoid(s). Then, the procedure for local training of the probability mask at round is as follows (here, the steps from Step 2 to 4 describe one local iteration, which is repeated number of times as standard in FL (McMahan et al. 2017ab):
(1) The server sends the global probability mask 08.2-1 to K chosen clients, and the clients set kst sigmoid='(09.--0 where Sigmoid-'(( (.) is the inverse of the sigmoid function.
(2) Then, the clients generate binary mask by first transforming back g = Sigmoid(s*:)) and then sampling a binary mask h from g as shown in Figure R.t. ~ Bern ().).
(3) The sampled binary mask then sparsifies the initial weight vector wiit, wht m k.t O wnit
(4) ho is then used for forward pass, and the loss C(fur.,, D&) on the local task is backpropagated to update the score mask k, = kht V/V[(f Dz) (n7 is the local learning rate).
All the local operations from Step 2 to Step 4 are differentiable, except for the Bernoulli sampling. We backpropagate the gradients through the Berouuli sampling operation with a throigh estimator Bengio et al. (2013), using the first-order gradient of the Bernoulli function, which is simply equal to the probability mask gk.t.
4

---

Published as a conference paper at ICLR 2023
Server Estimate
True Mean gh
K m
gat
m
(0.11
m 24
e (0,13
m 1)
Berm (
Beru(
Bern Bern(e
Sigmoid(s'1)
Sigmold(s*t)
Sigmaidds
Figure 2: Communication--fficeenn estimation of the mean of the probability masks 09.1 Each client communicates a stochastic binary mask m sampled from the local probabillity mask Q We reduce the bitrate less than bit per parameter by using arithmetic coding encode k.4 When the frequency of I's is far from 0.5 (which is usually the case with FedM(FedPM, the number of bits per parameter to communicate m f is less than 1. See Figure 3 for more details.
3.1.2 COMMUNICATION STRATEGY
Once the local training at round completed, the server needs to distill the global probability mask 0s. by taking the empirical average of the local probability masks 0s.t K kee, Ok collected from the clients. However, since we aim for communication efficiency, the clients do not send their local probability masks directly. Instead, they communicate stochastic binary sample F. from their probability masks sampled as hit Bet)( and then the server estimates the global aggregate 00 @a. ΣkEK, = This distributed mean estimation problem with
communication constraints is summarized in Figure Our estimator δo.t t Ekek, mi is an unbiased estimate of the true aggregate, in that
1
E Bem((r..) vkEK. [09.t] M VREK.
M
K REK.
Σ
EMa Rem( [M (M
K
kEK,
Σ
khe
K
kEK.
0a.t
Moreover, the estimation error is upper bounded as (the proof is given in Appendix B)
d
E Be wkEK, [[]0s.t
0 <
(2)
4K'
Since each client communicates stochastic binary mask k bpp is the worst-case bitrate for FedPM We can further reduce the bitrate to less than by using arithmetic coding (Rissanen & Langdon 1979) or universal coding (Krichevsky & Trofimov 1981 Barron et al. 1998) to encode m 5. and achieve the empirical entropy since d is large. This gives us smaller bitrates whenever the frequency of I's in k.f is far from 0.5 which is usually the case for our method (see Figure 3 and Appendix E.2 for results). We note that, with a deterministic mask training approach as in FedMask 2021 arithmetic coding of m Kits does not provide any further gain in bitrate, as we have
(Li et al. empirically observed that the frequency of I's is always around 0.5 (see Figure and Appendix E.2) here we apply arithmetic coding for FedMask improve our baseline although it was not proposed in the original paper. Moreover, FedMask (Li et al. 202I) and HideNSeek (Vallapuram et al. 2022) do not enjoy the guarantees we have their estimator (1) is not unbiased and (ii) does not have upper bound on the estimation error due to hard thresholding (Li et al. (02TT) and sign operations (Vallapuram al. 2022). This is another benefit of our stochastic sampling approach.
5

---

Published as a conference paper at ICLR 2023
3.2 FedPM WITH BAYESIAN AGGREGATION
Another important aspect that differentiates our work from existing masking methods such Fed- Mask (Li 2 and HideNSeek (Vallapuram et al. 2022) is the Bayesian aggregation strategy, which exploits the underlying stochastic mask to synthesize global model, boosting the perfor- mance in scenarios where only a fraction of the clients participate in each round. Given the proba- bilistic interpretation of the FedPM mask's values, at the server side we further model the probability mask fa. with Beta distribution Beta( (3: parameterized by the round-dependent param- eters a and f which are initialized to a. = 33.0 Ao. At the beginning of the training process, there is no prior knowledge indicating which network weight should be more important than the others, and so each entry in the probability mask is uniformly distributed [o, 1] - which is the prior distribution. Consequently, the clients' local binary masks MK's are the data the server uses to update its belief on each weight score, and so the aggregation strategy corresponds now to a posterior update. Specifically, given the conjugate relation between the ecta-Bernoolli distributions, the new posteriors are still Beta distributions with parameters
mask's
3. 2.t-11 + M and 3 35.1-1 K M
Vt 2 1,
where M = ELEK, M and 1 is the d-dimensional all-ones vector. Then, the server broad- casts to the clients the mode of the Bernoulli distributions, as suggested by Ferreira al. (202I).
9.
gs.t
a + Bo. -
where the division operation is applied element-wise. However, to obtain the best performance out of this method, the Beta parameters should be re-initialized to their original values A with some regularity. We present an ablation study to demonstrate the improvements gained by the Bayesian aggregation strategy and the reasonable choices for the resetting frequency in Section 4.3 Notice that if A 1, and if a and B re-initialized the beginning of each round, the method is equivalent to the aggregation strategy detailed in Section 3.1.2
3.3 WEIGHT DISTRIBUTION
As mentioned in Section 3.1 the fixed weight vector wiit is initialized by sampling from the distri- bution Pw using the randomly generated SEED. We note that the choice of this distribution impacts two important aspects of FedPM (i) the values of wnit highly influence the final accuracy achieved by the model, as they represent the building blocks to extract subnetwork fü (see Figure D which should be rich enough to solve the learning task, and (ii) the size of the sample space of Pw affects the number of bits needed to store the model during the inference process (this is different from the I bpp model storage when the model is not in use). Regarding (i), as also proposed in RRamanujan et al. 22020), we sample weights from a uniform distribution, whose domain is {-o, +o., where the standard deviation of the Kaiming Normal distribution (He et al. 2015). In this way, we control the variance of the neurons' output to be 1, which avoids the vanishing or the explo- sion of activation values. Previous experiments in (Zhou et al. 2019 Ramanujan et al. (202) also demonstrate the superior performance achieved by binary weights distributions when compared to standard continuous counterparts, e.g., Gaussian. Regarding (ii), even if knowing the value of SEED is enough to perfectly reconstruct the vector wiilt, one would have to generate the entire vector at every inference step. Consequently, to achieve fast inference, the actual values the weights need to be stored in the memory of the devices during the inference process. Fortunately, allows for efficient storage even during inference since (after reconstructing linia using SEED and m final {0, 1]d) we only need to indicate whether the weight values in final -a, 0, to, with a ternary representation that can be efficiently deployed on hardware (Alemdar et al. 2017
initialization
minaall
3.4 PRIVACY
Privacy is another challenge in FL as the model updates (in our case, h may leak information about the client data. In Appendix we analyze the differential privacy guarantees of FedPM and give an initial foray into how FedPM can be helpful in amplifying privacy.

---

Published as a conference paper at ICLR 2023
4 EXPERIMENTS
In this section, we empirically show the performance of FedPMjin terms of accuracy, bitrate, converge speed, and the final model size. We consider four datasets: CIFAR-10 with 10 classes, CIFAR-100
(Krizhevsky et al. 2009) with 100 classes, MNIST (Deng 2012) with 10 classes, and EMNIST (Co- hen et al.] 2017) with 47 classes. For CIFAR- 100, we use 10-layer convolutional network (CNN) CONV-10 and ResNet- 18 He et (2016); for CIFAR- 10, a 6-layer CNN CONV-6 and ResNet- 18 He al. (2016); and for MNIST and EMNIST. 4-layer CNN CONV-4. A detailed description of the ar- Due to limited space, we provide the results on ResNet-
chitectures can be found in Appendix D
in Appendix E. We first compare FedPX with SignSGD (Bernttein et al.) 2018 TernGra (Wen
iet al. 2022 and FedMask (Li al. 2021 on IID data split and full client participation in Section We then extend our experiments to non-IlI) IID data splits and partial participation in Section 4.2 Finally, in Section 4.3] we present a key ablation study to justify why the Bayesian aggregation strategy is necessary for partial participation and to demonstrate how the resetting frequency affects the con- vergence rate and the final accuracy. Clients perform 3 local epochs in all experiments. We provide additional details on the experimental setup in Appendix D We present results averaged over runs.
2017). QSGD (Alistarh et al.
2017). DRIVE (Vargaftik et al. 2021). EDEN Vargaftik et al.
4.1 IID DATA SPLIT AND FULL PARTICIPATION (K N)
In this section, we focus on IID data distribution and the case when all the clients participate in the training at each round. We set the number of clients to N K 10. We report the estimated bitrate for the arithmetic code that uses the empirical frequency of the symbols (for our method FedPM this corresponds to the frequency of 1 I's in m f.,) which is equal to the empirical entropy
for blocklength as large as the model size. In Figure 3 we compare the accuracy, bitrate, and
convergence speed FedPP with relevant baselines. As can be seen in the figure, FeedPMMcovveerree
to the highest accuracy on all four datasets. DRIVE, EDEN, and QSGD (they mostly overlap in the accuracy plots) seem be the three baselines that perform the best after however, their convergence speed is significantly lower than FedPM] In terms of convergence speed, FedMask is the fastest among the baselines- in fact, at the beginning of the training, FedMask faster than FedPM as well. However, its final accuracy is lower than the others. We also would like to highlight that while some of our baselines, such as FedMask and TernGrad, have a visibly high variance in accuracy, FedPX shows stable training behavior across all experiments.
Server Teal Accuracy El
Server Tast Accusscy reanvio-charttco E01
Servar Text Accuracy (srwe mniiec
Syr000
TemmCred
4.7
DRVV
Accrage: b6 (a
Auzrage toare
Averlge Stlute lorred (es5))
hedPooun
Sgr00o
DAYE
EDCN
(nditett
NN0000
Figure 3: Accuracy and bitrate comparison of FedPM with SignSGD (Bernstein et al. 2018 Tern- Grad (Wen et al. 2017), QSGD (Alistarh et al. 2017). DRIVE (Vargaftik et al. 2021). EDEN (Var-
gaftik et al. 2022). and FedMask (Li et al. 2021). all performing in the same bitrate regime.
In terms of bitrate, SignSGD and FedMask consistently spend bpp. which is the default number when a binary mask or sign mask is communicated. This means binary values (I's and 0's) are almost equally distributed in their masks, which prevents them from enjoying additional bitrate gains. Across all experiments, TernGrad has the highest bitrate. We would like to leave a note about the bitrate of QSGD. Unlike other baselines, including our work, QSGD can go down to very low bitrates by adjusting the number of levels in quantization. We have observed that in the extreme quantization case, QSGD underperforms FedPM] Then, we have decided to increase the number of quantization levels in QSGD to see if it improves the accuracy. However, as can be seen from the plots, even with bitrate larger than 1, QSGD still underperforms FedPM The only two
7

---

Published as a conference paper at ICLR 2023
baselines that challenge FedPM in terms of bitrate are DRIVE and EDEN. While FedPM has lower bitrates on CIFAR-10 and EMNIST DRIVE and EDEN have better bitrates on CIFAR-100 and MNIST. However, the accuracy of DRIVE and EDEN on these datasets (specifically CIFAR-100) is with slower convergence.
significantly lower than that of FedPM
As for the final model size, FedPM needs only 0.8 hpp for the CONV-6 model trained CIFAR-IO, 0.85 hpp for the CONV-10 model trained on CIFAR-100 100, 0.96 bpp for the CONV-4 model trained on MNIST, and 0.83 bpp for the CONV-4 model trained on EMNIST. On the other hand, other baselines that train a dense model, namely SignSGD, TerGGrdd, QSGD, DRIVE, and EDEN, would need to represent each weight with their full precision value, ie.. 32 bpp. This implies that FedPM provides providd around 38.6 improvement in the storage or the communication of the final model. Since FedMask also trains a sparse model, enjoys a similar gain in the final model size requiring 1 hpp across all the models. Due to the stochastic masking procedure and uneven distribution of I's and O's in the binary masks.(eddPM)
up 0. 0.17 hpp improvement over the deterministic procedure in FedMask, which adds up to a large gain due to the huge model size.
We provide additional experimental results with ResNet-18 model on CIFAR-10 and CIFAR-100 datasets in Appendix E. and observe similar improvements over the baselines.
4.2 NON-IID DATA SPLIT AND PARTIAL PARTICIPATION (K= < <N)
This section considers more realistic scenarios, in which the local clients' datasets are generated from slightly different data distributions. We focus on CIFAR-10 with CONV-6, and we compare FedPM against (i) the most promising baselines, which, based on the results of Section 4.1, are DRIVE, EDEN, and QSGD, and (ii) FedMask, as it is the only sparse baseline. To choose the size of each dataset [Pal Dn. for each client n E {I, [L,...,AV N. an integer jn is sampled uniformly from {10, 11...., 100). Then, a coefficient Pn. = - is computed, which represents the size of the local dataset D, as a fraction of the size of the full dataset, i.c., the training set of CIFAR-IO. In this way, highly unbalanced datasets can be generated from the central one. Moreover, since the task is a classification problem, we impose maximum number of different labels, or classes, Cuax, that one client can see. Consequently, clients need cooperation to learn the statistics of other classes' distributions, as the test dataset contains samples from all classes. In addition, partial participation also considered, meaning that at each round, the server uniformly samples a fraction p = N clients to participate in the training round. This is motivated in real-world scenarios by the scarcity of physical communication network resources, which may limit the availability of part of the clients during one round. The maximum number of classes per local datasct is set to Cmax E {2, 4), and the participation ratio is set to E {0.1, 0.2, 0.5, 1}. For p = 1 and p = 0.5, the total number of clients is set to N 10 (and K is equal to 10 and 5, respectively). For p 0.2, we set N 100 (and so K = 20), and for = 0.1, we set N = 50 (and so K = 5), which is the worst scenario among all combinations, given the small amount of information the server can collect the end of each round, When p = 1, for the F FedPM algorithm, we keep the same aggregation strategy exposed in Section 3.1.2 and Figure 2 and we switch the Bayesian aggregation method (see Section 3.2) when there is partial participation, i.c., when P < 1. Indeed, applying the Bayesian aggregation method is revealed to be crucial for achieving good accuracy when p < 1 and data are non-IlI,, obtaining large gain with respect to the simpler version in Section 3.1.2] which resets the Beta priors at each round (or takes the average of the samples, as explained in Section 3.2). We elaborate
K of the
Table I: Average final accuracy to in non-lID data split with Cmax = 4 and 2, and client partic- ipation ratios م {0.1, 0.2, 0.5, 1). for FedPM FedMask, and the strongest baselines in the IID experiments: EDEN, DRIVE, and QSGD. The training duration was set to fum 200 rounds.
Algoritiun
p=1
0.5
p= 0.2
p= 0.1
DRIVE
Vargalik et al. 2021
0.739
0.005
0.632
2 0.000
0.563 1: 0.005
EDEN
0.717 0.006
0.665
0.012
0.565 0.009
0.300
Cpus
QSGD
0.006
0.01100001
0.56711..00
0.399 0.020
FedMaax
2021
0.511 0.044
0.435 0.057
0.434 0.036
0.302 0.004
FedFF Our3)
0.748 0.003
0.720
0.007
0.617
0.021
0.496 :: 0.007
DRIVE
Varcafiik
2021
0.434 0.025
0.376 0.014
0.375
0.015
0:221 0.000
EDEN
Varyalik clair
0.535 0.050
0.461
0.016
0.380
0.015
0,219 0.005
Cros 2
QSGD
Aligarh et al
2017
0.476 = 0.833
0.164
= 0.002
0.375
2: 0.026
0.243 1: 0.014
HolMint 01
21:1
01420 0.028
0.387 0.062
01285
+ 0.040
0.197 0.09)
0.016
0.031
0.372
0.277 0.003
8

---

In this section, we try to answer two questions: (1) Is Bayesian aggregation really necessary? and (2) What is the effect of resetting frequency on the convergence rate and the final accuracy? We do this by analyzing the effect of different resetting frequencies of the Beta priors on the training behavior of FddPM with non-IID data split and partial client participation; and report the results in Figure 4 Hereafter, we denote with y the number of aggregation rounds before resetting the priors. corresponds resetting the priors at every iteration, which is equivalent to the aggregation method presented in Section 3.1.2 On the other extreme, 7 200 indicates that the priors are never reset. seen that y curves fluctuate significantly and never converge to the best accuracy in any setting, while y 200 curves look smoother but converge to the lowest accuracy in all settings. This intuitively makes sense because, as already mentioned in Section 3.2 by increasing the value of % we allow the server consider the information coming from multiple rounds while updating the global parameters. Indeed, with partial participation and non-lID data, a single round's 's updates may convey skewed information, depending on the level of data heterogeneity Cmax. and client participation ratio p. As a rule of thumb for the resetting frequency value, we suggest tuning 7 around the value 1. The rationale behind this is that with uniform client sampling, at least p' rounds are needed to have the non-zero probability to sample from each client once before resetting Published as a conference paper at ICLR 2023
more this observation with ablation study in Section 4.3 We adopt simple heuristic schedule to reset the priors: Reset every 3 rounds when p = 0.5 and = 0.2, and every 10 rounds when 0.1. As expected, the smaller the ratio p. the larger the number of rounds we should wait before resetting the priors to collect more information from a much more diverse pool of clients (see Section 44. for a rule of thumb the resetting frequency).
Table the results with Cmax = 4 and 2. FedPM to outperform all the baselines in every configuration, the Bayesian aggregation allows the server to collect more data before resetting the priors, which is important when clients' data distributions are non-IID, and only a fraction of the clients participate in each round. This strategy can be seen as the FedPM counterpart of decreasing the learning rate (which we applied in the other dense compression based baselines, like DRIVE, EDEN, and QSGD). It seen from Table [ that FedMask (Li et al., 202T) struggling the non- IID case, as applying hard threshold on the scores to binarize the mask does not provide proper way to implement multiple-
aggregation, emphasizing the benefit of the stochastic process in FedPM It is interesting to notice that, especially when Cmax 4, the lower the value of p. the larger the gap between[FedPig and the baselines, corroborating the fact that the Bayesian strategy can better deal with partial participation. Analysis of the communication bitrate is provided in Appendix. E.2
4.3 ABLATION STUDY ON THE BAYESIAN AGGREGATION STRATEGY
For instance, 7
the prior. In practice, we do not need to sample exactly from every client, as enough information is
contained in the updates of the other sampled ones.
Accuracylp 0.1. N K0
Accuracy(p 0,2, 20)
Accuracy = O.S.N K0.K=5)
y-1
Aecurecy
Y-5
0.
03
y=10
200
Mouudds
Rounds
Houndds
Figure 4: Accuracy for different values of 7 the number of rounds before resetting the priors.
5 CONCLUSION
In this work, we introduced Federated Probabilistic Mask Training (FedPM) - communication- efficient FL strategy. FedPM relies on the idea of finding a sparse network in a randomly initialized dense network, which is then sparsified by a collaboratively trained stochastic binary mask. In addition to reducing the communication cost to less than bit per parameter (bpp), FedPM also reaches higher accuracy with faster convergence than the relevant baselines, and can potentially amplify privacy while additionally outputting compressed final model with size less than I bpp. Throughout the manuscript, we highlighted the advantages of having a stochastic mask training approach rather than deterministic one in terms of accuracy, bitrate, and privacy.

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
All the experiments in the paper were performed on publicly available datasets. When we evaluated our strategy, only considered accuracy a measure of performance. However, as pointed out by Hooker et al. (2020), compression methods may disproportionately impact different subgroups of the data. We agree that this may potentially create a fairness issue in all communication-efiee -ffficient federated learning frameworks and deserves more attention from the community.
7 REPRODUCTION STATEMENT
The codebase for this work is open-sourced at http:////t..h..coooo.eoo vantivaniin vanTsik k/ sparse- wando--ettooooeeeeee works All the hyperparameters necessary to reproduce the results in the paper can be found in Appendix D links to them in the manuscript.
We only used publicly available standard datasets and included
8 ACKNOWLEDGEMENT
The authors would like to thank the anonymous reviewers and area chairs who provided valuable feedback; and Zachary Charles, Mahdi Haghifam, Peter Kairouz, and Nicole Mitchell for inspiring discussions. This work was supported in part by a Sony Stanford Graduate Fellowship, National Science Foundation (NSF) award, a Meta research grant, and the European Union under the Italian National Recovery and Resilience Plan (NRRP) of NextGenerationEUU partnership on "Telecom- munications of the Future" (PE0000001 program "RESTART").
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Naman Agarwal, Peter Kairouz, and Ziyu Liu. The skellam mechanism for differentially private federated learning. Advances Neural Information Processing Systems, 34:5052-5064, 2021.
Alham Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In EMNLP 2017: Conference Empirical Methods in Natural Language Processing, pp. 440-445. Association for Computational Linguistics (ACL), 2017.
Maxwell M Aladago and Lorenzo Torresani. Slot machines: Discovering winning combinations of random weights in neural networks. In International Conference on Machine Learning, pp- 163-174. PMLR, 2021.
Hande Alemdar, Vincent Leroy Adrien Prost-Boucle, and Frédéric Pétrot. Ternary neural net- works for resource-efficient Al applications. In International Joint conference on Neural Net- works (IJCNN,, pp. 2547-2554, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Communication-efficeeen SGD via gradient quantization and encoding. Advances Neural In- formation Processing Systems, 30, 2017.
QSGD:
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:1mm5,4:11455 34:17455- 17466, 2021.
Sara Babakniya, Souvik Kundu, Saurav Prakash, Yue Niu, and Salman Avestimehr. Federated sparse training: Lottery aware model compression for resource constrained edge. arXiv preprint arXiv:2208. 13002, 2022.
B. Balle, Barthe, and M. Gaboardi. Privacy amplification by subsampling: tight analyses via couplings and divergences. Advances in neural information processing systems, 2018.
10

---

Published as a conference paper at ICLR 2023
Borja Balle, Peter Kairouz, Brendan McMahan, Om Thakkar, and Abhradeep Guha Thakurta. Pri- vacy amplification via random check-ins. In Advances in Neural Information Processing Systems, 2020.
Leightn Pate Barnes, Huseyin A Inan, Berivan Isik, and Ayfer Özgür. rtop-k: A statistical estima- tion approach to distributed SGD. IEEE Journal on Selected Areas in Information Theory, 1(3): 897-907, 2020.
Andrew Barron, Jorma Rissanen, and Bin Yu. The minimum description length principle in coding and modeling. IEEE transactions on information theory, 44(6):2743-2760, 1998.
Ran Ben Basat, Shay Vargaftik, Amit Portnoy, Gil Einziger, Yaniv Ben-Itzhak, and Michael Mitzenmacher. Quick-fl: Quick unbiased compression for federated learning. arXiv preprint arXiv:2205.13341 2022.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 300.::1338.332, 2013.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569, PMLR, 2018
Sameer Bibikar, Haris Vikalo, Zhangyang Wang, and Xiaohan Chen. Federated dynamic sparse training: Computing less, communicating less, yet learning better. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6080-6088, 2022.
Gregory Cohen, Saced Afshar, Jonathan Tapson, and Andre Van Schaik. EMNIST: Extending
MNIST to handwritten letters. In International Joint Conference on Neural Networks (IJCN), pp. 2921-2926, 2017.
Rong Dai, Li Shen, Fengxiang He, Xinmei Tian, and Dacheng Tao. Dispfl: Towards communication- efficient personalized federated learning via decentralized sparse training. arXiv preprint arXiv:2206.00/88 2022.
Li Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2416)144 2012.
James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning randomly weighted network. In International Conference on Learning Representations, 2020.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265 284. Springer, 2006.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pp. 2468 2479, 2019.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on doi: 10. 10.11099FOCS33299922011
Foundations of Computer Science (FOCS), pp. 954 964, 2022.
00096.
Paulo Abelha Ferreira, Pablo Nascimento da Silva, Vinicius Gottin, Roberto Stelling, and Tiago Calmon. Bayesian signSGD optimizer for federated learning. Advances in Neural Information Processing Systems, 34, 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018
Antonious M. Girgis, Deepesh Data, and Suhas Diggavi. Differentially private federated learning with shuffling and client samplin... In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 538-343, 2021. doi: 10. 04.10999STT4451142222.991111 201.2.9999..99

---

Published as a conference paper at ICLR 2023
Farzin Haddadpour, Belhal Karimi, Ping Li, and Xiaoyun Li. Fedsketch: Communicationn-ffinn effiicient and private federated learning via sketching. arXiv preprint arXiv:2008.04973, 2020.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Feder- ated learning with compression: Unified analysis and sharp guarantees. In International Confer- on Artificial Intelligence and Statistics, pp. 2350-2355 PMLR, 2021.
Burak Hasircioglu and Deniz Gunduz. Privacy amplification via random participation in feder- ated learning. 2022. doi: 10.4850/ARXIIV.205.05555 URL htttt::///axii....ttt//
2205. 01556
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpass- ing human-level performance on imagenet classification. In JEEE International Conference on Computer Vision (ICCV), pp. 1026-1034, 2015. doi: 10.1 109/CCC.20155.233..
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Sara Hooker, Nyalleng Moorosi, Gregory Clark, Samy Bengio, and Emily Denton. Characterising bias in compressed models. arXiv preprint arXiv:2010.03058, 2020.
Jacob Imola and Kamalika Chaudhuri. Privacy amplification via bernoulli sampling. arXiv preprint arXiv:2105.10520 2021.
Berivan Isik, Tsachy Weissman, and Albert No. An information -ooommtiin-thhoreticc justification for model pruning. In International Conference on Artificial Intelligence and Statistics, pp. 3821-3846. PMLR, 2022.
Shaoxiong Ji, Wenqi Jiang. Anwar Walid, and Xue Li. Dynamic sampling and selective masking for communication-efficiee. federated learning. arXiv preprint arXiv:2003. 096003, 2020.
Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K. Leung, and Leandros Tassiulas. Model pruning enables efficient federated learning on edge devices. IEEE Transactions on Neural Networks and Learning Systems, April 2022.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-200 2021.
Jakub Koneěný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05443 2016.
Raphail Krichevsky and Victor Trofimov. The performance of universal encoding. IEEE Transac- fions on Information Theory, 1992)79 1981.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ang Li. Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. Lotteryfl: Personalized and communication--fee efficiient federated learning with lottery ticket hypothesis on non-iid datasets. arXiv preprint arXiv:2008.033: 2020.
Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. Fedmask: Joint computa- tion and coamuuication-effiitii personalized federated learning via heterogeneous masking. In Proceedings of the 19th ACM Conference on Embedded Networked Sensor Systems, pp. 42-55, 2021.
Sheng Lin, Chenghong Wang, Hongjia Li, Jieren Deng, Yanzhi Wang, and Caiwen Ding. Esmfl: Efficient and secure models for federated learning. arXiv preprint 200i::0009001666) 2020.
12

---

Published as a conference paper at ICLR 2023
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018.
Yang Liu, Yi Zhao, Guangmeng Zhou, and Ke Xu. Fedprune: Personalized and communication- efficient federated learning on non-iid data. In International Conference on Neural Information Processing, pp. 430-437. Springer, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicationn-cficienttt learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 2273-1282, PMLR, 2017a.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:/710.006: 2017b.
Ilya Mironov. Rényi differential privacy. In IEEE 30th computer security foundations symposium (CSF), pp. 263-275. IEEE, 2017.
Nicole Mitchell, Johannes Ballé, Zachary Charles, and Jakub Konečný. Optimizing the communication-accuacyy trade-off in federated learning with rate-distortion theory. arXiv preprint arXiv:2201.02664, 2022.
Amirkeivan Mohtashami, Martin Jaggi, and Sebastian Stich. Masked training of neural networks with partial gradients. In International Conference Artificial Intelligence and Statisties, pp- 5876-5890. PMLR, 2022.
Hamid Mozaffari, Virat Shejwalkar, and Amir Houmansadr. Fri: Federated rank learning. arXiv preprint arXiv:2110.043:: 2021.
Muhammad Tahir Munir, Muhammad Mustansar Saeed, Mahad Ali, Zafar Ayyub Qazi, and Ihsan Ayyub Qazi. Fedprune: Towards inclusive federated learning. arXiv preprint arXiv:21 14205, 2021.
Emre Ozfatura, Kerem Ozfatura, and Deniz Gündüz. Time-correlated sparsification for communication-efficieeett federated learning. In IEEE International Symposium on Information Theory (ISIT), pp. 461-466. IEEE, 2021.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic over-paraaeteriizaion is sufficient. Advances in Neural Information Processing Systems, 33:2599-26100 2020.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in randomly weighted neural network? In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 11893-1 1902, 2020.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-effiiiee federated learning method with periodic averaging and quan- tization. In International Conference on Artificial Intelligence and Statistics, pp. 2021-2031.
PMLR. 2020.
Jorma Rissanen and Glen Langdon. Arithmetic coding. IBM Journal of research and development, 1392):149-162, 1979.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication-effiieennn federated learning with sketching, In International Conference on Machine Learning, pp. 8253-8265. PMLR, 2020.
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojeiech Samek. Robust and communication-effiiine federated learning from non-iid data. JEEE transactions on neural ner- works and learning systems, 31 3100):340033413 2019.
Sejin Seo, Seung- Woo Ko, Jihong Park, Seong- LLun Kim, and Mehdi Bennis. Communication- efficient and personalized federated lottery ticket learning. In IEEE 22nd International Workshop Signal Processing Advances in Wireless Communications (SPAWC), pp. 581-585. IEFE, 2021.
13

---

Published as a conference paper at ICLR 2023
Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. International conference on machine learning, pp- 3329-3337, PMLR, 2017.
Anish K Vallapuram, Pengyuan Zhou, Young D Kwon, Lik Hang Lee, Hengwei Xu, and Pan Hui. Hidenseek: Federated lottery ticket via server-side pruning and sign supermask. arXiv preprint 04X1::2206.04385 2022.
Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. Drive: one-bit distributed mean estimation. Advances in Neural Information Processing Systems, 34:362-377, 2021.
Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben Itzhak, and Michael Mitzemmacher. Eden: Communication--ffeccent and robust distributed mean estimation for fed- erated learning. In International Conference on Machine Learning, pp. 21984-22014. PMLR, 2022.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.
Hongyi Wang. Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication--fficiie learning via atomic sparsification. Advances in Neural Information Processing Systems, 31, 2018.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled renyi differential pri- vacy and analytical moments accountant. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statis- tics, volume 89 of Proceedings of Machine Learning Research, pp. 1226 1235. PMLR, 16-18 Apr 2019.
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terggad: Ternary gradients to reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017.
Sixing Yu, Phuong Nguyen, Ali Anwar, and Ali Jannesari. Adaptive dynamic pruning for non-iid federated learning. arXiv preprint urXiv:2106.06921, 2021.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
14

---

Published as a conference paper at ICLR 2023
A FedPM ALGORITHM
We provide the pseudocode for FedPM in Algorithms T and 2
In Algorithm the prior resetting
scheduling policy is controlled by the procedure ResPrion(t), which may depend on quantities other than the round number such as loss.
Algorithm FedPM
Hyperparameters: learning rate 7), minibatch size B, number of local iterations т. Inputs: local datasets D,, .
Output:
random seed SEED and binary mask parameters m K
At the server, initialize random network with weight vector wiit E R using a random seed SEED, and broadcast it to the clients.
At the server, initialize the random score vector 89.0 E Rdd, and compute 0o.0 Sigmoid(s*.0) At the server, initialize Beta priors a = B9.00 Ao- for 1, do
Sample subset K., (1,...,.N) of [Ca K clients without replacement. On Client Nodes: for & K, do
Receive 08.1-1 from the server and set ght = Sigmoid Sigmoid"((Os.-11))
for 1,.............. ...., do
g <- Sig
Sample binary mask m Bern(Ok..).
ki +- m h1 ④ agil
grad ah t B EB
Lb=1 Ve(ib";;;) {B
R uniformly chosen from Dj
shr +- k.
grad,
end for
ghf +- Sigmoid(sf
Sample binary mask ki (ek)()
Send the arithmetic coded binary mask m kit to the server.
end for
On the Server Node:
Receive m f 's from K client nodes.
0 = BayesAgg( fm Jac, t) // See Algorithm Broadcast fa.t to all client nodes.
end for
Sample the final binary mask linal Generate the final model: linil +- m linal O wint
Bern (OsT))
Algorithm BayesAgg.
Inputs:
clients' updates (m* heeK,, and round number t global probability mask 69.7
Output:
if ResPriors(t) then a9.2-1 = -0.1-11= = Au
end
Compute me8 EkEK, m.k.
0.9.1 9.1-1 m 983.!
3 3 + K m..
09.1
Return 6a.t
15

---

Published as a conference paper at ICLR 2023
B PROOF OF THE UPPER BOUND ON THE ESTIMATION ERROR
We now provide proof of the upper bound on the estimation error in Eq. 2 Recall that our true mean is Ouit LxEx. @hi whereas estimate is Po.t 1 ΣkER. m where m
Bern ( Then we can compute the error as
20.
( (0g.) - 27
E (e VkeK. [110*
03.
E M
N Bemm( of WKEK.
(5)
E M Bem( ( vkEK,
Σ (M...
(6)
K
REK,
d
27
(Ar - .f/it))
E M of Bem(0 WhEK,
(7)
K2
kEK
(M 04.00
E M Bem(0 ( WhEKs
K
LEEK
d
"em Bem(ohin [CA - O4/0g2)
(9)
K2
1= KEK,
d
L M " BemLOo IKA,, 1110,,,,,,,,,,, -(0%%192)
(10)
KEK,
(B (0):))2)
(11)
K2
i=1 keK.
$ 4K
(12)
From (5) to (6), we use the definition of gø.t (8), the fact that " ">Bmm( vkek. [M 0.0 O: and M 0f and M - 0/'
K Σx_ m and g = 1 Ex= 8h.t. From (7)
K
are independent for + le [K]. Finally, the inequality in (8) follows from gf [0, for all k E [K].
C PRIVACY AMPLIFICATION AND BIAS CORRECTION
Differential privacy (DP) guarantees that the probability of an outcome of an algorithm that runs on client data does not change much by single client's data. This is typically ensured via injecting noise to a function of the client data at a particular step in the algorithm with some utility loss in the application. While there have been many DDP strategies developed for For and deep learning (Abadi) al.) 2016; McMahan et al.) 2017b] Agarwal al. 2021, Andrew et al. (021). these strategies typically suffer from severe performance degradation due to noise injection. To make DP practical, researchers have explored certain randomization mechanisms that amplify the privacy guarantee. When these mechanisms are parts of the FL framework, such as sampling (data (Balle et al. 2018
Wang et 2019) device (Balle et 2020 Girgis al. 202 (Hasiriioglu & Gunduz 2022
and shuffling (Erlingsson et al. 2019 Feldman et al. (022). the amplification comes for free. This helpful because the overall process can meet stronger privacy guarantee without increasing the
noise level. FedPM promises one such amplification due to the stochastic Bernoulli sampling step. We first revisit the definitions of differential privacy (Dwork al.) (2066). Rényi divergence, and Rényi differential privacy (Mironov) (001)); and then present the amplification result.
Definition 1. [Adjacent Datasets] Two datasets D, D' E are called adjacent if they differ in at data sample.
16

---

Published as a conference paper at ICLR 2023
Definition 2. [(c, 6)-DP A randomized mechanism D R offers (..8)-differentill privacy if for any adjacent D, D' E DD and S C R
Pr(f(D) E 8] PPiFFD E ES]
Definition 3. [Rényi Divergence] For two probability distributions P and defined over R, the Rényi divergence of order a > 1 is
P(x) Q(x)
Da (PlQ)) = log EanQ
Definition 4. [(,, c)-RDP A randomized mechanism f 'D - R offers c-Rényi differential privacy of order (or in short (a,P) for any adjacent D, D' DD it holds that
Do(I(D)IL(D))) 6.
In particular, Imola & Chaudhuri 2021 have shown that when sample M E 10, from already privatized vector O E c. c.e. where 0 < < 0.5, is released to a third party (instead of 0 itself), the privacy is amplified under some conditions. More precisely, when there is an (a, Rényi Differential Privacy mechanism (Mironov (017) that privatizes O E [c, - c)3, releasing sample from (ern( yields an improved privacy budget (the smaller c, the better the privacy): Camp I min (r.d-rac)) Here, ro (p) is the binary symmetric Rényi divergence function defined as (p) - log (1º(1 p)=-a (1 p)))+=)). Notice that FedPM already involves this Bernoulli sampling step in the communication protocol and in the forward pass m Bern (0h.t) However, the d term in the upper bound limits the amplification for large model sizes. We believe worth exploring a tighter upper bound on <amp to enjoy privacy amplification in |FddM with practical models. Nonetheless, in Appendix C we demonstrate the impact of this amplification on a distributed mean estimation problem, described in Figure 2 where the goal is to estimate the true mean of the probability masks K Σ 0 under communication and privacy constraints. We also provide a bias correction mechanism, specific our scheme in Figure in Appendix C that mitigates the bias due to the DP mechanism and reduces the estimation error.
Now, suppose that have (a, e RDDD algorithm f that outputs privatized 0h E 1c cf with 0 < < 0.5, using local client data Dx. As summarized in Figure 5 we are interested in what happens when instead of releasing 0h fDDx), the client releases Bernoulli sample from it: m" {0, _]d ~ Bern(@*). We already explained the advantages in terms of communication bitrate, estimation error, unbiasedness throughout the manuscript; however, this approach also amplifies the privacy guarantees, meaning that it makes the overall privacy budget smaller camp S e. Quantita- tively, [mola & Chaudhuri (202T) showed that after the Bernoulli sampling, the privacy budget of the overall process is
Camp S min (e, dr)
where (.) is the Rényi divergence of the binary symmetric function. More precisely, consider P. Q random variables with support on [21 C and let p = Pr(P 21), 1 - pp = Pr(Q = 21). Then the Rényi divergence is defined as
1 - log (1 p)) 1-a + +1 p'-)p'--))
(p(p) - (.
a
Notice that Maat(FedPMaaleeaa involves this Bernoulli sampling step the communication protocol and in the forward pass m.. (ern( This implies FedPM improves the privacy guarantee without changing the privacy mechanism - e.g. without increasing the injected noise level. How- ever, the d term in the upper bound limits the amplification for large model sizes. We believe it is worth exploring a tighter upper bound on Camp to enjoy privacy amplification in FFFedP with prac- tical models. Nonetheless, estimation problem, described Figure where the probability masks l E [c, 1c.1-00 cc cj are a func- tion of client data DR; and are first corrupted by Gaussian noise, and then clipped the range
demonstrate the impact of this amplification
distributed mean
17

---

Published as a conference paper at ICLR 2023
1 cl.. Our goal is, before, to estimate the true mean 0 K ΣbEK, O by averaging the sampled binary masks, i.e., 0 * EKEK, m Differently from our previous experiments, have privacy constraints now, meaning that want to guarantee (c, 6)-DP by injecting a Gaussian noise with variance x² 21 (1.25/6)42 with small 6, where R Nिz and A₂ is the fz-sensitivity of the probability masks (in our case A = (1 dd). We transfer the above amplification results in RDP to DP using the well-known relation:
Remark C.I. Mironov 2017) showed that if f is an (ax, R)-RDP mechanism, it also satisfies (e +
log 1/6 6)-DP for any 0 < 8 <. 1.
Server Estimate
True Mean
6o!
gat
gks
K
K
m 1 E {o, 12
m 3 E 00 10,13
m
k {0, 13dd
Bern ())
Bern (2.t)
Bern (kxtt
g+dt
g
@K
1)
")
Figure 5: Distributed mean estimation scheme in FedPM modified for differential privacy.
Since clipping after the noise addition step would lead bias in the estimated mean, we work out bias correction mechanism. We denote with 0 one general parameter at client l: for one parameter, with 0 its noisy version, and with = clip(f) its clipped version. Specifically, if = 0 + is the noisy version of the parameter, where (0, o²), then
0 if cso+n51-c
clip(0) = 1-c, c, if 0+1>1-c
(13)
C, if 0+n<c.
We now compute E AM where .² Bern()), to analyze the bias where M Be) First of all, notice that
M E [M] E MM
0.
f IE 1 p) f(o)dp= L' pf(p)dp= =01]
E M
18

---

Published as a conference paper at ICLR 2023
And now compute the mean of the clipped parameter
E
0
pf(d)d
clip(0 + d))(())
1-c-8
1 1-00- (1- f())dn
c. e-f(r)d +
(0+ (0))))f()ddn f(n)dn
f(n)dn + 1 2-c-0
= cb,(c- 0) + c-0
nf(n)dn + (1 - c) o (1 81)
Jc-0
-0
01-0-002
((--0) 2nd
cb 0) + [ c- 0) 2 (c -0]]
20
+
2T
+ (1 c) c) (1 - 6, c- -))
-
= =1- 0 1+ c o (1 - c-
- 0) + 0 -0)) + -
2(c 2(c-0)
-1
0)
2T
where o (.) is the cumulative distribution function of a Gaussian random variable with standard deviation o, and zero mean. We use this relation correct the bias in θ. In practice, to adopt the bias-correction strategy, sample the function IE 0 which is function of the true parameter 0, noise standard deviation a, and clipping parameter c, at Q different points 2 21.... TQ. i.c., different values for the uncorrupted 0, and store the values in table. Indeed, the values a and are set at the beginning of the training process, secretly shared among the participants, and never modified.
Then, once the server computes an estimate for 0, it corrects by finding the closest outputs of TE in the stored table, and inverts the map by choosing the corresponding F;, i.e., the original A.
We conduct our experiments with N = 100 clients, each having independent probability masks with dimension d 5 and range [0.2, 0.8], i.e., 0 E: [0.2, 0.8]5. Figure shows the estimation error 10 0 under no noise injection case (i.e. no DP) with the black line. Recall that we want to reach smaller estimation error and smaller (i.e., stronger privacy guarantee). The red curve corresponds to the vs. estimation error behavior if Bernoulli sampling did not amplify the privacy. The blue curve shows the amplified (i.e. 6amp < e) vs. estimation error behavior, and it overlaps with the red curve for values smaller than d. (c) (c) ie., Comp e. However, notice that the blue line never reaches e's higher than this value due to amplification, while enjoying smaller estimation errors that the red curve can only achieve with very large 6. This shows the promise of FedPM in having better privacy-accuracy performance than most baselines that do not have amplification. Finally, the green curve shows that bias correction improves this performance further even with d (c( = 8.96 by achieving lower estimation errors with the same
8.96, where there is no privacy amplification,
D ADDITIONAL EXPERIMENTAL DETAILS
In Table 2 we provide the architectures for all the models used in our experiments. Clients per- formed local epochs with batch size of 128 and local learning rate of 0.1 in all the experiments. Notice that there is no server learning rate in FedPM instead, we tune the prior resetting sched- ule Bayesian aggregation for the experiments in Section 4.2
We conducted our experiments on internal cluster server, using GPU per one run.
NVIDIA Titan X GPUs
In the non-lID and partial participation experiments in Section 4.2 to distill the final model, we may apply both stochastic sampling, during training, hard-threshold method, similar to the one adopted FedMask (Li et al., 202T). In the latter, binary mask coefficient m; is set to 0, > Ouss and 0 otherwise. For all experiments but one, when aus [0.4, 0.6), the thresholding test accuracy is always higher than the sampling method, and so we use the threshold method. However, in the extreme case Cmax = 2 and p 0.1, the optimal values for Omax were in [0.2, 0.4) and (0.6, 0.8)
19

---

Published as a conference paper at ICLR 2023
No DP (baseline)
(c, 6)-DP
(Camp. 8)-DP
40
(Camp, 8)-DP bias correction
30
20
0.0000
0,0002
0.0004
0.0006
0.000S
Estimation error
Figure 6: The effect of privacy amplification and bias correction in the privacy budget (c) esti- mation error behavior. Comparing red and blue curves, we see that we can reach small estimation errors without increasing thanks the amplification (see the vertical blue line at low estimation error.). While the red curve and blue curve overlap for < d Ta (c) = 8.96, in that regime, we benefit from our bias correction strategy to reach lower error.
Table 2: Architectures for CONV-4, CONV-6, and CONV-10 models used in the experiments.
Model
CONV-4
CONV-6
CONV-10
64, 64, pool
128, 128, pool
64, 64, pool 128, 128, pool 256, 256, pool
256, 256, pool
Convolutional
64, 64, pool 128, 128. pool
512, 512, pool
Layers
1024, 1024, pool
Fully-Connected Layers
256, 10
256, 256, 10
256, 256, 100
all experiments, probably due the high randomness given by the highly heterogeneous scenario. Consequently, for the last experiment, we just adopt the stochastic sampling strategy to evaluate the model, as further optimizing the Oubs means adapting to the test dataset, which may corrupt the ability of the model to generalize.
E ADDITIONAL EXPERIMENTAL RESULTS
E. ADDITIONAL EXPERIMENTS ON RESNET ARCHITECTURES
In this section, we provide additional experimental results with ResNet-18 (He et al., 2016) on CIFAR-10 and and
CIFAR-100 datasets. For these experiments, focus IID data distribution and the case when all the clients participate in the training at each round. We use the same hyperparameters from Section 4. We provide the details of the ResNet- 18 architecture in TableBbeloo..
Figures 7 and show the results on CIFAR-10 and CIFAR-100 datasets, respectively. is seen that FedPM outperfors all the baselines in terms of accuracy. Although DRIVE and EDEN require
20

---

Published as a conference paper at ICLR 2023
Table ResNet- 18 architecture.
Name convl
Component
3 x 3 conv, 64 filters. stride 1, BatchNorm
3 x conv, 64 filters
Residual Block
3 x conv, filters
x
3 x 3 conv, 128 filters
Residual Block
x 3 conv, 128 filters
x
x 3 conv, 256 filters
Residual Block
x 3 conv, 256 filters
x 3 conv, 512 filters 3 x 3 conv, 512 filters
Residual Block
Output Layer
4 X
average pool stride I, fully-connneted, softmax
Accuracy (resnet18-cifar10)
Bitrate (bits per parameter)
Average Bitrate (resnet18-cifar10)
0.8
FedPM(ours)
14
SignSGD
0.6
Accuracy
12
TernGrad
QSGD
0.4
DRIVE
0.3
0.8
EDEN
0.6
FedMask
0.1
50
100
150
200
250
300
350
400
50
100
150
200
250
300
350
400
Rounds
Rounds
Figure 7: Accuracy and bitrate comparison of FedPM with baselines SignSGD (Bernstein al.
2018), TemGrad (Wen et al., 2017), QSGD (Alistarh et al. 2017), DRIVE (Vargaftik et al. 2021 EDEN (Vargaftik al. 2022). and FedMask (Li al. 2021 with ResNet-18 CIFAR-I0.
Server Test Accuracy (resnet18-cifa1100
Bitrate (bits per parameter)
Average Bitrate (resnet18-cifar100
FedPM(ours)
044
1.4
SignSGD
Accuracy
12
TernGrad
QSGD
1.0
0.2
DRIVE
EDEN
FedMask
0.
200 Rounds
Rounds
Accuracy and bitrate comparison of FedPM with baselines SignSGD (Bersstein et al, 2018 TemGGad (Wen et al., (017)) QSGD (Alistarh et al. 2017), DRIVE (Vargaftik et al. 2021] EDEN (Vargaftik et al. 2022), and FedMask (Li al. 2021) with ResNet-18 on CIFAR-T00.
Figure
approximately 0.1 smaller bitrates than FedPM they also reach lower accuracy. In summary, the advantages FFFFeM discussed the main manuscript carry over to ResNet- 18 model as well.
E.2 BITRATE CONSIDERATIONS ON NON-IID DATA
now report the communication bitrate considerations on the non-IID data split experiments de- scribed in Section 4.2 Table 4 reports the average bitrate needed by different algorithms over the whole training process when Cmux = 4 and Cmax = By simply multiplying the obtained average bitrate by the total number of rounds tmax 200, obtain the total number of bits element in the global probability mask needs to converge to its final value. indicating the total amount of information communicated during the training process.
21

---

Published as a conference paper at ICLR 2023
We first observe that both DRIVE and EDEN consume almost the amount of bits matter the system configuration and round number (very small variance). and is instead model dependent (see Figure 3). On the contrary, FedPM and QSGD report higher bitrate variability,, the training phase and system setting. As already observed in Section 4.1] FedMask balances almost uniformly the binary updates, leading to bitrate that is basically fixed to 1. For both Cmax = 4 and
depends both
Cmax = 2. FedePMyyyssdds the smallest bitrate when 1, whereas for the other scenarios, EDEN and DRIVE are slightly more efficient. We argue that this motivated by the fact that, the learning task becomes harder due to the high system heterogeneity, all the models struggle to converge to good and stable solutions, which means that FedPM] still uncertain about the weights' importance probabilities 0, setting many of them close to 0.5. However, we think that this may be useful feature FedPM to quantify its internal uncertainty, which we will further analyze.
Algorithm
p
0.5
0.2
p 0.1
DRIVE Vargaftik
2021
0.885
10
0.885 +
4
0.885
0.885 10
BDEN
Vargalik al.
0.885 10
0.885 + 10-4
0.885 8. 10
0.
Canaa
QSGD
Alisarr
0.027
0.923-0.000
1.188 0.034
0.01
FedMask (La
2021
3- 10
1.000 8-
+.000
6-000+6110-
F FedPP Uuns)
0.863 0.077
0.912 :: 0.056
0.965 0.0000812
0.996 0.003
DRIVE
Vargaftik
2021
0.885 10
0.885
2.
0.885 7.
0.885 2.
EDEN
Vargaftik
2022
0.885 +: 1-10-
0.885 + 10-5
0.885 - 6
0.885
7-1--
Finax
QSGD
Alistara et al.
2017
1.230 0.043
1.234 0.038
1.100 0.01
1.082 =002=0000 0.01
FodMask (Li ct al.
2021
1.000 = 2-1066
1.000 2 10-9
1,000 = 10
1.000 2- 10-7
FedPY (Our))
0.868 + 0.076
0.904 0.003
0.980 + 0.014
0.997 + 0.01
Table 4: Average bitrate =o over the whole training process in non-lID data split with Cmax =
and Cmax 2, and partial participation with ratios p {0.11 0.5, 1}. for [FedMM] FedMask, and the strongest baselines in the IID experiments: EDEN, DRIVE, and QSGD. The training duration was set to mmxx 200 rounds.
To conclude the analysis, we also report FedPM bpp for the final model, which an indication of the average number of bits needed per one parameter of the model. In the case of Cmax = 4. the final model sizes are 0.79 bpp. 0.834 bpp, and 0.99 bpp, when p {0.1, 0.5, 1}, respectively. When Cmax = 2, the final model sizes are 0.8 bpp. 0.817 bpp, and 0.992 bpp. Consequently, at the end of the training process, FedPM] the most efficient option, as already observed in Section 4.1
22


Reviews:
[{"review_id": "qjKm4OqF_D", "reviewer": "Reviewer_19LP", "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": "", "summary_of_the_paper": "The paper proposes a new approach to communication efficient federated learning. They keep the weights of the model fixed after random initialization via a SEED. and then only train the probabilistic mask over the model in collaboration with all the clients. They reduce the communication of requirement to less1bpp during model upload from clients to server. I have a couple of questions for the authors, \n\n\n1. The paper argues that they reduce the communication cost to less than 1bpp every round. However, there are two communication steps in each round: server to clients in before each round and clients to server. While in the second step the communication is less than 1bpp as instead of communicating the masks, clients communicate a sample from the probabilistic mask, as per the paper ( algorithm line “Receive..”, section 3.1.1 first line), clients receive the actual probability mask  (not a sample)  from the server. Then the total cost of communicating 2xmodel_size in usual FL is reduced to only (model_size (download) + mask (upload)). Are we assuming large discrepancies in download and upload bitrates ? \n\n2. If the above assumption is incorrect, then the comparison baselines which were chosen to be  1bpp should also be revised and compared with baselines with larger communication footprint including naive FL which has 2xmodel_size communication.\n\n3. In section 3.3, paper mentions that they use a discrete support for P_w for improving inference storage cost. However if the final weights are ternary, we can eliminate the managing the mask and directly use this for better communication ( at-least client to server communication) . The paradigm would be as follows, each maintains the floating-point models \\theta_i, the final weights are used after applying an activation like tanh. Then while communicating the model to server, you sample from this tanh(theta) to have a support of {-1, 0, 1} (you can consider the factor of sigma separately).  I am curious what the authors think about this.\n\n", "summary_of_the_review": "The major concern for me is that I am not sure if communication is really being reduced. While volume of upload data is surely reduced, the volume of download data is clearly not. I would like to understand the rationale behind this and if i am missing something. This is the basis of my current score.\n\n[post rebuttal] The authors have sufficiently addressed my concerns. i am raising my score.", "strength_and_weaknesses": "[strength]\n1. The approach is novel and unexplored. \n2. the problem being tackled is important \n3. paper is well written\n[weaknesses]\n1. See the points 1-2 above", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "JP6TJimpuF", "reviewer": "Reviewer_EaNE", "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": "", "summary_of_the_paper": "**UPDATE**  \nI thank the authors for providing an extensive response. I carefully read it and discussed with the other reviewers. I'm glad the authors clarified their major design choices and supported them with new experiments. One issue that remains is that of limited evaluations, but with the extra support added in the new version of the paper, I feel more confident that the proposed methodology will generalize to other setups.\n\n---------\nThis paper studies communication-efficient federated learning with random sparsification of the network weights. The main idea of the work is to use the lottery ticket hypothesis and try to find a good subnetwork by estimating a sparsifying mask. The mask parameterized by a vector of probabilities $\\theta$, which, in turn, are estimated using a score mask $s$, whose softmax gives us $\\theta$. Moreover, the authors use multiple clients that run gradient descent to estimate the best mask and then communicate only the binary vector produced randomly from the local estimate. By receiving multiple random masks, the authors build a Bayesian estimator to produce a global model.", "summary_of_the_review": "While the work clearly explains the points that are novel, they do not seem justified or derived in an intuitive manner. The proposed modifications to prior work are somewhat arbitrary and do not follow a rigorous mathematical derivation or empirical evaluation of different options. While the experiments show that the resulting method performs better on a number of problems, it is not apparent that the same improvement would hold universally and where exactly the improvement comes from. For instance, the method converged to better test accuracy on conv10-cifar100, but why it is not explained why it is so.", "strength_and_weaknesses": "The main strength of this work is in the presented empirical improvements on the considered benchmarks. The proposed method is shown to outperform all competitors both in terms of test accuracy and communication efficiency.\n\nWhat makes me concerned is the way the method was derived and studied. Most of the ideas do not look well-motivated. For instance, the authors explain that the mask $\\theta$ cannot be used with regularization because it may lead to a performance drop, so they instead use softmax. However, it is not apparent to me why there would be a performance drop with regularization but no performance drop with score mask. In the majority of cases, I think that an ablation study is required to show that the made choices were the right ones. As of now, the paper just selects a set of ideas that are not justified using theory and then proceed to study the empirical behaviour of the resulting method. I am left with the feeling that I do not understand why the method performs well and if it will generalize to other problems. This is especially troubling since the evaluations are limited to simple problems (CIFAR-10/100, EMNIST, small networks).", "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": "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": "IWvs0kQChM", "reviewer": "Reviewer_Un54", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "", "summary_of_the_paper": "The paper proposes a combination of ideas and methods to enable low-bit-width communication in federated learning. \nThe authors combine the idea of learning a sparse sub-network of a randomly initialized model through a binary mask with a stochastic sampling scheme of said mask to communicate with the server and further a bayesian aggregation scheme. These algorithms exist in the literature but not applied successfully to FL as presented here. \n\n", "summary_of_the_review": "Very interesting paper with a convincing story. The experimental section could be improved. I am happy to raise my score should the authors provide experiments with more modern network architectures and FL settings with a larger number of clients. \n\n-- post rebuttal -- \nI have read the rebuttal and revised manuscript. The authors have addressed my concerns and I have raised my score", "strength_and_weaknesses": "This paper's strength lie in the excellent exposition and description of the method. The paper is very pleasant to read, easy to follow and written in a convincing way. \n\nThe weakness of the paper lies in the experimental evaluation. The model & data-set combinations are not up-to-date with the literature. Generally speaking, (wide) ResNet or more edge-device friendly models would be more realistic than these VGG-type models. Especially with respect to the compression angle, I would like to understand how wider networks are influenced by the subnet-selection problem in the federated setting - also I'm curious if convolutional-only models (such as ResNets) perform equally well. \nThe data-set setting does consider partial participation and heterogeneity through label-skew and differing dataset-sizes, which is highly commendable. At the same time, most FL papers consider settings with >50 clients, such as Femnist (3.6k clients) or even NLP tasks on the Stackoverflow dataset with approx 340k clients. Alternatively, I'd be curious to understand how, staying with the experimental theme of the paper, TinyImagenet (64x64) split across several hundred clients performs here. \nThat being said, the existing experiments do convince me of the value of the proposed algorithm.\n\nIn terms of ablations, I would have liked the authors to provide more guidance on the resetting of the server-side $\\alpha$ and $\\beta$. What is happening to require the resetting in the first place? How does the frequency of resets influence the convergence? And how does non-iid data influence this behaviour? This heuristic seemingly is very important to good results, so I am curious to learn more. Please provide more detail on your statement: \"... design an improved aggregation strategy with a Bayesian approach so that the previous masks at the server are not hard replaced – a useful strategy specifically in unbalanced non-IID splits\"\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "CoMH56MSTFA", "reviewer": "Reviewer_iZTn", "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": "", "summary_of_the_paper": "This work proposes FedPM, a scheme for communication (and as a byproduct, computation) efficient federated learning. Instead of training the neural network weights with, e.g., FedAvg, the authors propose to freeze the network at its random initialisation and then only train a *binary* mask over the weights, to prune some connections, in a federated fashion. The benefit of this approach is that the client-to-server communication now becomes much cheaper, due to communicating (potentially encoded) binary vectors instead of full precision weights. To train the binary mask, the authors propose to employ a distribution over masks, the probabilities of which are a server side parameter. On each round, this distribution is communicated to each client, which then optimises it locally on their own data by 1) sampling binary masks according to this probability distribution, 2) sparsifying the weight according to the sampled mask, 3) doing the forward pass with the sparsified network and 4) approximating the gradient of the loss with respect to the parameters of the probability distribution with the straight-through estimator [1](although the authors do not explicitly mention it). The reduction in the upload costs comes from having each client communicate to the server a random sample from the locally training distribution over the masks (which is binary) instead of the actual distribution over the masks. The download cost of FedPM is the same as FedAvg (since the probabilities are real values and one for each weight). To aggregate the binary masks at the server, the authors propose to use the Bayesian aggregation from Ferreira et. al. Finally, to accommodate for computationally fast inference, the authors also propose to randomly initialise the weights to be binary with a specific scaling that leads to better behaved gradients. \n\n[1] Bengio et al. Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation, 2013", "summary_of_the_review": "Given the aforementioned comments, I am leaning towards not recommending acceptance of this work; the technical novelty is small (as it is a combination of prior ideas) and the empirical novelty, while appreciated, is not enough for me to push this work over the acceptance threshold.\n", "strength_and_weaknesses": "Strengths\n- Simple method\n- Good results\n\nWeaknesses\n- Limited technical novelty\n- Some clarity concerns ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster