FSL: Federated Supermask Learning
Authors: Hamid Mozaffari
Virat Shejwalkar
Amir Houmansadr
Venue: ICLR 2022 Submitted (2022)
Keywords: Collaborative learning
robustness
poisoning attacks
communication efficiency

Abstract: Federated learning (FL) allows multiple clients with (private) data to collaboratively train a common machine learning model without sharing their private training data. In-the-wild deployment of FL faces two major hurdles: robustness to poisoning attacks and communication efficiency. To address these concurrently, we propose Federated Supermask Learning (FSL). FSL server trains a global subnetwork within a randomly initialized neural network by aggregating local subnetworks of all collaborating clients. FSL clients share local subnetworks in the form of rankings of network edges; more useful edges have higher ranks. By sharing integer rankings, instead of float weights, FSL restricts the space available to craft effective poisoning updates, and by sharing subnetworks, FSL reduces the communication cost of training. We show theoretically and empirically that FSL is robust by design and also significantly communication efficient; all this without compromising clients' privacy. Our experiments demonstrate the superiority of FSL in real-world FL settings; in particular, (1) FSL achieves similar performances as state-of-the-art FedAvg with significantly lower communication costs: for CIFAR10, FSL achieves same performance as Federated Averaging while reducing communication cost by $\sim35\%$. (2) FSL is substantially more robust to poisoning attacks than state-of-the-art robust aggregation algorithms.

