Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Strengths:
1)	This paper combines “supermask” techniques with FL and improve the communication efficiency and robustness of FL at the same time.
2)	This paper provides thorough empirical results to support its claim about the improvement of communication efficiency and robustness.
Weaknesses:
1)	The 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.
2)	The 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.
3)	The 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. 

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: Strength

1. A federated supermask learning is proposed for improving the communication efficiency of federated learning

2. The edge ranking communication improves the efficiency of the federated supermask learning itself.

3. Extensive evaluation on three real datasets demonstrate the superior performance of the proposed approach.

Weakness

1. 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.

2. 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.

3. 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.

4. The paper lacks of enough novelties, since two main components of the paper, EdgePop and voting, are from existing techniques.

[1] Yuang Jiang et al. "Model Pruning Enables Efficient Federated Learning on Edge Devices". In: CoRR abs/1909.12326 (2019).

[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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to collaboratively learn a supermask within a randomly initialized neural networks, instead of learning the model parameters.
This 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.
main_review: # Strengths
* The idea of introducing supermask learning (on a randomly initialized network) for federated learning is interesting.
* 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.

# Weaknesses
* The authors may ignore some prior works that attempt to introduce the idea of masking to federated learning, like [1].
* 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.
    * 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].
    * 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.
    * 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.
    * 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.


# Reference
1. Dynamic Sampling and Selective Masking for Communication-Efficient Federated Learning, https://arxiv.org/abs/2003.09603, 2020.
2. Error Feedback Fixes SignSGD and other Gradient Compression Schemes, ICML 2019.
3. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback, NeurIPS 2021.
4. Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training, ICLR 2018.
5. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, ICML 2020.
6. Federated Optimization in Heterogeneous Networks, MLSys 2020.
7. Faster Non-Convex Federated Learning via Global and Local Momentum, 2020.
8. Adaptive Federated Optimization, ICLR 2021.
9. Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization, NeurIPS 2020.
10. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees, 2021
11. Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients, Feb. 2021.
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).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 

main_review: I enjoyed reading this paper. The authors accompany their explanation with an illustrative example which helps understanding. 
Regardless, several things remain unclear.

High-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. 

Communication:
- I am confused by the authors calculation of the communication requirements of SFL (Appendix E). 
In 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)$.
Using the provided numbers in Table 3 for the Cifar10 model, I compute 
sum([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. 
- 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.
The alternative approach of encoding a given permutation as list of integers would require $n_l*\log(n_l)$ bits, which amounts to 
sum([(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. 

Robustness to Attacks:
- 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? 
- 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?
- Can you validate your theoretical curves in Figure 2 by measuring flips in your empirical experiments?

Sparse-FSL:
The 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. 
In 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. 

Experiments:
- 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. 
- 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
- Please provide your hyper parameter selection strategy: Did you optimize hyper parameters across baselines and FSL independently? Which ranges did you consider?
- 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 


Baselines:
- 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. 
In case these stated Upload / Download costs are not happening at the same frequencies as for e.g. FedAvg of FSL, Table 1 is misleading.
- Please plot learning curves where on the x-axis we have accumulated communication-budget and on the y-axis we see validation accuracy.
- 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. 
Further 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. 


Some minor aspects:
- 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?
- 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. 
- 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. 
- page 14 bottom, 'sparsification' no capitalisation 
-  Introduction First paragraph: How is 'Google' an example of a server?
- 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...' 

Final 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_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.
review_title: null

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