Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
The paper studies the problem of asynchronous training  with robustness to adversaries in federated learning. The authors propose an idea based on entropy based filtering to simultaneously filter out adversaries, and a weighted averaging technique to handle staleness in the gradients.

Pros:
-->I like the idea of using stale gradients that arrive past their due date in a delayed manner with appropriate weight.
--> The idea of using a public data set, and metrics from that data set to aide filtering out adversaries is interesting, and possibly worthy of pursuit.

Cons/Concerns:
--> The paper's analysis assumes that the entropy based filtering technique automatically filters out gradients from adversaries. In fact, this seems to play no role in the the analysis in Theorem 1 (Appendix G.1). In fact, this theorem proof seems to be identical to a proof that would exist if there were no adversaries (unless I missed something).

--> I find Theorem 1's result a bit confusing. As per the paper, they seem to be allowing an arbitrary number of stragglers (and arbitrary degree of straggling). For instance, for some value of t, it is possible that $S_t = U_\infty^{t},$ which means that none of the nodes selected in time $t$ ever send their updates. The theorem's assumptions do not seem to preclude this, but somehow, the result is blind to such straggling. Put differently, we expect that the performance must closely depend on the degree of asynchrony. However, this is not sufficiently captured in the statement of Theorem 2.

--> Overall, I find that the novelty is relatively limited, and the ideas seem to be a simple combination of those that have appeared in Zhao et. al 2018, and Xie et. al 2019 

review_title: Recommendation to Reject

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper considers federated learning with straggling and adversarial devices. To tackle stragglers, the paper proposes semi-synchronous averaging wherein models with the same staleness are first averaged together, and then a weighted average of the results with different stateless is computed. To mitigate adversaries, the paper proposes to first perform entropy-based filtering to remove suspected outliers, and then compute loss-weighted average. The server is assumed to have some public data, which is used for entropy-based filtering. Together, the proposed algorithm is called semi-synchronous entropy and loss based filtering (Sself). 

Strong points:

1. Mitigating adversarial attacks, especially model poisoning and backdoor attacks, is an important challenge in federated learning. 

2. The proposed algorithm is simple. The paper is well-written, and easy to follow. 

Weak points:

1. Theorem 1 does not seem to consider adversarial devices, and the proof seems to only the semi-synchronous part of Sself without entropy-based filtering and loss-weighted average. Intuitively, the convergence performance should degrade with the number of adversarial devices. However, the theorem statement does not seem to indicate so. If the theorem only analyzes the semi-synchronous part of Sself, then this should be explicitly mentioned. The theorem in its current form is a bit misleading.

Further, even when there are no adversaries, what is the theoretical improvement over FedAsync? Specifically, what is the impact of staleness on convergence. It is important to add remarks to elaborate the gains qualitatively. 

2. Experiments are performed for the simplistic case when each device has a delay of 0, 1, or 2 rounds (chosen uniformly at random and independently for each device). Further, experiments (in the main body of the paper and supplementary material) are for a limited number of adversarial attacks. The performance can be evaluated for practically motivated straggler models and more powerful known attacks. For instance, the attack from the following paper:

G. Baruch, M. Baruch, Y. Goldberg, “A Little Is Enough: Circumventing Defenses For Distributed Learning”, NeurIPS 2019.

While proposing entropy-based filtering, the authors hypothesize that “if the local model is poisoned, e.g., by reverse sign attack, the model is more likely to predict randomly for all classes and thus has a high entropy”. However, some attacks such as targeted backdoor attacks typically do not hurt overall accuracy. So, it is not clear why the poisoned model is likely to predict randomly for all classes. It will be helpful to add more evidence. 

3. Evaluating the loss on the public data for each device may incur significant computational complexity. It is important to elaborate on how much the complexity at the server will increase by using entropy-based filtering on public data. 

Other suggestions:

1. Fig. 2, should the x-axis label be round number than running time?

2. In experiments, can you quantify the performance gain of Sself over FedAsync? For instance, in Fig. 2, FedAsnc seems to be almost on par with Sself. It will be helpful to quantify the performance improvement. 

3. Zeno proposed in the following paper also uses public data at the server. If possible, it will be good to compare against Zeno for fairness. 

Cong Xie, Sanmi Koyejo, Indranil Gupta, “Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance”, ICML 2019.

In summary, the theoretical result (Theorem 1) is weak as it does not seem to consider adversarial devices. In experiments, the stragglers are simulated in a simplistic manner, and the gains over FedAsync are not quantified. It will be good to consider the weak points and suggestions to improve the paper. Currently, the novelty seems to be fairly limited. 

-------------- Post-Rebuttal Comments -----------------
Thanks to the authors for their response, and for updating the manuscript. Some of my queries were clarified. However, updated Theorem 1 seems to raise more questions. In particular, Assumption 4 looks very restrictive to me. If adversaries manage to produce large values of \Gamma, they can inflict a large error as per (7). The paragraph after Theorem 1 does not mention how entropy and loss based filtering methods can achieve small \Omega_{max}, but only says that "if the entropy-based filtering method successfully filters out the model poisoned devices, and the loss-weights \beta_i(k) of the adversaries are significantly small for data poisoning and backdoor attacks... ... then we have a small error term". It is not clear what guarantees the filtering schemes yield. Due to these reasons, I still think the paper is not yet ready for publication.
review_title: Official Blind Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Paper summary**

