Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies and the interesting problem of presence of both stragglers and adversaries in Federated Learning (FL), and proposes a solution that simultaneously addresses both issues. There's no question that the challenges considered in this paper are important to the FL community. The solution is based on grouping the late model update from stragglers, incorporating them into the model update, and performing an entropy-based filtering to find the adversarial updates. The paper has really interesting and comprehensive experiments, and it is backed by theoretical findings. 
main_review: The paper proposes an original solution to address both stragglers and adversaries in FL. The idea is novel and very interesting. The claims in the paper are backed by theory and comprehensive experiments. The sheer number of experiments and ablation studies are quite useful in evaluating the claims of the paper. The paper is well-written and it is easy to read

I have the following major comments:
1. Complexity: It seems like the proposed solution has high running time complexity. In particular, the equation (4) is calculated for every update. Computing entropy seems to be of high complexity (I might be wrong, but I get this feeling by reading the paper, as it goes through all data samples in public dataset and also depends on number of classes in dataset). Can the authors explain the asymptotic time complexity of their algorithm? How does the asymptotic time complexity of their algorithm compares to the other related algorithms mentioned in the paper?

2. Datasets: The authors have used the following datasets: MNIST, FMNIST, and CIFAR10. These datasets are not always representative of the challenges in FL. The gold standard benchmark for FL is LEAF: https://leaf.cmu.edu.

3. Question: It would be great if authors could provide more explanation/justification why entropy is a good measure? In the current writeup of the paper, it seems a bit ad-hoc why entropy is a good measure to detect some attacks. 

Some minor suggestions:
- when referring to supplemental material from the main text, it would be nice to refer to the exact section.
- some figures can be improve. E.g. fig 2c and fig 6 have data points all over the figure which makes the figures hard to read.

limitations_and_societal_impact: The authors do not discuss the limitations and negative societal impact of their work. I suggest authors think deeply about their scheme, and discuss these in the full manuscript. While it may not be very easy to find direct societal impact of this work, topics such as bias and discrimination (when we filter out adversaries, would it be possible that we are also discriminating?) might be easier to discuss. Also, I suggest the authors discuss the limitations of their work, as it would make their paper higher quality and would make it more honest about its assumptions and applicability of the solutions discussed in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a robust FL approach to deal with stragglers and adversaries in federated learning. Model grouping and staleness dependent weighting of models is done at the server to deal with stragglers. For model poising attacks, entropy-based filtering is proposed, where a client model entropy is calculated on a public dataset stored at the server. Same dataset is used to calculate loss of different client models at the server to identify clients contributing data-poisoned models. Theoretical bounds on convergence of the proposed method are obtained. Experimental results with three image classification datasets show that the proposed approach outperforms existing solutions to deal with stragglers and adversaries in FL. 
main_review: The paper has some novel ideas, in particular the idea of using both entropy-based filtering and loss-weighted averaging provides protection against both model poisoning and data poisoning attacks. The proposed approach Sagerflow integrates techniques for straggler mitigation and adversarial robustness in FL. The work is technically sound and performance of Sageflow is much better against the baselines. 
The paper is well written and the main ideas are explained clearly. 
Major comments: 
1. Line 39-40: "The presence ...aggregation schemes". This sentence is not clear. What if attackers are also the stragglers ? In that case avoiding stragglers will drive the attack ratio lower. Right ? 
2. The assumption that you have access to public data at the server is very strong. First you do not know what is the distribution of the data across all the clients. What should be the data distribution of this public data ? You are using this public data for entropy and loss calculations of individual client models to identify if they are potential adversaries or not. Basically if the entropy is high or the loss is high you mark the device as adversarial. But entropy and loss can be higher every for benign devices if their local data distribution is very different than data distribution at other clients. 
3. Higher entropy may not always mean an adversary. Since you are calculating entropy using public data, it may happen that higher entropy of a client model with public data is simply because the client has a very different data distribution than the public data. If this is the case then  filtering out the client model and not using it in global model update is not a good idea. Your global model may never be able to learn from the data local to the client. 
4. You are accounting for all the stragglers in your update, even the one which arrive very late. I am not sure if this is a good idea as too stale weights will only make the training unstable. Why not just set a threshold on stragglers even for your grouping approach ? 
5. How does Sageflow computational overhead at the server scales with number of clients ? With more clients you need to calculate entropy and loss for more number of clients using the public data. You should show scalability of Sageflow with increasing number of clients . 
6. Why were batch normalization layers ignored when training VG-11 and CIFAR10 ?
7. Line 283: What is parameter C ? 
8. Your results in the main paper are for very low staleness distribution (0,1,2). How does Sageflow perform with higher sateness values ? What is the final accuracy with Sageflow vs baselines in Figure 3. I would assume the benefits with Sageflow will diminish with high staleness and increased non-iid-ness of data distribution across clients. 
9. Use a better term instead of "model update poisoning".
limitations_and_societal_impact: The authors have not discussed limitations of their work. You need to provide example of scenarios where your approach may not work. Since your approach requires availability of public data at the server which is representation of global data, your approach will not work in FL settings where such data is not available or no knowledge about global data distribution is available .
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an approach, Sageflow, that jointly handles stragglers and Byzantine users in FL. Sageflow groups the users based on their staleness to handle stragglers and uses entropy-based filtering and loss-weighted averaging to provide Byzantine-robustness. This approach depends on the assumption that the server has access to a public dataset or the users share part of their data with the server to to identify the Byzantine users. Several experiments show that effectiveness of the Sageflow against some of the prior approaches.  
main_review: The proposed approach, Sageflow, handles stragglers and Byzantines jointly and prior works only focus on one of these two issues.
The idea of adapting the weights while aggregating the models based on the staleness is a nice idea as the the updates get less important as they become stale. Sageflow also combines between entropy-based filtering and loss-based averaging to handle Byzantine users, which is a good idea as each metric is more suitable for certain class of attacks. 

