Achieving Optimal Breakdown for Byzantine-Robust Gossip

Authors: Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx
Primary area: optimization
Keywords: byzantine, robustness, decentralized, gossip, averaging, sgd

Abstract:
Distributed approaches have many computational benefits, but they are vulnerable to attacks from a subset of devices transmitting incorrect information. This paper investigates  Byzantine-resilient algorithms in a decentralized setting, where devices communicate directly with one another. 
We investigate the notion of breakdown point and show an upper bound on the number of adversaries that decentralized algorithms can tolerate. We introduce an algorithmic framework that recovers ClippedGossip and NNA, two popular approaches for robust decentralized learning, as special cases. This framework allows us to generalize NNA to sparse graph, and introduce CG+, which is at the intersection of the two. Our unified analysis framework gives near-optimal guarantees for CG+ (and other approaches with additional assumptions). Experimental evidence validates the effectiveness of CG+ and the gap with NNA, in particular against a novel attack tailored to sparse graphs that we introduce.

Decision: reject
Reviewer scores: 6, 6, 3

Reviews and discussion:
<thread>
creation date:
1729237000778

thread_type:
official_review

<thread_object>
creator: reviewer_mdqu

<content>
summary:
This paper analyzes the breakdown point of robust algorithms in decentralized optimization and proposes the CG Plus method, which achieves the optimal breakdown point. Convergence guarantees and experimental results are provided to support the proposed method.

strengths:
1. The analysis of the breakdown point for robust algorithms in decentralized optimization is novel and has not been previously explored. 


2. The proposed CG Plus is well-motivated, addressing the impractical clipping threshold issue in ClippedGossip.

weaknesses:
1. The experimental evaluation is insufficient. The authors only conducted experiments on the MNIST dataset, and additional results from other datasets are recommended to strengthen the conclusions.

2. The experimental results do not clearly demonstrate the advantage of CG Plus. In fact, ClippedGossip seems to outperforms the proposed CG Plus overall. The authors' claim that "ClippedGossip might fail against other attacks" is unconvincing. It is recommended that further results be provided to demonstrate CG Plus's advantage over ClippedGossip; otherwise, the development of CG Plus seems unjustified.

questions:
1. The authors utilize the Laplacian matrix of the graph as the gossip matrix. However, in decentralized optimization, the gossip matrix is typically required to be doubly stochastic (He et al., 2022). Moreover, in Section 4.1, the weighted averaging step with $W_{ij}$ in ClippedGossip  (He et al., 2022) is replaced by a "communication step-size" $\eta$. The condition $\eta \leq 1/u_{max}$ seems unable to recover traditional averaging when there are no Byzantine agents. The authors should provide more explanation regarding $\eta$ and clarify why they chose not to use the conventional doubly stochastic gossip matrix. 

2. The paper investigates the breakdown point in terms of the number of Byzantine agents. However, in traditional Byzantine-robust decentralized optimization, the focus often lies on the gossip weights assigned to Byzantine agents, rather than merely the number of Byzantine agents (He et al., 2022). For instance, if more than half of the neighbors are Byzantine, but the total gossip weight assigned to them is minimal, the algorithm can still remain robust. Does this perspective conflict with Theorem 1? It is recommended that the breakdown point analysis consider the gossip matrix in more detail.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729690129364

thread_type:
official_review

<thread_object>
creator: reviewer_jjqz

<content>
summary:
This paper analyzes the optimal breakdown point of robust aggregators in the Byzantine-robust decentralized average consensus problem and proves that the breakdown point of the proposed CG$^+$ method almost aligns with the optimal values. To further validate the effectiveness of the CG$^+$ method in general Byzantine-robust decentralized stochastic problems, this paper examines its theoretical convergence and demonstrates its practical performance compared to existing methods in experiments.

strengths:
The analysis of the optimal breakdown point of robust aggregators is both novel and significant in the field of Byzantine-robust decentralized learning.

weaknesses:
1. The lower bound of the breakdown point indicated in Theorem 1 appears to be not tight, as the breakdown point of CG$^+$ presented in Theorem 2 ($b < \frac{\mu_{\min}}{2} - 1$) does not align with the lower bound ($b \geq \frac{\mu_{\min}}{2}$). This leaves a gap when $b \in$ { $\lceil \frac{\mu_{\min}}{2} - 1 \rceil, \lfloor \frac{\mu_{\min}}{2} \rfloor$}. Therefore, there may be better methods available that can match the lower bound and tolerate more Byzantine neighbors than CG$^+$. I suggest the authors discuss whether this gap is fundamental or if CG$^+$ could potentially be improved to match the lower bound exactly. 
		
2. In Corollary 2, the authors only demonstrate the optimality of the proposed CG$^+$ method. I would like to know the theoretical consensus rate of the honest models when using this method. Can the honest models achieve consensus by the end of the training? Could the authors provide theoretical guarantees on how quickly or to what degree consensus is achieved among honest nodes in the training process?
		
3. The proposed CG$^+$ method does not demonstrate any performance improvement over the existing ClippedGossip in the experiments, which raises doubts about the practical effectiveness of CG$^+$. 

4. Equation (CG) appears to be not correct. The update rule of ClippedGossip involves a doubly-stochastic mixing matrix to aggregate messages from neighbors, while (CG) does not include such a mixing matrix. Please refer to (He et al., 2022) and correct this equation.

questions:
My detailed questions are listed in the above section; please refer to it.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730727930361

thread_type:
official_review

<thread_object>
creator: reviewer_twsj