Under review as a conference paper at ICLR 2022
FSL: FEDERATED SUPERMASK LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) allows multiple clients with (private) data collabora- tively train a common machine learning model without sharing their private train- ing data. In-the-wild deployment of FL faces two major hurdles: robustness poisoning attacks and communication efficiency. To address these concurrently, we propose Federated Supermask Learning (FSL). FSL server trains a global sub- network within a randomly initialized neural network by aggregating local subnet- works of all collaborating clients. FSL clients share local subnetworks in the form of rankings of network edges; more useful edges have higher ranks. By shar- ing integer rankings, instead of float weights, FSL restricts the space available to craft effective poisoning updates, and by sharing subnetworks, FSL reduces the communication cost training. We show theoretically and empirically that FSL is robust by design and also significantly communication efficient; all this with- out compromising clients' privacy. Our experiments demonstrate the superiority of FSL in real-word world FL settings; in particular, (1) FSL achieves similar perfor- mances as state-of-the-art FedAvg with significantly lower communication costs: for CIFAR1O, 10, FSL achieves same performance as Federated Averaging while re- ducing communication cost by ~ 35%. (2) FSL is substantially more robust to poisoning attacks than state-of-the-ar robust aggregation algorithms.
INTRODUCTION
Federated Learning (FL) is an emerging AI technology, where mutually untrusted clients (e.g.. An- droid devices) collaborate to train shared model, called the global model, without explicitly sharing their local training data. FI. training involves a server (e.g., Google server) which collects model updates from selected FI. clients in each round of training, and uses them to update the global model. FL., although highly promising, faces multiple challenges (Kairouz et al.) 2019 Li et al.) 2020b) to its practical deployment, in particular, communication efficiency and robustness, which are the focus of our work. Privacy preservation is another major challenge to FL, but is orthogonal to our work.
We present Federated Supermask Learning (FSL), a novel approach to perform FL while concur- rently achieving the two goals of robustness and communication efficiency. FSL is built novel learning paradigm called supermasks (Zhou et al. 2019 Ramanujan et al. (020), which allows it to reduce communication costs while achieving significantly higher robustness. Specifically, in FSL,, clients collaborate to find a subnetwork within a randomly initialized neural network which we call the supernetwork (this in contrast conventional FL where clients collaborate train neural network). The goal of training in FSL is to collaboratively identify a supermask, which is a binary mask of I's and O's, that is superimposed on the random neural network (the supernetwork) obtain the final subnetwork. The subnetwork is then used for downstream tasks, e.g., image classification, hence it is equivalent to the global model in conventional FL. Note that entire FSL training, weights of the supernetwork do not change.
More specifically, each FSL. client computes the importance of the edges of the supernetwork based on their local data. The importance of the edges is represented as ranking vector. Each FSL client will use the edge popup algorithm (Ramanujan et al. 2020) and their data to compute their local rankings (the edge popup algorithm aims at learning which edges in a supernetwork are more important over the other edges by minimizing the loss of the subnetwork on their local data). Each client then will send their local edge ranking the server. Finally, the FSL server uses novel voting mechanism to aggregate client rankings into a supermask, which represents which edges of the random neural network (the supernetwork) will form the global subnetwork.

---

Under review as a conference paper at ICLR 2022
Intuitions on FSL's robustness: In traditional FL algorithms, clients send large- lange-dimension model updates E Rd (real numbers) to the server, providing malicious clients a significant flexibility in fabricating malicious updates. By contrast, FSL clients merely share the rankings of the edges of the supernetwork, i.e., integers E [1. [1.d, where d is the size of the supernetwork. Therefore, as we will show both theoretically and empirically, FSL provides robustness by design and reduces the impact of untargeted poisoning attacks. Furthermore, unlike most existing robust FL frameworks, FSL does not require any knowledge about the percentages of malicious clients.
Intuitions on FSL's communication efficiency: In FSL, the clients and the server communicate just the rankings of the edges in the supernetwork, i..., a permutation of indices in [1, d]. Ranking vectors are generally significantly smaller than the global model. This, as we will show, signifi- cantly reduces the upload and download communication in FSI. compared to Federated Averaging (FedAvg) (McMahan et al. 2017), where clients communicate model parameters, each of 32/64 bits.
Empirical results: We experiment with three datasets in real-world heterogeneous FL settings and show that: (1) FSL achieves similar performance (e.g.. model accuracy) as state-of-the-ar FedAvg but with significantly reduced communication costs: for CIFARIO 10, the accuracy and communication cost per client are 85.4% and 40.2MB for FedAvg. while 85.3% and 26.2MB for FSL. (2) FSL is highly robust to poisoning attacks as compared to state-of-thee the--ht-rttttt robust aggregation algorithms: from 85.4% in the benign setting, 10% malicious clients reduce the accuracy of FL to 56.3% and 58.8% with Trimmed- (Xie et al.] 20188 Yin et al., 2018) and Multi-Krum (Blanchard et al., 2017). respectively, while FSL's performance only decreases 79.0%.
We also compare FSL with two communication reduction methods, SignSGD (Bernstein et al, 2019) and TopK (Alistarh al. 2018a) and show that FSL produces comparable communication costs and model accuracies. For instance, on CIFAR 10, FSL, SignSGD, and TopK achieve 85.3%, 79.1%, and 82.1% test accuracy, respectively. when the corresponding communication costs (down- load and upload) are 26, 20.73 and 30.79MB. On the other hand, FSL offers a significantly superior robustness. For instance, on CIFARIO. 10% (20%) malicious clients reduce the accuracy of SignSGI to 39.7% (10.0%), but FSL's accuracy decreases to only 79.0% (69.5%). TopK is in- compatible with existing robust aggregation algorithms, hence uses Average aggregation and as vulnerable as FedAvg, especially in the real-world heterogeneous settings.
2 RELATED WORKS
Supermask Learning: Modern neural networks have a very large number of parameters. These networks are generally overparameterized (Dauphin & Bengio 2013, Denil et al. 2013), i.e., they have more parameters than they need to perform a particular task, e.g., classification. The lottery ticket hypothesis (Frankle & Carbin 2019) states that a fully-trained neural network, i.c., supernet work, contains sparse subnetworks, L.e., subsets of all neurons in supemneworr, which can be trained from scratch (i.e., by training same initialized weights of the subnetwork) and achieve performances close to the fully trained supernetwork. The lottery ticket hypothesis allows for massive reductions in the sizes of neural networks. (Ramanujan et al. (2020) offer a complementary conjecture that an overparameterized neural network with randomly initialized weights contains subnetworks which perform as good as the fully trained network.
Poisoning Attacks and Defenses for Federated Learning (FL): FL involves mutually untrusting clients. Hence, a poisoning adversary may own or compromise some of the FL clients, called malicious clients, with the goal of mounting targeted or untargeted poisoning attack. In targeted attack, the goal is to reduce the utility of the model on specific test inputs, while in the untargeted attack, the goal is to reduce the utility for all (or most) test inputs. It is shown (Blanchard et al., 2017) that even a single malicious client can mount an effective untargeted attack on FedAvg.
In order to make FL robust to the presence of such malicious clients, the literature has designed various robust aggregation rules (AGR) (Blanchard et al. 2017 Mhamdi et al., 2018 Yin et al.) 2018 Chang et al.) 2019), which aim to remove or attenuate the updates that are more likely to be malicious according to some criterion. For instance, Multi-krum (Blanchard et al.) 2017) repeatedly removes updates that are far from the geometric median of all the updates, and Trimmed- mean (Xie) et al. 2018 Yin et al. 2018) removes the largest and smallest values of each update dimension and calculates the mean of the remaining values. Unfortunately. these robust AGRs are not very effective
in non-convex FL. settings and multiple works have demonstrated strong targeted (Wang al. 2020
2

---

Under review as a conference paper at ICLR 2022
Bhagoji al. 2019) and untargeted attacks (Shejwalkar & Houmansadr 2021 Fang et al. 2020 on them.
Communication Cost of FL: In many real-world applications of FL, it is essential to minimize the communication between FL server and clients. Especially in cross-device FL. the clients (c.g., mobile phones and wearable devices) have limited resources and communication can be a major bottleneck. There are two major types of communication reduction methods: (1) Qunatization methods reduce the resolution of (i.e., number of bits used represent) each dimension of client update. For instance, SignSGD (Bernstein et al. 2019) uses the sign (1 bit) of each dimension of model updates. (2) Sparsification methods methods propose use only subset of all the update dimensions. For instance, in TopK (Aji & Heatield 2017 Alistarh et al.) 2218a), only the largest K% update dimensions are sent to the server in each FI. round, We note that, communication reduction methods primarily focus on and succeed at reducing upload communication (client - server), but they use the entire model download communication (server -> client).
PRELIMINARIES
3.1 FEDERATED LEARNING
In FL (McMahan et al.) 2017 Kairouz et al. 2019] Konečný et al. (016), N clients collaborate to train a global model without directly sharing their data. In round t, the service provider (server) selects n out of N total clients and sends them the most recent global model 0*. Each client trains local model for E local epochs on their data starting from the A using stochastic gradient descent (SGD). Then the client send back the calculated gradients (Vx for kth client) to the server. The server then aggregates the collected gradients and updates the global model for the next round. FL can be either cross-device or cross-silo (Kairouz et al., 2019). In cross-device FL, N is large (from few thousands to billions) and only a small fraction of clients is chosen each FL training round, i.c., n < N. By contrast, in cross-silo FL, N is moderate (up to 100) and all clients are chosen in each round, i.c., n N. In this work, we evaluate the performance of FSL and other FL baselines for cross-device FL under realistic production FL settings.
Algorithm 1 Edge-popup (EP) algorithm: it finds a subnetwork of size 1% of the entire network 1: Input: number of local epochs E, training data D. initial weights 9" and scores 8", sub- network size 1%, learning rate T
3.2 EDGE-POPUP ALGORITHM
The edge-popup (EP) algorithm Ramanujan al. (020) is a novel optimization method to lind supermasks within a large, randomly ini- tialized neural network, i.e., a supernetwork, with performances close to the fully trained su- pernetwork. EP algorithm does not train the weights of the network, instead only decides the set of edges to keep and removes the rest of the edges (i.e., pop). Specifically, EP al- gorithm assigns a positive score to each of the edges in the supernetwork. On forward pass, it selects top k% edges with highest scores, where is the percentage of the total number of edges in the supernetwork that will remain in the fi- nal subnetwork. On the backward pass, it up- dates the scores with the traight-thhouuhe gradi-
2:
for E [E] do
3:
B Split D in B batches
4:
for batch b E [B] do
5:
EP FORWARD (8"h 00,k, k, f- 0 - (((=:b))
6:
7: end for
8: end for
9: return 0=
10: function EP FORWARD(#" ,0,, ,,, b)
11:
m + sort(0")
12:
f int((1
k) ien(m))
13:
mf:
14:
m]t: =1
15:
OP 0" о m
ent estimator (Bengio et al. (203).. Algorithm
16: return
(P)
presents EP algorithm; we defer further details to Appendix
17:
end function
4 FEDERATED SUPERMASK LEARNING: DESIGN
In this section, we provide the design of our federated supermask learning (FSL) algorithm. FSL clients collaborate (without sharing their local data) to find subnetwork within randomly ini- tialized, untrained neural network called the supernetwork. Algorithm 2 describes FSL's training. Training a global model in FSL means to first find unanimous ranking of supernetwork edges and then use the subnetwork of the top ranked edges as the final output. We detail a round of FSL train- ing and depict it in Figure TT. where we use supernetwork with six edges <4((0,5) to demonstrate
3

---

Under review as a conference paper at ICLR 2022
single FSL round and consider three clients Cj((,a] who aim to find subnetwork of size k=50% of the original supernetwork.
Algorithm 2 Federated Supermask Learning (FSL)
Input: number of FL. rounds T, number of local epochs E, number of selected users in each round seed SEED, learning rate y, subnetwork size 4%
2: Server: Initialization
3: 0* @ <- Initialize random scores and weights of global model 0 using SEED
4: Ry ARGSORT((*)
Sort the initial scores and obtain initial rankings
5: for t [1, do
6:
U 4 set of n randomly selected clients out of N total clients
7:
for in U do
8:
Clients: Calculating the ranks
9:
0r, 0 + Initialize scores and weights using SEED
10:
[n g. f (0*)(0")
b sort the scores based on the global ranking D Client u uses Algorithn to train a
11:
S < 55Egge--Ppp EddgePPoUUp(F, Drr, 00,0", 00,k,, k))))
supermask its local training data
12:
R + ARGSORT(S)
> Ranking of the client
end for 14: Server: Majority Vote
R + NOTR(R
P Majority vote aggregation
16: end for
17: function VOTE(RquEUT) ):
V + (RGSORT(R(UETT)
A LUM(V)
20: return (RGSORT(A)
end function
4.1 SERVER: INITIALIZATION PHASE (ONLY FOR ROUND =
In the first round, the FSL server chooses random seed SEED to generate initial random weights 8" and scores 8 for the global supernetwork note that, f", 8", and SEED remain constant during the entire FSL. training. Next, the FSL server shares SEED with FSL clients, who can then locally reconstruct the initial weights d" and scores 0* using SEED. Figure 1 depicts this step.
Recall that, the goal of FSL training is to find the most important edges in tt without changing the weights. Unless specified otherwise, both server and clients use the Singed Kaiming Constant algo- rithm (Ramanujan et al. 2020) to generate random weights and the Kaiming Uniform algorithm (He) et al. 2015) to generate random scores. However, in Appendix C.I we also explore the impacts of different initialization algorithms the performance of FSL. We use the same seed to initialize weights and scores.
At the beginning, the FSL server finds the global rankings of the initial random scores (Algorithm) line 4), i.e., R. = ARGSORT((*). We define rankings of a vector as the indices of elements vector when the vector is sorted from low to high, which is computed using ARGSORT function (argsort).
4.2 CLIENTS: CALCULATING THE RANKS (FOR EACH ROUND t)
In the t round, FSL server randomly selects n clients among total N clients, and shares the global rankings R², with them. Each of the selected clients locally reconstructs the weights 0w's ' and scores 8* using SEED (Algorithm based on the global rankings, R2 (Algorithm 2 line 10); we depict this in Figure 22)
2 line 9). Then, each FSL client reorders the random scores
Next, each of the clients uses reordered (+ and finds subnetwork within 0 using Algorithm I to find a subnetwork, they use their local data and F. local epochs (A (Algorithm line 11). Note that, each iteration of Algorithm updates the scores 6². Then client u computes their local rankings R using the final updated scores (S) and ARGSORT()), and sends R to the server. Figure 2a shows how each of the selected clients reorders the random scores using global rankings. For instance, the initial global rankings for this round are 9 = [2, 3, O, 5, 1, 4], meaning that edge e4 should get the highest score (84 = 1.2), and edge e2 should get the lowest score (82 0.2).
2
4

---

Under review as a conference paper at ICLR 2022
Server: Initialization
2b
Clients: training
Server: Vote
nd (any: mi miy Ma, Mi my
d" (0.5, 0.2, 0.7,
Clcnt 1
05
Pg
1 +
+1+00
0
2
V
0
1/
15
P
P
2
5
0
+1
+
12
8
0
2/
Pa
3
5
11
R2
[4,
2, 3,
Pa
0
8
P3
4 3
9
Client 2
3,,2,3,0,47
05
V
R3
2,,,,4,5,3,1
2/2
Clients: reordering
55
00.5, 0.2, 0.3, O.T,
R
0, 1, 4,
R
5,
55
0
15
0..4 1.2, 0.3.
R5 2, 3,4,, 1,
Figure 1: A single FSL round with three clients and network of 6 edges.
2h shows, for each client, the scores and rankings they obtained after finding their local subnetwork. For example, rankings of client C₁ are R = [4, 0, 2, 3, 5. 11, i.e., 64 is the least impor- tant and e1 is the most important edge for C1. Considering desired subnetwork size to be 50%, C1 uses edges {3,5,1} in their final subnetwork.
Figure
4.3 SERVER: MAJORITY VOTE (FOR EACH ROUND f)
The server receives all the local rankings of the selected n clients, i.c., R Me Then, it performs majority vote over all the local rankings using VOTE(.) function. Note that, for client u, the index represents the importance of the edge R2 [X] for C.. For instance, in Figure
2h, rankings of C1 are R = [4, 2, 3, 5, 1]. hence the edge 64 at index=0 is the least important edge for C1, while the edge e1 index=5 is the most important edge. Consequently, VOTE(.) function assigns reputation=0 to edge e4, reputation=1 to ég, reputation=2 to e2, and so on. In other words, for rankings It, of Cn and edge ex, VOTE(.) computes the reputation of e; its index in R. Finally, VOTE(.) computes the total reputation of e; as the sum reputations from each of the local rankings. In Figure 2b) reputations of en are in Ri in R2 and Ry., hence, the total reputation of ég is 2. We depict this in Figure I 3; here, the final total reputations for edges (ic[(o,5] A [2, 12, 3, 11, 8, 9]. Finally, the server computes global rankings R for round 1 by sorting the final total reputations of all edges, i.e., R ARGSORT(A).
Note that, all FSL operations that involve sorting, reordering, and voting are performed in a layer- wise manner. For instance, the server computes global rankings Rt in round for each layer sepa- rately, and consequently, the clients selected in round reorder their local randomly generated scores 8* for each layer separately.
5 FEDERATED SUPERMASK LEARNING: SALIENT FEATURES
In this section, discuss the two salient features of FSL that instrumental for any distributed learning algorithm to be practical: robustness to poisoning attacks and communication efficiency.
5.1 ROBUSTNESS OF FSL TO POISONING ATTACKS
FSL is distributed learning algorithm with mutually untrusting clients. Hence, a poisoning adver- sary may own or compromise some FSL clients, called malicious clients, and mount a targeted untargeted poisoning attack. In our work, consider the untargeted attacks as they more severe than targeted attacks and can cause ofniall-f-service for collaborating clients (Shejwalkar al. 202T and show that FSL is secure against such poisoning attacks by design.
5

---

Under review as a conference paper at ICLR 2022
Intuition on FSL's robustness: Existing FL algorithms, including robust FL algorithms, are shown to be vulnerable to targeted and untargeted poisoning attacks (Shejwalkar et al. (021) where mali- cious clients corrupt the global model by sharing malicious model updates. One of the key reasons behind the susceptibility of existing algorithms is that their model updates can have arbitrary values. For instance, manipulate vanilla FedAvg, malicious clients send very large updates (Blanchard itt 2017), and to manipulate Multi-krum and Trimmed-men Houmansadr 2021 propose to perturb benign update in a specific malicious direction. On the other hand, in FSL, clients must send a permutation of indices E [1, ne] for each layer. Hence, FSL significantly reduces the space of the possible malicious updates that an adversary can craft. Ma- jority voting in FSL further reduces the chances of successful attack. Intuitively, this makes FSL design robust to poisoning attacks. Below, we make this intuition more concrete.
(Fang et al. [020; Shejwalkar &
The worst-case untargeted poisoning attack on FSL: Here, the poisoning adversary aims to reduce the accuracy of the final global FSL. subnetwork on most test inputs. To achieve this, the adversary should replace the high ranked edges with low ranked edges in the final subnetwork. For the worst-case analysis of FSL, we assume a very strong adversary (i.e., threat model); 1) each of the malicious clients has some data from benign distribution; 2) malicious clients know the entire FSL algorithm and its parameters; 3) malicious clients can collude. Under this threat model we design worst case attack on FSL (Algorithm in Appendix (A.I), which executes as follows: First, all malicious clients compute rankings on their benign data and use VOTE(.) algorithm to compute an aggregate rankings. Finally, each of the malicious clients uses the reverse of the aggregate rankings to share with the FSL server in given round. The adversary should invert the rankings layer-wise as the FSL server will aggregate the local rankings per layer too, and it is not possible mount model-wise attack.
Now we justify why the attack in Algorithm B the worst case attack on FSL for the strong threat model we consider. Note that, FSL aggregation, i.e., VOTE(.,, computes the reputations using clients' rankings and sums the reputations of each network edge. Therefore, the strongest poi- soning attack would want to reduce the reputation of good edges. This can be achieved following the aforementioned procedure of Algorithm 3 to reverse the rankings computed using benign data.
Theoretical analysis of robustness of FSL algorithm: In this section, we prove an upper bound on the failure
probability of robustness of FSL, i.e., the probability that a good edge will be removed from the final subnetwork when malicious clients mount the worst case attack.
10
1.0
a
70
Vote Falure Faluee Prob Uppesbound
0.8
Following the work of Bernstein et al. 2019), we make two assumptions in order to facilitate concrete robust- ness analysis of FSL: a) each malicious client has access only to its own data, and b) we consider a simpler VOTE(.) function, where the FSL server puts an edge e; in the fi- nal subnetwork if more than half of the clients have e; (a good edge) in their local subnetworks. In other words, the rankings that each client sends to the server is just a bit mask showing that each edge should or should not be in the final subnetwork. The server makes majority vote on the bit masks, and if an edge has more than half votes, will be in the global subnetwork. Our VOTE()) mecha- nism has more strict robustness criterion, it uses more nuanced reputations of edges instead of bit masks. Hence, the upper bound on failure probability in this section also applies to the FSL VOTE(.) function.
0.6
0.4
0.2
0.0
0.6
0.7
U.8
0.9
1.0
Figure 2: Upper bound on the failure
probability of VOTE(.) function in FSL.
The probability that our voting system fails is the probability that more than half of the votes do not include 6; in their subnetworks. The upper bound on the probability of failure would be 1/2 mp(1-p) p)
where n is the number of clients being processed, p shows the probabil- ity that a benign client puts e; in their top ranks, and a is the fraction of malicious clients. Due to space limitations, we defer the detailed proof to Appendix A.2 [ the upper bound on the failure of VOTE(.) for different values of a and p. We note that, the higher the probability p. the higher the robustness of FSL.

---

Under review as a conference paper at ICLR 2022
5.2 FSL's COMMUNICATION COSTS
In FI,, and especially in the cross-device setting, clients have limited communication bandwidth. Hence, FL. algorithms must be communication efficient. We discuss here the communication cost of FSL. algorithm. In the first round, the FSL. server only sends one seed of 32 bits all the FSL, clients, so they can construct the random weights (0")) and scores (0*). In round t, each of selected FSL clients receives the global rankings Ry and sends back their local rankings R The rankings are a permutation of the indices of the edges in each layer, i.e. of [0, ny - 1jve E [L] where L the number of layers and ng is the number of parameters in 7th layer.
We use the naive approach to communicate layer-wise rankings, where each FSL client exchanges total of LeELy ne x log(ne) bits. Because, for the layer e, the client receives and sends ny ranks where each one is encoded with log(ne) bits. On the other hand, client exchanges ΣeE[L] ngg 32 bits in FedAvg, when 32 bits are used to represent each of n, weights in layer f. Appendix we compare theoretical communication costs of various FL algorithms.
Sparse-FSLL Here, we propose Sparse-FSL, a simple extension of FSL to further reduce the com- munication cost. In Sparse-FLS, client sends only the most important ranks of their local rankings to the server for aggregation. For instance, in Figure | client C1 sends Ri = [4, 0, 2, 5, 1] in case of FSL. But in sparse-FSL. with sparsity set to 50%, client C1 sends just the top 3 rankings, i.e., sends R = [3. 5, 1]. For each client, the sparse-FSL server assumes O reputation for all of the edges not included in the client's rankings, i.e., in Figure sparse-FSL server will assign reputation=O for edges Ca. Co. and 62 Then the server uses VOTE(.) to compute total reputations of all edges and then sort them obtain the final aggregate global rankings, i.e., R2 use for subsequent rounds. We observe in out experiments, that sparse-FSL performs very close to FSL, even with sparsity as low as 10%, while also significantly reducing the communication cost. Due to space limitation, we defer the communication cost comparison of FSL with FedAvg, SingSGD, and LotteryFL (Li et al.) 2020ah to Appendix F.
EXPERIMENTS
In this section, we investigate the utility, robustness, and communication cost of our FSL frame- work. We use MNIST, CIFARIO. 10, and FEMNIST data and distribute them in non-iid fashion (using Dirichlet distribution) among 1000, 1000, and 3400 clients respectively. At the end of the training, we calculate the test accuracy of all the clients on the final global model, and we report the mean and standard deviation of all clients' test accuracies in our experiments. We provide further details of experimental setup in Appendix B In addition to FSL, we also evaluate Sparse-FSL in different settings. We use SFSL top x% to denote Sparse-FSI. clients who sends top x% of ranks in each round.
6.1 COMMUNICATION COST ANALYSIS
In FSL, both clients and server communicate just the edge ranks instead of weight parameters.
Thus, FSL reduces both upload and download communication cost. Table [ illustrates the utility,
i.e. the accuracy on test data, and communication cost of FSL and state-of-the-art quantization.
i.e., SignSGD (Bernstein et al. 2019) and sparsification, i.e., TopK (Alistarh et al. 2018b Aji & Heafield 2017) Communication-redueee reduction methods.
FSL versus SignSGD: We note that, FSL is significantly more accurate than SignSGD. For in- stance, on CIFARIO, distributed non-iid among 1000 clients, FSL achieves 85.3% while SignSGD achieves 79.1% or on FEMNIST, FSL achieves 84.2% while SignSGD achieves 79.3%. This is because, FSL clients send more nuanced information via rankings of their subnetworks compared to SignSGD, where clients just send the signs of their model updates.
SignSGD in FL reduces only the upload communication, but for efficiency reasons, the server sends all of the weight parameters (each of 32 bits) to the newly selected clients. Hence, SignSGD has very efficient upload communication, but very inefficient download communication. For instance, on CIFARIO, 10, for both upload and download, FSL achieves 13. each while SignSGD achieves 0.63MB and 20.IMB, respectively.
FSL versus TopK: We compare FSL with TopK with K E {10, 50]%. FSL is more accurate than Topk for MNIST and CIFAR10: on CIFAR1O, FSL accuracy is 85.3%, while TopK accuracies are 82. 1 % and 77.8% with K=50% and K=10%, respectively. Similar to SignSGD, Topk is more efficiently reduces upload cost, but has very high download communication cost. Therefore, the
7

---

Under review as a conference paper at ICLR 2022
Table 1: Comparing the utility (test accuracy) and communication cost of FedAvg, FSL (in bold),
SignSGD and, TopK and Sparse-FSL (SFSL) with different percentages of sparsity (in bold).
Dataset
Algorithm
Accuracy (STD)
Upload (MB)
Download (MB)
FedAvg
98.8 (3.1)
6.20
6.20
FSL
98.8 (3.2)
4.05
4.05
SESL Top 50%
98.2 (3.8)
2.03
4.05
MNIST + LoNet
SFSL Top 10%
89.5 (9.2)
0.40
4.05
1000 clients
SignSGD
97.2 (4.6)
0.19
6.20
TopK 50%
98.8 (3.2)
3.29
6.20
TopK 10%
98.7 (3.2)
0.81
6.20
FedAvg
85.4 (11.2)
20.1
FSL
85.3 (11.3)
13.1
13.1
SFSI. Top 50%
77.6 (13.0)
6.5
13.1
CIFARIO + Conv8
1000 clients
SFSL Top 10%
27.5 (14.4)
1.3
13.1
SignSGD
79.1 (13.6)
0.63
20.1
TopK 50%
82.1 (11.8)
10.69
20.1
TopK 10%
77.8 (13.0)
2.64
20.1
FedAvg
85.8 (10.2)
6.23
6.23
FSL
84.2 (10.7)
4.06
4.06
SESL Top 50%
75.2 (12.7)
2.03
4.06
FEMNIST LeNet
SFSI. Top 10%
59.2 (15.0)
0.40
4.06
3400 clients
SignSGD
79.3 (12.4)
0.19
6.23
TopK 50%
85.7 (9.9)
3.31
6.23
TopK 10%
85.5 (10.0)
0.81
6.23
combined upload and download communication cost per client per round is 26.2MB for FSL and 30.79MB for TopK with K=50%, and TopK still has worse performance.
Communication cost reduction due to Sparse-FSL. (SFSL): We now evaluate SFSL explained in Section 5.2 In SFSL with top 50% ranks, clients send the top 50% their ranks to the server, which reduces the upload bandwidth consumption by half. Please note that the download cost of SFSL is the same as FSL since the FSL server should send all the global rankings to the selected clients in each round. We note from Table | that, by sending fewer ranks, SFSL reduces upload communication at a small cost of performance. For instance, on II,AR10, SFLS with top 50% reduces the upload communication by 50% at the cost reducing accuracy from 85.4% 77.6%.
6.2 SECURITY ANALYSIS
We compare FSL with state-of-the-art robust aggregation rules (AGRs): Mkrum (Blanchard et al. 2017), and Trimmed-mean (Xie al. 2018 Yin al.) 2018). Table gives the performances of robust AGRs, SignSGD, and FSL with different percentages of malicious clients. Here, we make rather impractical assumption favor of the robust AGRs: we assume that the server knows the exact % of malicious clients in each FL round. FSL does not require this knowledge.
FSL achieves higher robustness than stafe-of-the-arf robust AGRs: We note from Table 2 that, FSL is more robust to the presence of malicious clients who try to poison the global model compared to Multi-Krum, Trimmed-mean, and SignSGD for both 10% and 20% malicious clients rates. For instance, CIFAR10, 10% malicious clients can decrease the accuracy of FL models to 56.3%, 58.8%, and 39.8% for Trimmed-mean, Multi-Krun Krum, and SignSGD respectively; 20% malicious clients can decrease the accuracy of the FL models 20.5%, 25.6%, 10.0% for Trimmed-men Multi-Krum Krum, and SignSGD respectively. On the other hand, FSL performance decreases to 79.0% and 69.5% for 10% and 20% attacking ratio respectively.
We make similar observations for MNIST and FEMNIST datasets: for FEMNIST, 10% (20%) mali- cious clients reduce accuracy of the global model from 85.8% to 72.7% (56.2%) for Trimmed-Mean to 80.9% 9% (23.7%) for Multi-krum, and 76.7% (55.1% %) for SignSGD, while FSL accuracy decreases 83.00 0% (65.5) (6).. We omit evaluating TopK, because even single malicious client (Blanchard et al. 2017 can jeopardize its accuracy.
8

---

Under review as a conference paper at ICLR 2022
Table 2: Comparing the robustness of various FI. algorithms: FSL and SFSL (in bold) outperform
state-of-the-art robust AGRs and SignSGD against strongest of untargeted poisoning attacks.
Dataset
AGR
No malicious
10% malicious
20% malicious
FedAvg
98.8 (3.2)
10.0 (10.0)
10.0 (10.0)
Trimmed-ment
98.8 (3.2)
95.1 (7.7)
87.6 (9.5)
MNIST LeNet
Multi-krum
98.8 (3.2)
98.6 (3.3)
97.9 (4.1)
1000 clients
SignSGD
97.2 (4.6)
96.6 (5.0)
96.2 (5.6)
FSL
98.8 (3.1)
98.8 (3.1)
98.7 (3.3)
SFSL Top 50%
98.2 (3.8)
97.04 (4.4)
95.1 (7.8)
FedAvg
85.4 (11.2)
10.0 (10.1)
10.0 (10.1)
Trimmed mean
84,9 (11.0)
56.3 (16.0)
20.5 (13.2)
CIFAR1O Conv8
Multi-krum
84.7 (11.3)
58.8 (15.8)
25.6 (14.4)
1000 clients
SignSGD
79.1 (12.8)
39.7 (15.9)
10.0 (10.1)
FSL
85.3 (11.3)
79.0 (12.4)
69.5 (14.8)
SESI. Top 50%
77.6 (13.0)
41.7 (15.4)
39.7 (15.2)
FedAvg
85,8 (10.2)
6.3 (5.8)
6.3 (5.8)
Trimmed-mean
85.2 (11.0)
72.7 (15.7)
56.2 (20.3)
FEMNIST + LeNet
Multi-krum
85.2 (10.9)
80.9 (12.2)
23.7 (12.8)
3400 clients
SignSGD
(12.4)
76.7 (13.2)
55.1 (14.9)
FSL
84.2 (10.7)
83.0 (10.9)
65.8 (17.8)
SFSL Top 50%
75.2 (12.7)
70.5 (14.4)
60.39 (14.8)
6.3 MISCELLANEOUS DISCUSSIONS
Due to space limitations, we defer a detailed discussion ablation studies of FSL to Appendix C and below give their important takeaways.
Initialization matters in FSL:: In FSI., the weight parameters are randomly initialized at the start and remain fixed throughout the training. An appropriate initialization is instrumental to the success of FSL, since the clients are trying to find the most important weight parameters, We study efficacy of three initializing strategies that use three different distributions: Glorot Normal, Kaiming Normal, and Singed Kaiming Constant. Table 5) shows the results. We observe from Table that, Singed Kaiming Constant initialization achieves the best results that are closest to FedAvg.
Varying the sparsity of edge-popup algorithm in FSL: Figure illustrates how the performance of FSL varies with the sizes of local subnetworks that the clients share with the server. In other words, when we vary the sparsity 1% of edge popup algorithm during local subnetwork search [10, 20, 30, 40, 50, 60, 70, 80, 90]%. Interestingly we note that, FSL performs the worst when clients use all (k=100%) or none (k=0%) of the edges. This is because, it is difficult to find subnetwork with small number of edges. While using all of the edge essentially results in using a random neural network. As we can see FSL with & E [40, 70)%, gives the best performances for all the three datasets. Hence, we set k550% by default our experiments.
CONCLUSIONS
We designed a novel collaborative learning algorithm, called Federated Supermask Learning (FSL), to address the issues of robustness to poisoning and communication efficiency in existing FL algo- rithms. We argue that core reason for the susceptibility of existing FL. algorithms to poisoning is the use of arbitrary values in their model updates. Hence, in FSL, we use ranks of edges of randomly initialized neural network contributed by collaborating clients to find global ranking and then use subnetwork based only on the top edges. Use of rankings in a fixed range restricts the space available to poisoning adversaries to craft malicious updates, and also allows FSL to use sophisticated communication reduction methods. We show, both theoretically and empirically, that ranking based collaborative learning can effectively mitigate the robustness issue as well as reduce the communication costs involved.

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
We have attached our implementation code and experiment notebooks as supplementary materi- als. There are separate experiment notebooks showing the process of FSL training for MNIST, CIFARIO, and FEMNIST (results that we used in Table [ and 2). We have explained all the hyperparameters including optimizer, learning rate, momentum, weight decay, and batch size Ap- pendix B.I for both FSL and FedAvg (including using robust AGRs) settings. We also explained the model architectures we used in our experiments in Table 4 explaining different layers with number of parameters inside each. We also explained how distributed MNIST and CIFARIO samples among 1,000 clients using Dirichlet distribution to make them non-iid Appendix
We propose Federated Supermask Learning (FSL) where clients find subnetwork within ran- domly initialized neural network, without training the weights of the network. Our extensive evalu- ation demonstrated FSL can provide better communication and more robustness to untargeted poisoning attacks compared to existing FL compressors and Byzantine-robust aggregation rules.
REFERENCES
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems 31: NeurIPS, 2018a.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pp. 5973-5983, 2018b.
argsort.
argsor..
URL httes///pttoccccoorr//////saaaae
torch. argsort..rrr..cc.o.o html
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint
2013.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. In 7th International Conference on Learning Representations, ICLR, 2019.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning, pp. 634 643, 2019.
Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries: Byzan- tine tolerant gradient descent. In Advances in Neural Information Prucessing Systems, pp. 119- 129, 2017.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. CoRR, abs/1812.01097, 2018.
URL http::htta//iiiieeeeee wttp://b///.........00
Francesco Paolo Cantelli. Sui confini della probabilita. In Ati del Congresso Internazionale dei Matematici: Bologna del 3 10 de settembre di 1928, pp. 47-60, 1929.
Hongyan Chang, Virat Shejwalkar, Reza Shokri, and Amir Houmansadr. Cronus: Robust and het- erogeneous collaborative learning with black- box knowledge transfer, 2019.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André Schaik. EMNIST: extending
MNIST to handwritten letters. In 2017 International Joint Conference on Neural Nenworks, IJCNN, 2017.
10

---

Under review as a conference paper at ICLR 2022
Yann N Dauphin and Yoshua Bengio. Big neural networks waste capacity. arXiv preprint 13X.v:130..3533, 2013.
Misha Denil, Babak Shakibi, Laurent Dinh, Mare Aurelio Ranzato, and Nando de Freitas. Predicting parameters in deep learning. In Proceedings of the 26th International Conference on Neural Information Processing Eestems-Volumee 2. pp. 2148-2156, 2013.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Local model poisoning attacks to byzantine-robust federated learning. Srdjan Capkun and Franziska Roesner (eds.), 29th USENIX Security Symposium, USENIX Security, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. ICLR, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint (rXXiv:109.06333 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: 19Xxv:9112.04977 2019.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:/610.05492 2016.
Alex Krizhevsky and Geoffrey Hinton. 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--efiiiee federated learning with lottery ticket hypothesis on non-iid datasets. CoRR, 2020a. URL/ttts:: arxiv. org. habs//////// 2208 03371
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020b.
Heiko Ludwig, Nathalie Baracaldo, Gegi Thomas, and Yi Zhou. IBM federated learning: an enter- prise framework white paper V0.1. CoRR, abs/2007.109%; 2020.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-fffcienn learning of deep networks from decentralized data. Proceedings of the 20 th International Conference on Artificial Intelligence and Statistics, 2017.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of dis- tributed learning in byzantium. In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018
Matthias Paulik, Matt Seigel, and Henry Mason and. Federated evaluation and tuning for on-device
personalization: System design & applications. CoRR, abs/2102.08503, 2021. URL https:
7/ wtw.ix/.rr/aab///00 2210 211.110020001311 08503
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in a randomly weighted neural network? In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pp. 11893-11902, 2020.
Sashank J Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2020.
11

---

Under review as a conference paper at ICLR 2022
Virat Shejwalkar and Amir Houmansadr. Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning. Proceedings of the 28th Network and Distributed System Security Symposium, (NDSS), 2021.
Virat Shejwalkar, Amir Houmansadr, Peter Kairouz, and Daniel Ramage. Back the drawing board: A critical evaluation of poisoning attacks on federated learning. arXiv preprint arXiv:2108. 10241,
2021.
Hongyi Wang. Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy- yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. arXiv preprint urXiv:2007.05000 2020.
Mitchell Wortsman, Vivek Ramanujan, Rosanne Liu, Aniruddha Kembhavi, Mohammad Rastegari, Jason Yosinski, and Ali Farhadi. Supermasks in superposition. In Advances in Neural Information Processing Systems 33: NeurIPS, 2020.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd. arXiv preprint arXiv: 16, 2018.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter L., Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In Jennifer G. Dy and Andreas Krause (eds.), Pro- ceedings of the 35th International Conference on Machine Learning, ICML, 2018.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: 7eros, signs, and the supermask. In Advances in Neural Information Processing Systems 32: NeurlPS, 2019.
12

---

Under review as a conference paper at ICLR 2022
A MISSING DETAILS OF ROBUSTNESS OF FSL
A.1 FSL WORST CASE POISONING ATTACK ALGORITHM
Algorithm shows the rankings poisoning attack explained in Section
Algorithm FSL Poisoning
1: Input: number of malicious clients M, number of malicious local epochs E', seed SEED, global ranking Ry learning rate 17, subnetwork size k%
2: function CRAFIMALLCIOOUPPPATELLLLAA SEED, Ryg. .).
3: for mu E [M do
D For all the malicious clients
4:
Malicious Client Executes:
5:
8", 8t + Initialize scores and weights using SEED
6:
0 [ f SORT((")
7:
S f Edge-PopUp(E', Dtt 0" ,0,,0, k,
8:
R f ARGSORT(S))
D Ranking of the malicious client
9:
end for
10: Aggregation:
11: P + VOTE(R R (M))
Majority vote aggregation b reverse the ranking
12: return REVERSE R
13:
end function
A.2 THEORETICAL ANALYSIS ROBUSTNESS OF FSL
In this section, we detail the proof of robustness of FSL. In other words, we prove upper bound on the failure probability of robustness of FSL, i.c. the probability that a good edge will be re- moved from the final subnetwork when malicious clients mount the worst case attack. Inspired from SignSGD Bernstein et al. 2019). for this proof, We assume a simpler VOTE(.) function where more than half of the clients add edge e; to their subnetworks, then the FSL server adds it to the final global subnetwork. We also assume that the malicious clients cannot collude our proof.
Assume that edge e; is good edge, i.c., having e; in the final subnetwork improves the performance of the final subnetwork. Let Z be the random variable that represents the number clients who vote for the edge e; be in the final subnetwork, i.e., the number of clients whose local subnetwork of size 6% of the entire supernetwork (Algorithm) 2 line 11) contains e,, Therefore, Z E [0, n] where is the number of clients being processed in given FSL round.
Let G and be the random variable that represent the number of benign and malicious clients that vote for edge e,, respectively; the malicious clients inadvertently exclude the good edge e; in their local subnetwork based on their benign training data.
There are total of an malicious clients, where is the fraction of malicious clients that of them decides that e; is bad edge and should not be removed. Each of the malicious clients computes the subnetwork on own benign training data, so of them do not conclude that e, is a good edge. Hence, Z G + B. We can say that G and B have binomial distribution i.e., G binomial((ani, - p] where p the probability that benign client
binomial([ (x) m. p) and has this edge in their local subnetwork and is the fraction of malicious clients. Note that the probability that our voting in simplified FSL fails is P[failure] = PiZ <= i..., when more than half of the clients vote against e,, i.e. they do not include e; in their local subnetworks. We can find the mean and variance as follows:
E|Zl =
(1- -1
apm + am(1 p))
(1)
V Var [2] (1 a)np(1 p) + amp(1 p) -pp1-p)
Cantelli 1929
provides an inequality where for random variable X with mean μ and variance X >= X| <= 1+ Using this inequality, we can write:
we have Plu
13

---

Under review as a conference paper at ICLR 2022
malicious ratio=10%
malicious ratio=30%
malicious ratio=20%
malicious ratio=40%
25
20
Number of Votes
15
10
5
0
5
10
15
20
Round
Figure 3: Empirical robustness bounds of FSL. Bars are showing the number votes for a particular edge in first layer of LeNet (trained MNIST) with selecting 25 clients in each round and no presence of malicious client. The adversary tries to flip one good edge from the global model. The horizontal lines showing the thresholds for each malicious ratio that if the number of votes is less than them, the adversary can change the decision about this edge.
P|Z <= n 2
Z - 7 >= E n/2]
<=
(3)
[B n vor [2]
because + x²2 >= 2x. we have:
Var [Z]
nip(1 p)
PIZ <= <= 1/2
(E|Z) - -n/2)3 1/2
(4)
(mp amp + an onpp -mpp-11 1122²2
npp11 - p)
= -1/2/ (m(p + a(1 2p) - 1/2))2
What this means is that the probability that the simplified VOTE(.) fails is upper bounded as in (4) We show the effect of different values a and p in Figure if the benign clients train better supermasks (better chance that good edge ended in their subnetwork), the probability that the attackers succeed lower (more robustness)) VOTE(.) in FSL (Section
can see from Figure 2
more sophisticated and puts more constraints on the malicious clients, hence the about upper bound also applies to FSL.
We show the theoretical relationship between upper bound the failure of VOTE(.) for different values of malicious rate (a) in Figure 2 To validate our theoretical bounds, we measure the least number of malicious clients that the adversary needs control remove good edge from the global subnetwork in Figure 3 In this figure, we report the votes of one particular edge in the first layer of LeNet (trained on MNIST) where there are 288 edges in the first layer (Table I.Ilooss the number of edges in each layer). We consider this edge
good edge since we observe that it would be the final global subnetwork (at FSL. round 20) if there were no malicious clients. this figure, the bars are showing the number of votes this edge received to be in the global subnetwork for that FSL round. The horizontal lines are showing the thresholds that the number of votes is less than them, the adversary
change the decision about this good edge. We are selecting 25 clients in each round, so we consider x a x 25 for thresholds. For instance, when we assume there are 20% malicious clients (on average there are malicious among 25 selected clients) that means that 5 votes of benign votes decreases and 5 votes is added to malicious votes, so the threshold would be 10.
14

---

Under review as a conference paper at ICLR 2022
Table 3: Model architectures. We identical architecture those
Ramanujan al.
2020
Wortsman et al. (2200) used.
Architecture
Layer Name
Number of parameters
Convolution(322> Relu
288
Convolution((4)) Relu MaxPool(2x2)
18432
LeNet + MNIST
(Wortsman et al. 2020
FC(128) + Relu FC(10)
1605632
1280
Convolution(64) Relu
1728
Convolution(644) Relu
36864
MaxPool(2x2)
Convolution( (28) + Relu
73728
Convolution( 128) Relu
147456
MaxPool(2x2))
Convolution(256) + Relu
294912
Conv8 CIFARIO
Convolution((56) Relu
589824
(Ramanujan et 2020
MaxPool (2x2)
Convolution + Relu
1179648
Convolution(512) Relu
2359296
(axPool(2x2))
FC(256) + Relu
524288
FC(256) + Relu
65536
FC(10)
2560
Convolution(32) Relu
288
Convolution(64) Relu
18432
LeNet + FEMNIST
MaxPool(2x2)
(Wortsman al. 2020
FC(128) + Relu
1605632
FC(62)
7936
B MISSING DETAILS OF EXPERIMENTAL SETUP
B. DATASETS AND MODEL ARCHITECTURES
MNIST is 10-class class- balanced classification task with 70.000 gray-scale images, each of size 28 x 28. We experiment with LeNet architecture given in Table For local training each FSL/FL round, each client uses 2 epochs. For training weights (experiments with FedAvg, SignSGD, TopK), we use SGD optimizer with learning rate of 0.01, momentum of 0.9, weight decay le-4, and batch size 8. For training supermasks (experiments with FSL), we use SGD with learning rate of 0.4, momentum 0.9, weight decay le-4, and batch size 8.
CIFARIO (Krizhevsky & Hinton 2009) is 10-class classification task with 60,000 RGB images (50,000 for training and 10,000 for testing), each of size 32 x 32, We experiment with a VGG-like architecture given in Table 4 which is identical training in each FSL/FL round, each client uses 5 epochs. For training weights (experiments with FedAvg, SignSGD, TopK), we use SGD with learning rate of 0.1, momentum of 0.9, weight decay of le-4, and batch size of 8. For training supermasks (experiments with FSL), we optimize SGD with learning rate of 0.4, momentum of 0.9, weight decay of le-4, and batch size of 8.
what Raaaanujan et al. (2020) used. For local
FEMNIST (Caldas et al. 2018 Cohen et al. 2017) is a character recognition classification task with 3,400 clients, 62 classes (52 for upper and lower case letters and 10 for digits), and 671 ,585 gray-scale images. Each client has data of their own handwritten digits or letters. We use LeNet architecture given in Table 4 For local training in each FSL/FL round, each client uses 2 epochs. For training weights (experiments with FedAvg. SignSGD, TopK), we use SGD with learning rate of 0.15, momentum of 0.9, weight decay of 1e-4, and batch size 10. For training supermasks (experiments with FSL), we optimize SGD with learning rate of 0.2, momentum of 0.9, weight decay of le-4, and batch size of 10.
15

---

Under review as a conference paper at ICLR 2022
B.2 HYPERPARAMETERS TUNING
We optimize the hyperparameters based FSL and other baselines independently. The hyperpa- rameters that we used our experiments are tuned in scenario with no malicious clients. Table B.I shows the performance of FSL. and other baselines CIFAR10 (distributed over 1000 users using Dirichlet distribution) for different values of hyperparameters when there are 10% malicious clients among the clients. This table shows the robustness of FSL still persists even if we change the hyper- parameters. We reported mean of accuracies and standard deviation of accuracies for all the clients the final FSL round.
B.3 NON-IID DATA DISTRIBUTION
Considering the heterogeneous data in the real-word cross-device FL, similar to previous works (Reddi et al. 2020 Hsu al. 2019), we distribute MNIST and CIFAR1O among 1,000 clients in a non-iid fashion using Dirichlet distribution with parameter / 1. Note that increasing results in more iid datasets. Next, we split datasets of each client into training (80%) and test (20%). At the end of the FL rounds, we calculate the test accuracy of each client for its test data, and we report the average of test accuracies all the clients. We run all the experiments for 2000 global rounds of FSL and FL and select 25 clients in each round.
Using Dirichlet Distribution:
Assigning only two classes to each client: McMahan et al. (017) used a more extreme hetero- geneous data assignment. For assignment of MNIST and CIFARIO among 1000 clients using this Non-iid-ness method, we sort all the training and validation data inside MNIST and CIFAR1O, 10, then partition them into 2000 shards. This means that each shards of training MNIST has 30 images and each CIFAR10 shard has 25 images. Then we assign two random shards to each client resulting in each client have most data of two classes, and in CIFAR 10 experiments, each client has 50 training images, and 10 test images, and in MNIST experiments, each client has 60 training images and 10 test images. We only use this assignment in Section
B.4 BASELINE FL ALGORITHMS
Federated averaging In non-adversarial FL settings, i.e., without any malicious clients, the
dimension wise Average (FedAvg) (Konečný et al.] [2066; [cMahan et al. (217)) is an effective AGR. fact, due to its efficiency, Average is the only AGR implemented by FL applications in practice (Ludwig al. 2020 Paulik et al. 2021).
SignSGD quantization method used in distributed learning to compress each dimension of updates into bit instead of 32 64 bits. To achieve this, in SignSGD (Bernstein al. (019)) the clients only send the sign of the gradient updates to the server, and the server runs a majority vote them. SignSGD is designed for distributed learning where all the clients participate in each round, so all the clients are aware of the most updated weight parameters of the global model. However, using SignSGD in FL just provides benefit in upload bandwidth, but achieve good overall performance of the global model, the server should send all the weight parameters (each of 32 bits) the newly selected clients in each round. This makes SignSGD very efficient in upload cost, but it is as inefficient as FedAvg in download.
TopK is a sparsification method used in distributed learning that transmits only few elements in each model update to the server. In TopK (Aji & Heafield 2017] Alistarh et al. 2018a), the clients first sort the absolute values of their local gradient updates, and send the Top K% largest gradients update dimensions to the server for aggregation. Topk suffers from the same problem as SignSGD: for performance reasons, the server should send the entire updated model weights to the new selected clients.
B.5 MODEL POISONING ATTACK FOR ROBUSTNESS EVALUATIONS
To evaluate robustness of various FL algorithms, we use state-of-the-art model poisoning attack proposed by Shejwalkar & Houmansadr (2021) in our robustness experiments. The attack proposes general FL poisoning framework and then tailors it specific FL settings. It first computes an average à the available benign updates and perturbs it in a dynamic, data-dependent malicious direction to compute the final poisoned update V V yw. DYN-OPT finds the largest y that
16

---

Under review as a conference paper at ICLR 2022
Table 4: Performance of FSL with different hyperparameters trained CIFARIO (distributed over
1000 clients using Dirichlet distribution). Method
hyperparameter
value
Test Accuracy with 10% malicious
78.4 (12.6)
batch size
8
79.0 (12.4)
16
76.4 (13.6)
79.8 (12.2)
local epochs
5
79.0 (12.4)
FSL.
10
78.2 (12.6)
0.1
73.5 (13.4)
0.2
82.4 (12.1)
learning rate
0.3
83.11 (1L.8)
0.4
79.0 (12.4)
0.5
77.5 (13.1)
FedAvg
10.0 (10.1)
TopK
10.0 (10.1)
6
55.5 (14.5)
batch size
56.3 (16.0)
16
37.7 (15.6)
2
41.0 (1..4)
local epochs
56.3 (16.0)
FedAvg Trimmed-mean
21.0 (9.9)
0.01
34,0 (15.5)
0.05
38.3 (15.3)
Icarning rate
0.1
56.3 (16.0)
0.15
10.0 (10.0)
0.2
10.0 (10.0)
6
19.0 (12.5)
batch size
8
58.8 (15.8)
36.7 (14.8)
2
46.1 (15.9)
local epochs
5
58.8 (15.8)
FedAvg Multi-Krum
24.3 (11.7)
0.01
15..3 (11.7)
0.05
50,0 (16.2)
Icarning rate
0.1
58.8 (15.8)
0.15
15.4 (11.9)
0.2
10.0 (10.0)
33.1 (15.6)
batch size
8
39.7 (15.9)
16
10.2 (10.1)
10.2 (10.5)
local epochs
5
39.7 (15.9)
SignSGD
10
41.5 (16.0)
0.01
44.2 (15.8)
0.05
41.9 (15.5)
learning rate
0.1
39.7 (15.9)
0.15
35.8 (15.3)
0.2
10.2 (10.1)
17

---

Under review as a conference paper at ICLR 2022
successfully cireumvents the target AGR. DYN-OPT is much stronger, because unlike STAT-OPT, it finds the largest y and uses dataset tailored w.
C MISSING EXPERIMENTS
C.I FSL: INITIALIZATION MATTERS
Table 5: Comparing the performance of FSL with different random weight initialization algorithms with the performance of vanilla FedAvg for cross-device setting. Using Singed Kaiming Constant as weight initialization gives the best performance for all the datasets.
Algorithm
Metric
Dataset
FedAvg
FSL
Winit
Xx
Nx
UK
Mean
98.8
96.6
98.7
98.8
MNIST
STD
3.1
5.2
3.2
3.1
LeNet
Min
75.0
57.1
75.0
75.0
N=1000
Max
100
100
100
100
Mean
85.4
63.6
82.0
85.3
CIFARI0
STD
11.2
15.6
11.9
11.3
Conv8
Min
33.3
0
0
33.3
N=1000
Max
100
100
100
100
Mean
85.8
69.2
82.9
84.2
FEMNIST
STD
10.2
14.2
11.1
10.7
LeNet
Min
10.0
14.3
7.1
N=3400
Max
100
100
100
100
In FSL, the weight parameters are fixed throughout the FSL protocol and they are initialized ran- domly at the beginning of the protocol. is very important to appropriately initialize the weights since the clients will find the subnetworks within these weights. We use three different distribution for initializing the weight parameters as follows:
Glorot Normal (Glorot & Bengio 2010) where denote by Xyy Previous work Zhou et al. (209 used this initialization to demonstrate that subnetworks of randomly weighted neural networks can achieve impressive performance.
Kaiming Normal (He et al. 2015) where we denote by N&. defined as NK N (o, 2//me11 where N shows normal distribution. ny shows the number of parameters in the Eth layer.
Singed Kaiming Constant (Ramanujan et al. 2020) where all the wights are constant but they are assigned (+, randomly. This constant, o, standard deviation of Kaiming Normal. We
show this initialization with UK as we are sampling from {-a, +o} where
(2/mne-1)
3/shos the results of running FSL for three datasets under the three aforementioned initializa- tion algorithms. We compare FSL with FedAvg and report the mean, standard deviation, minimum, and maximum of the accuracies for the clients' local subnetwork (for FSL.) and local models (for FedAvg) at the end of FSI/FedAvg training. As we can see under three different random initial- ization, using Signed Kaiming Normal (Ux) results in better performance. We note from Table 5 that FSL with Signed Kaiming Normal (Uk) initialization achieves performance very close to the performance of FedAVg.
Note that, since the FSL clients update scores in each round, unlike initialization of weights, initial- ization of scores does not have significant impact the final global subnetwork search. Therefore, we do not explore different randomized initialization algorithms for scores and simply use Kaiming Uniform initialization for scores.
18

---

Under review as a conference paper at ICLR 2022
FodAeg
FSL
Foddng
FSL
Podiog
FSL
99.0
83.0
98.5
82.5
98.0
60
80.00
97.5
40
20
96.5
20
60
20
410
60
30
20
40
50
80
(a) MNIST
(b) CIFARIO
(c) FEMNIST
Figure 4: Comparing performance of FSL for different subnetwork sizes. & (x-axis) shows the % of weights that each client is including in its subnetwork, test accuracy (y-axis) shows the mean of accuracies for all the clients on their test data. The chosen clients in each round send all the ranks to the server. FSL with subnetworks of E [40%, 70%] result in better performances.
Ramanujan al. (2020) also considered these three initialization find the best subnetwork in centralized machine learning setting. They also showed that using Singed Kaiming Normal gives the best supermasks. Our results align with their conclusions, hence we use Singed Kaiming Normal to initialize the weights and Kaiming Uniform to initialize the scores of global supernetwork.
C.2 PERFORMANCES OF FSL WITH VARYING SIZES OF SUBNETWORKS
In FSL, each client uses Edge-Pop Algorithm (Ramanujan et al. 2020) and their local data to find local subnetwork within a randomly initialized global network, which we call supernetwork. Edge- Pop algorithm use parameter & which represents the % of all the edges in a superettork which will remain the final subnetwork. For instance, within supernetwork that has half the number of edges as in the supernetwork.
50% denotes that each client finds a subnetwork
Figure illustrates how the performance subnetwork; note that, all of the clients collaborate to find the global subnetwork. We train nine FSL models with E {10, 20,30, 30, 40, 50, 60, 70, 80, 90%% and a FedAvg model (shown using a horizontal line); FedAvg model updates all the weights, hence it is supermask with k 100%.
the global subnetwork in FSL varies with the size of
C.3 PERFORMANCES OF FSL WITH DIFFERENT HETEROGENEOUS DATA DISTRIBUTION METHODS
Table 6 shows the performances of FSL and FedAvg using different methods of non-iid assignment. We distribute the data between 1000 clients with two methods: (I) Dirichlet distribution with similar to (Reddi et al. 2020 Hsu et al. 2019) and (II) each client has data of 2 random classes sim- ilar to (McMahan et al. 2017). In this table, we can see that FSL can achieve the same performance of FedAvg in different heterogeneous data distributions.
D MISSING DETAILS OF EDGE-POPUP AND FSL ALGORITHM
Suppose a fully connected neural network, there are L layers and layer E [1, L] has ne neu- rons, denoted by Ve {Vi ... V ). If I, and Z, denote the input and output for neuron respectively, then the input of the node v is the weighted sum of all nodes in previous layer, i.e., Edge-popup
I, Eneve- W., Here, W.. is the weight of the edge connecting algorithm tries to find subnetwork E, the imput for neuron would be: I.- Σ (u,))E W..Z..
Updating scores. Consider edge End that connects two neurons u and W.. be the weight of Eue. and sav be the score assigned to the edge E., by Edge-popup algorithm. Then the edge-popup algorithm removes edge Eur from the supermask if its score Sue is not high enough. Each iteration of supermask training updates the scores of all edges such that, if having an edge E,, in subnetwork reduces loss (e.g., cross-entropy loss) over training data, the score 8uo increases.
19

---

Under review as a conference paper at ICLR 2022
Table 6: Comparing the performance of FSL. and FedAvg for cross-device setting using methods of data assignment. We distribute the data between 1000 clients with two methods: (I) Dirichlet distribution with and (II) each client has data of 2 random classes.
Algorithm
Dataset
Type of Non-IID
Metric
FedAvg
FSL
Mean
98.8
98.8
STD
3.1
3.1
Dirichlet Distribution 3
Min
75.0
75.0
MNIST LeNet N=1000
Max
100
100
Mean
98.4
98.3
STD
4.3
4.1
Randomly 2 classes assigned to each client
Min
70.0
80.0
Max
100
100
Mean
85.4
85.3
STD
11.2
1 11.3
Dirichlet Distribution 3
Min
33.3
33.3
CIFARIO Conv8
Max
100
100
Mcan
70.6
70.9
N=1000
STD
21.9
19.2
Randomly classes assigned to each client
Min
10.0
Max
100
100
The algorithm selects top k% edges (i.e., finds a subnetwork with sparsity of k%) with highest scores, so T reduces to T = Eveve W Zuh(ee( where h(.) returns 1 if the edge exists in top- k% highest score edges and () otherwise. Because of existence of h(-), which is not differentiable, impossible to compute the gradient of loss with respect Sue- Recall that, the edge-popup algorithm use straight-through gradient estimator (Bengio et al.) 2013) to compute gradients. In this approach, I(-)) will treated as identity the backward pass meaning that the upstream gradient (i.c.. SI,) goes straight-througe h(). Now using chain rule, we can derive
aL ar.
SI, Usu.
Wav where L is the loss to minimize. Then SGD with step size r) to update scores as AL 8T.
Suo + Sun a0.
8L Z, W....
uv-
Ramanujan et al. (2020) proved that when edge (a, b) replaces (c, b) in layer f and the rest of the subnetwork remains fixed then the loss of the supermask learning decreases (provided the loss is sufficiently smooth). Motivated by their proof, we can show when these two edges are swapped in FSL, the loss decreases for FSL optimization too.
Theorem 1: when edge (a, b) replaces (c, b) in layer l and the rest of the subnetwork remains fixed then the loss of the FSI. optimization will decrease (provided the loss sufficiently smooth).
proof. First, we know that the optimization problem of FSL is as follow:
min F(0 R
Rgy min R₂
X ( m) s.t.
(5)
Rg < and m Rg
(6)
where X; shows the importance of the 8th client in empirical risk minimization which A; = x gives same importance
all the participating clients. m is the final mask that contains the edges of top ranks, and L; is the loss function for the ith client. 0" @ m shows the subnetwork inside the random @" that all clients unanimously vote for. In this optimization, the FSL clients try minimize F by finding the best global ranking Rg-
We now wish to show F(6 R(+1) < F(8", Rt) when in FSL round t+ 1, the edge (a, b) replaces (c. b) in layer & and the rest of the subnetwork remains fixed. Suppose global rank of edge (a, b) was Rt (a, b)] and global rank of edge (c, was R2 [(c, b)] in round f, have:
20

---

Under review as a conference paper at ICLR 2022
[a Ry [c R2 [{a > (c,b)
where the order of all remaining global ranks remain fixed, and only these two edges are swapped in global ranking. Now let 4. shows the score of weight was in round & and client jth and sab 1-1, shows the updated score of it after local training. As our majority vote, calculating the sum of the reputation of edges we will have:
N
N
(9)
i=
bbb
(10)
We also know that Edge-popup algorithm updates the scores in the 8th client as follow:
0L Za
ab
1,,,
sab
11 aIa
Wab
(1I)
Based on 10 and
11
we can say:
N
N
N
4+,i
.+,,
(12)
ab
cb
ab
cb
2m
im
i=
We also know that:
N
N
θL
abb
141,
abb
1,
=
Σ
0T:
z Wab
(13)
1=1
N
N
aLi
8
11,,
1.
Σ
-1
7: cb
(14)
aTi
Based on 12
13 and 14
we can say:
N
OL!
N
(aL)
W:W aig
Z Wab
(15)
arg
So based on I5 and what RRaaanujan et al. 2020) proved for each supermask training we can show 16 We assume that loss is smooth and the input to the nodes that their edges are swapped are close before and after the swap.
N
N Σ (L mm))
(L. (
(16)
21

---

Under review as a conference paper at ICLR 2022
40
FSL(Lowerbuund)
(5S)))0%)
Communicicaioo CostiCB)
FedAvg
SFSL(10%)
30
FSL
SignSGD
20
10
2000
4000
6000
8000
10000
Number Parameters
Figure 5: Communication cost Analysis. Please note that the download communication cost of all SFSLs would be the same as FSL.
that means:
F(O", R F(O",
(17)
E MISSING DETAILS ABOUT COMMUNICATION COST COMPARISON
One of the features of the FSL training is its communication efficiency. In Section 5.2 we show that the FSL clients send and receive rankings, the communication cost will be EiE[L] The log(ne) bits per client. In this section, we are providing lower bound on the FSL communication cost, and then compare it with FedAvg and SignSGD.
Lowerbound of communication cost of FSL: Since the FSL clients send and receive layer- wise rankings of indices, i.c., integers E [0, ny 1]. for layer f, there are nz! possible permutations for layer & E [Z.]. If we use best possible compression method in FSI., an FSI. client needs to send and receive Σtelzj log(nz!) bits. Therefore, the download and upload bandwidth for each FSI.
client would be Exin(a) log (ng (ne (ng--1 1) * 2 1) ΣiELE E log(i) bits. Please note that in our experiment, FSI. clients send and receive the rankings without any further compression, and Ere(r) E log(t) just shows lower-boure of communication cost of FSL. In Section 6.1 measure the performance and communication cost of FSL with other existing FL compressors signSGD (Bernstein et al., (019) and TopK (Aji & Heafield, 2017; Allistarh et al. 2018a). In Fig- 5re we compare the communication cost of one client per FL round for FedAvg, SignSGD, and different variant of FSL for different number of parameters.
Similar work in this domain is LotteryFL (Li al. 2020a), personalization framework that each FL client learns a lottery ticket network (LTN) by pruning the base model using Lottery Ticket hypothesis (Frankle & Carbin 2019). In LotteryFL, each client sends and receives the update for its subnetwork, and at the end, they have an extra step for personalization. FSL is different from LotteryFL. as the FSL clients find subnetworks within random and fixed network and send the ranks of their subnetwork edges instead of what LotteryFL clients do that train their weights and find a subnetwork by freezing some weights and send their actual model update. LotteryFL is based on FedAvg that the clients can send any update to the server, which is vulnerable to the same attacks that existed for FedAVG. terms of communication cost, FSL is very close to LotteryFL. as they report 1,81x improvement over CIFARIO 10 which is close to FSL and SFSL(50%) which provide 1.53x, 3,09x improvement respectively over CIFARIO.
F ADDITIONAL. COMPARISONS
Figure is showing the learning curve of FSL for different numbers of local epochs for CIFARIO experiment. On the x-ais have accumulated communication cost: 13.1 x 2 25 MB where e is the FSL round, 13.1MB is the cost FSL per client, is for download+uuload cost, and 25 clients selected in each round.
22

---

Under review as a conference paper at ICLR 2022
Table 7: The effect of other settings performance of FSL trained CIFARIO distributed 1000 clients using Dirichlet distribution. The bold shows the value we used in our experiments.
Method
hyperparameter
value
Test Accuracy with 10% malicious
15
84.8 (11.3)
Number of participants (n)
25
85.3 (11.3)
50
84.9 (11.2)
82.2 (12.0)
FSL
local epochs (E)
5
85.3 (11.3)
10
83.5 (11.9)
(11.3)
Non-iid degree (3)
10
85.6 (11.1)
100
85.6 (10.9)
(E=2)
FSL (E=5)
FSL (E=10)
FSL (E=2)
FSL (E=5)
FSL (E=10)
70
2,00
1%6
1.75
Test
1.00
20
10
200
400
600
800
1000
1200
200
400
600
800
1000
1200
Accumulated Communncaiton cost (GB)
Accurnulsted Communicaiton cost (GB)
(a) CIFARIO (Test Accuracy)
(b) CIFARIO (Test Loss)
Figure 6: Comparing performance of FSL for different local epochs.
Table showing the effect of other settings on performance of FSL trained on CIFAR1O distributed over 1000 clients using Dirichlet distribution. The bold shows the value used in our experiments.
23


Reviews:
[{"review_id": "jUnwfyZT9df", "reviewer": "Reviewer_XrNo", "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": "# Strengths\n* The idea of introducing supermask learning (on a randomly initialized network) for federated learning is interesting.\n* The algorithm leverages the ideas like edge ranking order and majority voting to achieve the reduced communication cost, robustness to malicious clients. Some numerical experiments are performed on these aspects to justify the performance gain.\n\n# Weaknesses\n* The authors may ignore some prior works that attempt to introduce the idea of masking to federated learning, like [1].\n* The baselines are weak and potentially lead to unfair comparison. Without considering stronger baselines, it is hard to justify the performance gain of the proposed method.\n    * A more recent communication-efficient techniques developed for distributed learning need to be considered, e.g., at least the error-feedback framework [2, 3, 4] should be integrated with these compression techniques for FL [10, 11].\n    * The paper only considers comparing with FedAvg under non-iid local data distribution. A line of recent studies, e.g. SCAFFOLD [5], FedProx [6], FedNova [9], server Momentum-based FedAvg [7, 8], are ignored. Authors are also encouraged to comment the integrability of these FL methods on the proposed FSL method.\n    * It would be great if the authors can provide additional comparison results in terms of different local update updates, number of client participation ratio, local data non-iid-ness, etc.\n    * In the appendix, same hyper-parameters are used by all methods. It would be great if the authors can at least provide one Table/Figure to justify that tuning hyper-parameters for all methods will not change the performance gain of the proposed method.\n\n\n# Reference\n1. Dynamic Sampling and Selective Masking for Communication-Efficient Federated Learning, https://arxiv.org/abs/2003.09603, 2020.\n2. Error Feedback Fixes SignSGD and other Gradient Compression Schemes, ICML 2019.\n3. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback, NeurIPS 2021.\n4. Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training, ICLR 2018.\n5. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, ICML 2020.\n6. Federated Optimization in Heterogeneous Networks, MLSys 2020.\n7. Faster Non-Convex Federated Learning via Global and Local Momentum, 2020.\n8. Adaptive Federated Optimization, ICLR 2021.\n9. Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization, NeurIPS 2020.\n10. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees, 2021\n11. Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients, Feb. 2021.", "summary_of_the_paper": "The paper proposes to collaboratively learn a supermask within a randomly initialized neural networks, instead of learning the model parameters.\nThis idea is interesting and the authors verify its effectiveness on MNIST, CIFAR and FEMNIST, with the benefits of reduced communication cost and robustness to malicious clients.", "summary_of_the_review": "In general this paper is interesting; but before the acceptance of the paper, the authors need to provide additional numerical comparison over other strong baselines in the rebuttal (as pointed out in the main review section).", "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": "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": {}}, {"review_id": "cUSanxERx1Y", "reviewer": "Reviewer_q5LC", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n1)\tThis paper combines “supermask” techniques with FL and improve the communication efficiency and robustness of FL at the same time.\n2)\tThis paper provides thorough empirical results to support its claim about the improvement of communication efficiency and robustness.\nWeaknesses:\n1)\tThe experimental settings are not hard enough to evaluate the performance of FSL. There is no doubt that there is information loss when the devices transmit only the ranking of scores. This kind of information loss is not serious when the rankings on different devices are similar (the local subnetwork structures are similar due to similar data distributions). In this paper, the user uses Dirichlet distributions to construct non-IID data for MNIST and CIFAR10. Even though the data distributions are different across devices, each device still holds all classes of data and local subnetwork structures would not show significant difference. And I guess the robustness results have the same problem since the authors use a voting mechanism to update the global ranking. I am wondering whether FSL would perform well under the non-IID setting in FedAvg paper, where each client only has two classes of data rather than all classes of data.\n2)\tThe improvement over baselines is not significant on some dataset. For example, “Top-K 10%” achieves even higher accuracy than “FSL” with lower communication cost on FEMNIST dataset.\n3)\tThe idea of utilizing “supermask” seems novel, but this paper seems just simply combining “supermask” with FL. It is okey to do “A plus B” things, but you need to provide some scientific contributions like providing a theoretical analysis about why “supermask plus FL” works, and what challenges that you solved make it deserve an acceptance by a top avenue like ICLR. \n", "summary_of_the_paper": "This paper exploit the \"supermask\" technique to improve both robustness and communication efficiency in federated learning. The collaborating clients only share the local subnetwork based on the rankings of network edges, and the server performs aggregations over the local subnetworks of all participating clients. The authors also provides theoretical and empirical study on how the proposed method can improve robustness and communication efficiency.", "summary_of_the_review": "This paper utilizes “supermask” technique in FL to improve communication efficiency and robustness simultaneously and provides thorough empirical studies. However, it seems simply combines “supermask” and FL without solving any challenges nor providing theoretical analysis about why this can work. In addition, the experimental settings are not hard enough to judge the usability of the algorithm proposed by this paper. Based on the experimental settings and the lack of scientific contributions, I would give a negative score. If the authors can solve these two major concerns, I am delighted to increase my score.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Gr3wYQHrn0S", "reviewer": "Reviewer_JJjz", "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 enjoyed reading this paper. The authors accompany their explanation with an illustrative example which helps understanding. \nRegardless, several things remain unclear.\n\nHigh-level: Throughout the text the authors refer to robustness and communication as 'the' important issues in FL. I would argue that they are two important issues, but there are also many other important issues, such as differential privacy, efficiency, data/hardware/network heterogeneity, questions of fairness and representation among many others. \n\nCommunication:\n- I am confused by the authors calculation of the communication requirements of SFL (Appendix E). \nIn order to index all possible permutations of a layer with $n_l$ weights, we need $\\log_2(n_l!)$ bits. the computation of that number does not require Stirling's approximation, since $\\log(n_l!) = \\log(n_l*(n_l -1) * ( n_l - 2)* ... * 2 * 1) = \\sum_1^{n_l} \\log(i)$.\nUsing the provided numbers in Table 3 for the Cifar10 model, I compute \nsum([np.ceil(np.sum(np.log2(np.arange(2,l+1))))/(8 * 1024 * 1024) for l in layers]) = 11.698538184165955mb for a single message, instead of the 13.1MB that the authors claim. \n- Unfortunately the authors ignore a mayor practical aspect of this approach. What is the computational overhead in finding the appropriate index for a given permutation? I landed on the Lehmer code (https://en.wikipedia.org/wiki/Lehmer_code#Encoding_and_decoding) for computing the index, which seems to scale quadratically in $n_l$. Using https://gist.github.com/lukmdo/7049748 for a quick test, encoding a random permutation of length $2359296$ takes approx 42minutes on a modest Desktop-CPU. I would encourage the authors to discuss this in light of the cross-device setting and resource-constrained devices.\nThe alternative approach of encoding a given permutation as list of integers would require $n_l*\\log(n_l)$ bits, which amounts to \nsum([(l*np.ceil(np.log2(l)))/(8*1024*1024) for l in layers]) = 13.069404602050781mb. Now that I compute that number I realise that's the budget the authors claim, i.e. they seem to not index the permutation. I encourage the authors to clarify. \n\nRobustness to Attacks:\n- The authors claim that worst-case attack on FSL requires inverting the order of rankings. I would argue that a stronger attack might be considered when considering potential effects across all layers of the network. I.e. can a malicious client cause more damage by coordinating across layers? \n- Algorithm 3 in Appendix A.1 seems to suggest that Voting in Line 11 happens only across malicious clients. This goes in line with Argument 3)in the main-text concerning collusion. Why is this form of collusion the strongest form of attack? What are the consequences of each client independently reversing their rankings? On the other hand, can there be a stronger attack by not performing Vote, followed by reversing the order - and instead some other finding of consensus between malicious clients to maximally attack the model's performance?\n- Can you validate your theoretical curves in Figure 2 by measuring flips in your empirical experiments?\n\nSparse-FSL:\nThe authors discuss that client's don't send the bottom % of their rankings and the server assumes a reputation of 0 for those entries. In the end of section 6.1 the authors discuss that additionally, download-costs are reduced. Information about what the client's assume for the left-out entries is missing, however. \nIn the same paragraph, the authors argue that with 50% ranks sent, the communication is cut in half. Relating to above discussion about communication costs, there needs to be an encoding scheme behind this sparsification. I.e. if for $p\\%$ remaining rankings, you'd need $p n_l\\log_2(p n_l)$ for communicating the reduced rankings, plus a binary mask of $n_l$ bits. \n\nExperiments:\n- The authors state that they give 'mean of all client's test-accuracies'. Are those on fine-tuned local models? Are those weighted by local client's data-set sizes? Alternatively, keep the test-set on the server and evaluate the test-set on the server. Afaik this is the standard practice. \n- I examined the CIFAR10 notebook provided as supplementary. The way the authors split the data cross clients leads to some data-points not being used at all apparently, i.e. te_count + tr_count = 59886\n- Please provide your hyper parameter selection strategy: Did you optimize hyper parameters across baselines and FSL independently? Which ranges did you consider?\n- Based on how many seeds did you report the mean+std (Table 1 and 2). The deviations seem to be very high, i.e. for many experiments, the averages lie within the std of each other. It might be better to report the standard-error and repeat experiments more often to get a more reliable estimate. Additionally, it might also be a good idea to average evaluation-accuracies across the last few epochs to get a more robust estimate. Please plot stderror on below mentioned learning curves accordingly \n\n\nBaselines:\n- For SignSGD, do you communicate the bit-mask ever local gradient-step as originally proposed - or do you communicate a bit-mask after ever local Epoch E, as would be in line with Federated Learning? SignSGD cannot really be assumed to be a proper Federated algorithm due to the frequent communication - indeed it was proposed for data-centre applications. \nIn case these stated Upload / Download costs are not happening at the same frequencies as for e.g. FedAvg of FSL, Table 1 is misleading.\n- Please plot learning curves where on the x-axis we have accumulated communication-budget and on the y-axis we see validation accuracy.\n- Apart from binarising gradients, there is also the option to quantise gradients to b bits. A basic baseline for update expression is to do group-wise (e.g. per-layer) quantization to a b-bit grid that uniformly divides [min(x),max(x)] for x being the group of parameter-updates. The min/max values of the grid need to be communicated to the server. Stochastic quantization is important here. \nFurther compression can be achieved by performing vector-quantisation. A relatively recent work in this domain is HSQ (https://arxiv.org/abs/1911.04655), which targets the FL setting explicitly. \n\n\nSome minor aspects:\n- In Algorithm 3 you index with $mu$, as well as only $u$ and only $m$. What is the meaning of these individual or joint indices?\n- In Appendix B.2 and the main text, you should describe your sampling approach better, i.e. you never mention that you assign *labels* based on the Dirichlet samples. A convenient source to cite (as well as maybe improve your implementation with) is https://arxiv.org/abs/2003.00295. \n- Why are the authors citing Minka(2000) when mentioning the Dirichlet distribution? The cited work discussed parameter estimation for the Dirichlet distribution, which is not on-topic here. \n- page 14 bottom, 'sparsification' no capitalisation \n-  Introduction First paragraph: How is 'Google' an example of a server?\n- When describing a genderless object, such as a client, one should use 'their' instead of 'his' or 'her'. E.g. Abstract 3 introduction: ... send their local edge ranking...; Also: 3.1: '... on their data...' \n\nFinal disclaimer: I am not an expert in defences and attacks in the FL setup and will defer to other reviewers in their evaluation", "summary_of_the_paper": "The authors show how to apply the method of Ramanujan et al. (2020) and Wortsman et al. (2020) to the federated setting. They show that the proposed method, FSL, has desirable properties in reducing communication overhead and improving robustness to malicious attacks on the resulting model compared to other approaches. \n", "summary_of_the_review": "In Summary, the authors apply an existing algorithm to the FL setup, including a novel voting-algorithm that applies to this algorithm. The execution of the paper has some flaws that I would like to see corrected before the paper is ready for publication.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5J6Cr-pVvk_", "reviewer": "Reviewer_bj9t", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strength\n\n1. A federated supermask learning is proposed for improving the communication efficiency of federated learning\n\n2. The edge ranking communication improves the efficiency of the federated supermask learning itself.\n\n3. Extensive evaluation on three real datasets demonstrate the superior performance of the proposed approach.\n\nWeakness\n\n1. The authors leverage the EdgePop Algorithm [2] for model pruning. The original paper is only able to prove that switching edges according to iterated edge scores can reduce the loss on randomly initialized networks. The connection between the EdgePop Algorithm and the model pruning remains unclear.\n\n2. This paper is essentially a pruning-before-training algorithm. However, pruning-after-training and pruning-during-training techniques often achieve the better approximation. More detailed analysis are expected to explain the motivation and benefits of the choice, and whether the proposed method is able to guarantee the model accuracy.\n\n3. Utilizing network pruning to accelerate the FL training for reducing the communication cost is not a new research problem [1]. The authors should discuss recent advances in federated learning. In addition, the authors fail to discuss and compare with existing pruning-before-training techniques.\n\n4. The paper lacks of enough novelties, since two main components of the paper, EdgePop and voting, are from existing techniques.\n\n[1] Yuang Jiang et al. \"Model Pruning Enables Efficient Federated Learning on Edge Devices\". In: CoRR abs/1909.12326 (2019).\n\n[2] Vivek Ramanujan et al. \"What's Hidden in a Randomly Weighted Neural Network?\" In: 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020. Computer Vision Foundation / IEEE, 2020, pp. 11890–11899.", "summary_of_the_paper": "This paper presents a pruning-before-training algorithm for improving the communication efficiency of federated learning. In each iteration, all local devices with the same initial weights perform the pruning on their own local datasets. The edge scores produced by local devices are aggregated by the server. The order of the edge scores will be used in the next iteration of score initialization process. After the pruning convergence, the edges are pruned correspondingly and the federated learning model is trained on the pruned network.", "summary_of_the_review": "Overall, the well designed structure makes the workﬂow clear and easy to follow, but the further analysis and discussion are expected to clarify the contributions in the techniques as well as in the evaluation section.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper brings the "supermask" idea used in neural architecture search to the application of federated learning, here represented by a single mask of a larger network. The method can be seen as pruning-before-training, or more precisely pruning-instead-of-training. It is a simplified version of the related works LotteryFL, PruneFL or FedMask, with the difference that here no personalization and no training of the weights is performed, only learning of a global mask. Related work discussion should be improved. While the communication efficiency impact of the method seems minor but positive, the interesting point is that authors here argue that masking will improve robustness to adversarial participants during training. 

Unfortunately no theoretical evidence is provided for success of training, in the sense of Byzantine robustness. It is known that robust training can be attacked with small perturbations correlated over time (e.g. 'little is enough'), so also over layers, two important aspects which are ignored here - as voting here is only analysed static at a single time-point. As pointed out by reviewer JJjz, the considered attack (inverting ranking) is far from being formally proven to be the strongest one, and we would have wished for a more precise discussion of these issues as the target of the paper seems to be mainly robustness.

Concerns on the paper also remained on the level of novelty, as it only uses existing building blocks which are more or less directly applicable from the centralized setting, and on the limited contributions towards formal robustness, and on the limited discussion of related work mentioned by several reviewers, only some of which we were able to address in the discussion phase.

We hope the detailed feedback helps to strengthen the paper in the future.
Decision: Reject