I overall like the proposed approach, but there are some issues that should be addressed as I discuss below.

1- There are some prior approaches that also use data sharing to handle Byzantine users such as [1, 2], but this paper does not compare with them.

While these works only deal with Byzantine users and do not consider stragglers, it is good to compare the proposed strategy with them. 
You should also consider comparing with the OracleSGD [2] as a reference. 

2- Line 124: "Note that the result sent from device $k \in U_t^{(i)}$ is the model after E local updates starting from $\mathbf w_i$". 

3- The entropy-based filtering requires performing inference using the models of the users and the public samples at the servers. This seems significant and there's no discussion on the complexity of doing so. What's the complexity of this?

4- I do not see why high entropy always means that the user in Byzantine, what if this is due to the non-IID data distribution?
It's mentioned later in line 162 that some attacks tend to make the entropy high as they make the predictions random, but some other attacks also may be biased toward specific class and hence they result in a low entropy. 

5- Line 139: It's mentioned that the active users who get a new request should ignore this request. It may be better for those users instead to respond to this request and ignore the computations that they are doing. This is intuitive as the fresh updates are more important than the stale updates. Why ignoring the new request is better? 

6- Line 170: You mention that your work can handle large number of adversaries, what's this number? and how do you decide the threshold for the entropy-based filtering? 

In Multi-Krum, 2f+2<N, what about Sageflow?

7- A limitation of this work also is that it does not consider the convergence for the non-convex case. 
This seems to be doable as a recent work considering a similar problem has done this analysis.
 
This work appeared after the deadline for NeurIPS, so it's not an issue at all that you have not considered it. 

8- Why did you ignore the batch normalization layers in Section 4? Please explain and add results with batch normalization as well. 

9-  Line 86: You mention independent, identically distributed, but this should have been mentioned the first time the term IID is used. 

10- Line 292 has a typo: "percantage"
 
[1] X. Cao et al. "FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping." arXiv preprint arXiv:2012.13995 (2020).

[2] S. Prakash, and A. S. Avestimehr. "Mitigating byzantine attacks in federated learning." arXiv preprint arXiv:2010.07541 (2020).

[3], J. Nguyen et al. "Federated Learning with Buffered Asynchronous Aggregation." arXiv preprint arXiv:2106.06639 (2021).


limitations_and_societal_impact: There is no discussion on the limitations and potential negative societal impact. Since the work focuses on Byzantine mitigation, it has a positive societal impact. Please also see my comments above for my suggestions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper addresses a scheme to protect federated learning against stragglers and adversaries at the same time. For straggler resistance, the authors propose to group and weight the model coefficients according to their age. For resistance against adversaries they propose entropy-based filtering and loss-weighted averaging. Combining these schemes leads to their proposed Sageflow approach. They also provide an upper bound on the expected loss function error after a fixed number of operations.
main_review: Although the paper is merely a combination of two different schemes, which seems to be orthogonal in its impact, the strengths of the paper are in my opinion the convincing numerical results compared to other schemes and the convergence analysis, which ties the performance limiting impacts of straggling and adversarial nodes together.

On the other hand, the paper has several weaknesses, mostly in terms of clarity. While the description with respect to the straggler resistance was near to me, I was not able to follow their strategy to combat adversarial actions:
- I do not understand the underlying model to eq.(4) and why publicly available data helps. Specifically, how is P^{(q)}_{x_pub} computed? I must be fundamentally misunderstanding the idea as we do have these training examples the corresponding labels available. So isn't the corresponding probability always 1? The authors need to clarify this point in their response. 
- In line 180, why is the loss function computed between the weights and the data x? This does not make any sense to me.
- The authors should also clarify the novelty of their approach. It is clear that perhaps the combination and the bound in Theorem 1 is new, but what about the individual approaches with respect to stragglers and adversaries?
- Gradient coding is another method to provide straggler resistance in synchronous federated learning. It would be useful to compare their straggler approach with these synchronous schemes to properly assess the merit of their work.

If the authors satisfactorily respond to these questions (in particular to my first point), I am willing to increase my rating.

---------------------

After the authors's response: 
From reading the authors'c comments to my questions, the other reviews, and their response to those, I understand their scheme better now. Consequently, I am updating my score.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper proposes a robust approach to dealing with stragglers and adversaries in federated learning by model grouping and staleness-dependent weighting of models at the server, combined with entropy-based filtering. Stragglers and adversaries are two key concerns in federated learning, and this paper makes progress along both fronts. The reviewers generally received this work well, and the authors’ responses helped address many of their concerns, leading reviewers to increase their scores. Overall, the consensus was that this paper is worthy of acceptance and makes a solid contribution to the federated learning literature. When preparing the camera ready, please make sure to address the questions that came up during the review process, especially around clarifying the proposed approach.
Decision: Accept (Poster)