Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers collaborative learning in an (asynchronous) decentralized setup in the presence of Byzantine nodes. The authors define two problems: Byzantine-robust collaborative learning and Byzantine-robust ‘averaging agreement’. The main contribution is to show an equivalence between these two problems. Then, the paper proposes two algorithms for averaging agreement, which yield Byzantine-robust collaborative learning solutions. Finally, the paper shows that when the number of Byzantine nodes is larger than 1/3, then no algorithm can achieve Byzantine averaging agreement. 
main_review: *Originality and Quality:* The notion of Byzantine averaging agreement and the equivalence result are interesting. As mentioned in the paper, the equivalence result is powerful, as it allows one to obtain impossibility results for collaborative learning. On the other hand, I have three major concerns. 

1. The collaborative learning definition (Definition 1) warrants more justification. Works on Byzantine-robust distributed learning typically present learning algorithms which converge to a critical point of the (non-convex) statistical loss function. Is \bar{theta} serving the same purpose according to (4)? It will be important to add a discussion here. Without comparing to standard collaborative/distributed learning setups and objectives, it is difficult to appreciate the definition. 

2. The paper assumes that there is a predefined common seed. How is the common seed generated in the presence of Byzantine nodes? It is helpful to give more details on this. 

3. As mentioned in Remark 1, batch size needs to grow linearly with the number of iterations for the proof of Theorem 1 to hold. This seems to be quite restrictive from a practical perspective. Is this an artifact of the proof techniques or is it more fundamental? It would be important to add more details on this. 

Apart from these, another question is about the reliable broadcast model. Is the reliable broadcast decentralized model equivalent to the (trusted) parameter-server-based model (operationally, both the models seem to be the same)? It will be helpful to compare and contrast the two models.

*Clarity:* The paper is generally well-written, but the quality can be improved. Please find below some comments.  

1. It will be helpful to comment on how the formulation (in terms of the objective function) of collaborative learning compares with [36] (other than convex loss and synchrony assumption). Also, how does the model compare with that in [13]?

2. It will be important to explicitly define the notation in lines 6 and 8 of Algorithm 1. How is BYZ(.) defined?

3. According to Definition 2, AVG outputs a family of vectors. As per (10), MDA outputs a single vector. I may be missing something here, but it would clearly be helpful to provide more details. 

4. It will be helpful to formally define \bar{theta}. Assumption 5 should be stated in Theorem 4.

*Significance:* Unlike Byzantine-robust distributed learning (with a parameter server), which has received significant research attention recently, decentralized learning with Byzantine-resilience has received much less research attention. The asynchronous and omniscient adversary setup considered seems a bit too strong for practice, but it is intellectually interesting. The notion of averaging agreement and the equivalence result are quite interesting. I am willing to reconsider my score if the authors can address the major concerns and improve the clarity of exposition. 
limitations_and_societal_impact: The authors have discussed potential negative societal impact. It will be helpful to discuss limitations of the proposed averaging agreement algorithms: e.g., runtime of MDA is exponential in q when q is comparable to f, and trimmed-mean requires reliable broadcast assumption.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers the Byzantine-robust learning problem in a decentralized network. The authors discuss the connection between Byzantine-robust learning and averaging agreement. 
main_review: The authors claim that this paper addresses the problem of Byzantine-robust learning for the decentralized, asynchronous and heterogeneous setting. However, several issues must be clarified to avoid misunderstanding.
- The decentralized topology seems to be a complete graph. This is different to, and relatively simpler than the incomplete graph that is of interest to the machine learning community. 
- The asynchronous communication model assumes the malicious nodes can delay transmissions to the honest nodes. Intuitively the malicious nodes would like to send messages as fast as possible so as to maximize the effects of attacks. Therefore, this asynchronous setting can reduce to the worst case: among the q messages received by any honest node, f of them are malicious.
- Heterogeneity is a big challenge to Byzantine-robustness. This paper discusses its impact, but does not show how to address this issue.

I understand that the authors focus on the theoretical part of Byzantine-robustness, but sufficient numerical experiments are necessary for a NeurIPS paper. At least, the authors should compare the proposed methods with the existing decentralized Byzantine-robust learning algorithms. The authors should also show more performance metrics, in addition to slowdown.

The proposed MDA method is not new. Please cite proper references and give some discussions.