<content>
summary:
The authors prove a theoretical upper bound on the breakdown point for Byzantine-robust distributed machine learning in decentralized frameworks, and then propose a novel method called $CG^+$, which can achieve the proven upper bound. The theoretical convergence guarantee of $CG^+$ is provided together with empirical evaluation in this paper.

strengths:
+ The problem of obtaining Byzantine robustness in distributed learning on a decentralized framework is challenging and meaningful. 
+ This paper is generally well organized. 
+ This paper proves a new upper bound of the breakdown point and proposes a novel method, which can reach the optimal breakdown point.

weaknesses:
- The proposed method $CG^+$ is like a combination of ClippedGossip and NNA, and thus the novelty of the proposed method is a little bit limited (I understand that $CG^+$ has a better performance and guarantee than each of the two methods). 
- Could the authors briefly explain why the clipping scheme in $CG^+$ can achieve a better theoretical guarantee than ClippedGossip?
- There are replicated references (lines 577-583).

questions:
Please see the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732128440602

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Answer

comment:
We thank the reviewers for their thoughtful evaluation and time spent evaluating our paper and engaging in the discussions, which greatly helped us frame our work. 

We realized that the current writing did not draw a clear line between existing results and our contributions beyond CG+. We have therefore slightly **repositioned the paper as a unifying framework** with new guarantees for several algorithms (new and old ones, in particular but not limited to CG+, a new algorithm with tighter guarantees). We believe this better reflects what this paper brings to the community, without essentially changing the results. 

More specifically, we feel that some of our contributions have not been fully recognized, in particular regarding the improvements that we make to existing approaches. 
1) **Unified analysis of robust gossip algorithms.** This allows us to derive tight convergence guarantees for both ClippedGossip and a new algorithm based on NNA, which we adapt in the gossip setting. In the light of this unified analysis, we introduce a new algorithm, CG+, which features characteristics from the two others to obtain the strongest robustness guarantees. 
2) **Breakdown Point Characterization.** Our upper bound on the breakdown point allows us to characterize the distance between these guarantees and the optimal breakdown point.
3) **Fully decentralized attack**. We test these algorithms by introducing the first attack on gossip algorithms with mathematical foundations. Its effectiveness is proven by experimental results, as it makes aggregation rules break before all the other attacks. 


We summarize our results in the following table, which is an extended version of the table present in the original paper (cf. below for changes consecutive to the discussion with reviewers).

|Index | Status |Algorithm      |  Setup   | Breakdown point | Experiments |
| ------ | ------ | ------ | --- | -------- | -------- |
|1| Existing [1] | ClippedGossip w. *oracle rule* | Gossip - not implementable | $b \le \mathcal{O}(\gamma \mu_{\min})$ | none |
|2| Existing [1] | ClippedGossip w. adaptive rule | Gossip | No guarantee | Competitive|
|3| Existing [2] | NNA | Centralized case only |  No guarantee for sparse graphs | None on sparse graphs |
|4| **New (theory)** | Clipped Gossip w. *oracle rule* | Gossip - not implementable | $b \le \mu_{\min}/8$ | none |
|5| **New (algo + theory)** | Gossip NNA | Gossip - practical rule | $b \le \mu_{\min}/8$ | Competitive yet small breakdown |
|6| **New (algo + theory)** | CG+ | Gossip + practical clipping rule | $b\le \mu_{\min}/4$ | Competitive |
|7| **New (algo + theory)** | CG+, *oracle rule* | Gossip - not implementable | $b \le \mu_{\min}/2$ (optimal) | none |

**Summary of the table above and our contributions**

- We obtain the first gossip type algorithms with theoretical guarantees (lines 4 to 6).
- Our CG+ algorithm with practical rule is almost optimal - we rely on a new analysis to obtain this result (line 6).
- If an oracle was permitted for the clipping threshold:
  - We provide a new analysis of ClippedGossip with oracle rule improving on previous literature (line 4 vs. line 1)
  - We provide an optimal rate for our new rule (line 7 vs line 1)
- We define a gossip version of NNA and provide an analysis (line 5 vs line 3)
- In experiments we compare lines 2, 5 and 6. We conclude that both three methods are competitive bellow their own breakdown point. NNA breaks at first, then ClippedGossip. Surprisingly CG+ does not breaks on the MNIST task, even after the theoretical breakdown point, which might be due to the experimental setup, specifically the line search performed to scale the attacks.


[1]: Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Byzantine-robust decentralized learning via clippedgossip

[2]:  Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Le Nguyen Hoang, Rafael Pinot, and John Stephan. Robust collaborative learning with linear gradient overhead. In International Conference on Machine Learning, pp. 9761–9813. PMLR, 2023.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732590852781

thread_type:
official_comment

<thread_object>
creator: area_chair_vun2

<content>
title:
Response

comment:
Dear Reviewers,

The authors have provided their rebuttal to your questions/comments. It will be very helpful if you can take a look at their responses and provide any further comments/updated review, if you have not already done so.

Thanks!
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper considers a distributed computing set up where devices communicate with each other directly, however are subject to a fraction of them being Byzantine. They show an upper bound on the number of tolerable adversaries for a gossip-algorithm to still be able to find a solution. 

While the paper is interesting, two of the reviewers are on the fence, while one suggested rejection. The main complaint seem to be that of a lack of clarity and comparison with available results. Referees also raise the issue of lack of experimental validations. Reviewer mDqu 
engaged with the authors and after a log discussion decided to keep their score.

Based on the comments and the discussion, I recommend rejection of the article at this stage.