The paper claims to propose the first algorithm that can handle adversarial machines and stragglers simultaneously in the federated learning setting. To handle stragglers, the paper takes a semi-synchronous approach by taking a weighted sum of gradients depending on staleness. To handle adversarial machines, the algorithm uses an entropy based filtering and a loss based averaging strategy. Note that to handle the adversaries, the algorithm needs a public dataset at the server, using which it can evaluate the entropy and loss scores of each gradient.

**Strengths**
1. The problem of handling stragglers and adversarial machines (including data poisoning adversaries) seems a very relevant problem. The paper claims to be the first to solve this (however I think Xie et al.(2019) also solve a similar problem). 
2. The handling of stragglers seems to be theoretically backed (although I have some concerns about the handling of adversarial machines) and Theorem 1 shows that the convergence up to some error is fast.
3. The experiments show that the algorithm beats or matches existing algorithms on MNIST, CIFAR10 etc.  


**Concerns**
1. In the proof of Theorem 1, I could not find the analysis of the Entropy filtering step of the algorithm. 
2. I think Lemma 1 is only applicable on the non-adversarial machines. In the proof of Theorem 1, inequality (d) (on page 18) applies Lemma 1 on all the machines including the adversarial ones. 

For these reasons, I think Theorem 1 does not give correct guarantees for the algorithm.

**Score justification**

As mentioned in the Concerns section, I am not sure if the theoretical guarantees for the algorithm are correct.

**References**

Xie, C., Koyejo, O. and Gupta, I., 2019. Zeno++: Robust Fully Asynchronous SGD.

review_title: Good algorithm, but I have some concerns regarding the theory

final_score: rating: 4: Ok but not good enough - rejection
review_content: Review: This paper proposes Sself to achieve robustness against adversary when there are straggler.
They uses semi-synchronous scheme to handle the straggler. In each round, the server use entropy based filtering to filter models with large entropy. Then the models are aggregated based on their weights and staleness. The main contribution of this paper is to propose an asynchronous training scheme in the presence of Byzantine workers.

=======================================================

Pros:

- Using semi-synchronous scheme to handle straggler is interesting.

- The entropy based filtering and loss based averaging looks interesting.

- The`experiments presented in the paper look good.

=======================================================

Cons:

- The computation cost in each round grows linearly with time.
- Unfair baselines:
  - The comparison with [1] is unfair because they don't assume the server to have training data. Instead, Sself should be compared with Zeno++[2] which has similar setting;
  - `Waiting for straggler` is not a good baseline. To handle the straggler, [3] suggest the server can simply send requests to 30 percent more workers for updates and wait for the fastest replies.
- Assuming public and IID data on the server is a very strong assumption. The data collection schemes do not consider the existence of Byzantine worker.
- It is not clear to me how this method can defend backdoor attack. In [4], they mentioned that the goal is to achieve high accuracy on main task and an attacker-chosen subtask. So it should behave good on the main task, especially comparing to the models trained on non-i.i.d. good workers. Is it possible to improve the backdoor attack such that it can deceive Sself?

- It is not very convincing to me that the filtering threshold is easy to select. The entropy of the models decrease over time, does the threshold change as well? Is the threshold a prior knowledge or learned from data?

- What are the numbers of adversaries can be tolerated by this method?

=======================================================

Minor comments:

- The curves are a bit bumpy.


[1] Pillutla, Krishna, Sham M. Kakade, and Zaid Harchaoui. "Robust aggregation for federated learning." arXiv preprint arXiv:1912.13445 (2019).

[2] Xie, Cong, Sanmi Koyejo, and Indranil Gupta. "Zeno++: Robust Fully Asynchronous SGD." arXiv preprint arXiv:1903.07020 (2019).

[3] Bonawitz, Keith, et al. "Towards federated learning at scale: System design." arXiv preprint arXiv:1902.01046 (2019).

[4] Bagdasaryan, Eugene, et al. "How to backdoor federated learning." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.


review_title: Interesting idea with unfair baselines and unclear details.

Meta-review: This paper proposes a combined method to address stragglers and adversaries in federated learning. Stragglers are overcome by allowing staleness in model aggregation. Adversaries are handled by using a public dataset to identify poisoned devices and adjusting their weights when doing model aggregation. However, the reviewers raised concerns about:
* The correctness of Theorem 1
* The novelty of the paper given that there has been significant previous work on straggler mitigation and robust aggregation in distributed learning. 

As a result, I am unable to recommend the acceptance of the paper. However, the idea is certainly promising, and if built upon more rigorously can result in a nice and impactful paper. I hope that the authors can take the reviewers' feedback into account when revising the paper for a future submission!
Decision: Reject