limitations_and_societal_impact: No comment.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents algorithms for collaborative learning which are distributed and robust wrt Byzantine nodes as long as these do not exceed either 1/3 or 1/6 of the total number of nodes.  This result is achieved by proving the equivalence of two concepts the authors introduce, C-learning and C-averaging where C is a constant.  Computational results are provided to support the claims of the paper.
main_review: 
The paper tackles an important problem in distributed learning, namely, with the existence of Byzantine nodes, how does one construct cross-node learning algorithms which automatically and effectively filter out the influence of the unknown miscreant nodes and leverage neighbor node learning?    The writing of this paper is generally clear but occasionally there are lapses of clarity which turn out to be quite essential for following the basic narrative of this paper.  For example, the key concepts of C-leaning and C-averaging are defined only with reference to honest nodes but each node has to update its gradient vector and \theta estimates without such explicit knowledge.  So what is the exact procedure each nodes follows?  Is that what is shown as Algorithm 1 on line 240?  What's BYZ in steps 6 and 8 in this algorithm?   What does the equivalence of C-learning and C-averaging -- which involve honest nodes only -- has to say about the impact of Byzantine nodes on estimate of the gradient communicated to other nodes?   Remark 2 seems to mean T_{LEARN} scales like 1/\delta^3 and since batch size (see line 251) is set to t for t<=T_1 and equal to T_1 thereafter, nodes potentially have to use enormous batch sizes.  Are super large batch sizes needed to dilute the contribution of Byzantine nodes?  Is it then implicitly assumed that each node effectively has unlimited data from its own distribution?  Where do the coefficients 1/3 ( n > 3f) and 1/6 (n>6f) come from?  How does one ensure Assumption 5, which gives rise to 6 in n> 5f, holds in any given setting?  What happens if the data for all the honest nodes come from the same distribution, in other works when there is no heterogeneity?  In this case K=0 but it seems this paper has nothing to offer in this case, per statement on line 216.
limitations_and_societal_impact: 
It is hard to see where the authors identify key limitations of this paper often buried under 1/2 dozen assumptions made.  This is quite serious as there appears to be a large amount of averaging going on in the cross-node learning process necessitated to filter out the influence of the Byzantine nodes which is not explicitly localized and stated except implicitly within the 1/2 dozen assumptions.  The authors can start by explaining briefly where and why each assumption is needed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors present a study on Byzantine collaborative learning. In it, n nodes try to learn from each other’s data collectively and some f < n nodes can be adversarial to the learning process and are defined Byzantine. Such problem of collaborative learning is in a fully decentralised, Byzantine, heterogeneous and asynchronous environment with non-convex loss functions. 
In the first part, the authors formulate the collaborative learning problem; They then present an equivalence between collaborative learning and a problem called averaging agreement via two reductions from the former to the latter and vice versa. 
Their reduction proves useful to draw impossibility results and optimal algorithms for collaborative learning through the averaging agreement problem.
Therefore, they then move on to define a Byzantine collaborative learning algorithm called LEARN that allows to solve a Byzantine collaborative learning problem given an averaging agreement problem.
In the last section, the authors present and discuss some empirical evaluations.



main_review: General Comments
The paper is very precise accurate, and its structure is very clear. The double-ended reduction is quite interesting and suggests it could become a powerful tool. 
The notation is a bit cumbersome and reminding what some values represent somewhere along the paper could help improve the readability of the work.
A couple of key concepts are mentioned and used but not well-presented nor described. For example, the averaging agreement protocol is barely defined and it could be better appreciated with more explanations.

General Feeling
The paper is solid and shows attention to the details, the modifications suggested are intended to correct minor lacks. I recommend acceptance.

Detailed Notes
-	Theorem 5 the second sentence suggests to be a corollary. Consider making it one.
-	Figure 1 is very small and in this way hard to appreciate, I suggest making it bigger. Possibly not framed in text if not requested by the format guidelines
-	Despite putting the reference to the definition of Byzantine problems, a brief sentence could be helpful to recall what the authors refer to with the term Byzantine.
-	I cannot seem to find a real description of what averaging agreement is, nor a citation to works having it
-	Page 3 line 106 “in order of billions…”  “in the order of billions…”
limitations_and_societal_impact: Seems adequate.
review_title: null

Meta-review: This paper proposes a Byzantine-robust fully decentralized learning approach under data heterogeneity.

The reviews were initially quite mixed. After reading the author response, several reviewers updated their score. Some concerns about the role/relevance of using large batch sizes, as well as the lack of insights on what robustness can be achieved in the heterogeneous setting. However, the reviewers appreciated the response and recognize the relevance of the problem, approach and evaluation.

Therefore, the paper is accepted. The authors are strongly encouraged to incorporate suggestions and additional details from the discussion, in particular to improve the clarity of the presentation and give more intuitions about the approach.
Decision: Accept (Poster)