We thank the reviewer for their comments and their precious suggestions. We examine the questions raised below.

Additional Experiments

Following the reviewer's suggestion, we performed new experiments on Erdős-Rényi graphs and additionally compared ourselves with the IOS algorithm [Wu et al., 2022]. We refer the reviewer to the response to Reviewer UczM for further details.

Comment on Remark 3.2

We fully agree with the reviewer that there is no major technical difficulty in either: i) defining $(f,\kappa)$-robustness with arbitrary weights, or ii) going from $(f,\kappa)$-robustness to $(b,\rho)$-robustness with arbitrary weights.

In this remark, we mostly wanted to recall that $(f,\kappa)$-robustness is originally defined with constant weights, so that the reader can easily compare both definitions. Still, we do not believe that generalizing it to arbitrary weights is a major contribution.

For now, if proofs on $(f,\kappa)$-robust aggregators have been written with constant weights, arbitrary weights can be achieved, for instance by increasing artificially the number of input vectors so that the frequency of each input approaches the targeted weight.

Suggestions

We thank the reviewer for the meaningful and precious advice on the flow of the paper, which we will implement.

1. Introduction of Aggregation Rules We agree with the reviewer that this part takes space while not being clear enough. We will think about how to improve it. One solution we are investigating is to consider in the main part of the article definitions with unitary weights only and defer the generic definitions to the appendix. We agree that currently, the definition of $(b,\rho)$-robustness is a bit too far away from the example of robust summands.

2. Asynchronous Part We fully agree that it is a bit rushed; we will move it to the appendix to clarify it.

3. Title of Section 3.4 The reviewer is right to point out that our limits only apply when we consider $r$-robustness as the robustness definition of any decentralized algorithm. Thus, we will follow their suggestion.

4. Defining $(\alpha,\lambda)$-Reduction We agree as well that defining it properly will make the paper easier to read. Furthermore, it will allow us to better compare it with $r$-robustness.

5. Typos We agree that currently, the 'oracle' clipping thresholds are ill-defined; we will improve this point. Thank you as well for pointing out the missing sentence.

We thank the reviewer for their comments, which we discuss below.

The reviewer is perfectly right to point out that the choice of edge weights influences the spectral properties of the graph, which impact the robustness criterion. It is thus an interesting research direction to develop a method that maximizes the spectral gap of the honest subgraph through a robust protocol, agnostic to the position of the Byzantine nodes.

Meanwhile, it is still possible to build on existing methods, such as the Metropolis choice of weights:

1. Given an upper bound on the number of Byzantine nodes $f$, one can have a local upper bound on the weight of Byzantine neighbors using $b_i = f \max_{j \in n(i)} w_{ij}$. This can be combined with Metropolis weights to have a robust initialization of the matrix weights. Indeed, as pointed out by [He et al., 2023], defining $w_{ij}$ as $\frac{1}{max(d_i, d_j) + 1}$ is robust: if $i$ is honest and $j$ Byzantine, then $j$ cannot force $i$ to assign a weight greater than $1/(d_i+1)$ to the edge $(i,j)$. In this setting, a local bound of the Byzantine weight can be taken as $b_i=f/(d_i+1)$.
2. Having a local upper bound on the number of Byzantine weights $b_i \ge \sum_{j \in n_B(i)} w_{ij}$ is sufficient to implement the robust aggregation rules. For instance, each node $i \in H$ chooses the local clipping threshold based on this local $b_i$. Using such a local upper bound of the weights of Byzantines leads to the same guarantees, with $b = \max_{i \in H} b_i.$

Does our response answer your question?

[He et al., 2023] Byzantine-robust decentralized learning via clippedgossip, He et al. 2023

We thank the reviewer for their comments, which we discuss below.

Experiments

As requested by Reviewers CF8P, UczM, and EynP, we performed additional experiments, which are available here https://anonymous.4open.science/r/rebutal_files-342B/.

We provide 2 additional experiments on Erdös Renyi graphs: one on an averaging task, and one on a CNN trained on MNIST. We additionally compare ourselves with IOS algorithm [3], thus we provide the previous experiments on MNIST as well.

Setting

Erdős-Rényi The subgraph of honest nodes is sampled as a random Erdos Renyi graph with 20 honest nodes, each of them being always adjacent to 4 Byzantine nodes. For each seed, 12 different values of $p \in [0.25,1]$ are tested, where p denotes the probability for each edge to exist. We plot the links between the algebraic connectivity of the graph ($\mu_2$, the second smallest eigenvalue of the unitary weighted Laplacian) and the loss. The tasks tested on this graph are: a. Averaging task: Nodes' parameters are initialized using a $N(0,I_5)$ distribution. Nodes perform (robust) gossip communication iterations. We conduct experiments on 6 different seeds, and curves are smoothed using a moving average of size 4. b. MNIST: The model taken is the same CNN as in the previous experiments on MNIST in the paper. The heterogeneity among nodes has been increased to emphasize the importance of communication, from $\alpha=5$ to $\alpha=1$ (cf. Dirichlet sampling in [3]). Experiments are conducted on one seed.

For clarity, we changed the legend of CS$_{He}$-RG to ClippedGossip, even though they both correspond to the same implementable version of ClippedGossip from [1], unsupported by theory.

Analysis of the Experiments

Averaging Task on Erdős-Rényi

We provide, for each algorithm, the largest value of $\mu_2$ for which it is non-robust and the attack that makes the algorithm break:

1. CS$_{ours}$-RG breaks at $\mu_2 \approx 5.5$ with ALIE and FOE attacks.
2. ClippedGossip breaks at $\mu_2 \approx 10$ with ALIE attack.
3. IOS breaks at $\mu_2 \approx 16$ with FOE attack.
4. GTS-RG breaks at $\mu_2 \approx 10$ with SpH attack.

In this setting, $CS_{ours}$-RG is the algorithm with the best breakdown point among the compared methods. Interestingly, $CS_{ours}$-RG is robust for a connectivity $2$ times smaller than GTS-RG, as our theory predict it.

MNIST Experiments on Erdős-Rényi

We notice that:

1. CS$_{ours}$-RG keeps good performances in this setting while other methods break, showing a better performance than the (worst-case) one predicted in our theory.
2. SpH makes IOS break with larger connectivity than other rules. SpH is just as efficient as Dissensus on ClippedGossip, while Dissensus makes GTS-RG break with a larger connectivity.

IOS on MNIST: Previous Experiment

IOS performances are similar to that of GTS-RG: its breakdown point is slightly better than GTS-RG but still worse than CS$_{ours}$-RG. We notice that SpH is very effective against IOS as well in this setting, in the sense that it makes IOS break earlier than other attacks.

More Involved Datasets

We conducted our experiments on MNIST and CIFAR-10 datasets as those are standard benchmarks in the decentralized robustness literature (see e.g., [He et al., 2023] and [Farhadkani et al., 2022]). Furthermore, the initial experiments on MNIST require approximately 4 days to be performed: indeed, we train simultaneously 26 models for 10 different values of $b$, on 4 different attacks and 3 different algorithms, each experiment being initialized with 5 different seeds. This multiplication of configurations and models to train significantly increases the computational burden of experiments.

As our contributions focus on the averaging sub-problem (the rest is just a direct consequence of the better averaging properties), we provided learning experiments mostly to illustrate our theory, and show how better aggregations lead to better decentralized-SGD algorithms. Our goal was to provide clear theoretical foundations for decentralized optimization, not a large-scale benchmark of current solutions.

Generalization to Other Decentralized Protocols

Our analysis focuses on the gossip protocol, but it may be of interest to other protocols. Any protocol that, at some point, performs node-level averages of other parameters in the network could apply some $(b,\rho)$-robust summand instead of plain averaging and use our analysis to provide guarantees on the robustness of their algorithm. Note that averaging is particularly relevant, due to the average structure of the ERM problem.

[1] Byzantine-robust decentralized learning via clippedgossip, He et al 2023 [2] Byzantine-resilient decentralized stochastic optimization with robust aggregation rules, Wu et al 2023 [3] Robust collaborative learning with linear gradient overhead, Farhadkhani et al 2023 [4] Bridge: Byzantine- resilient decentralized gradient descent. Fang et al 2022

We thank the reviewer for their detailed comments, which we discuss below.

Theoretical Improvements

We respectfully but firmly disagree on the main weakness stated, i.e. our framework does not demonstrate theoretical improvement.

The major theoretical improvements of our framework rely on the tight analysis of the breakdown point, which are compared with previous papers in the paragraph near optimal breakdown point of Section 3.4.

The table below summarizes the main differences with previous works, with details afterwards.

We emphasize that:

• [1] relies on a non implementable clipping rule that requires prior knowledge of the neighbors' identity (Byzantine or honest). Yet we have better guarantees: their breakdown point is suboptimal by a significant factor $\gamma$ (the graph's spectral gap) shrinking with the lack of connectivity of the graph.
• [3]'s breakdown point is highly suboptimal: the proportion of tolerated Byzantine nodes goes to 0 when the number of nodes increases.
• [2] only considers fully connected networks, still we provide tighter breakdown guarantees: they show NNA tolerates up to 1/11 of Byzantines, while our method tolerates 1/5th. Moreover we show NNA tolerates up to 1/9th. Altough they show multiple steps of NNA satisfy $(\alpha,\lambda)$-reduction with 1/5 of Byzantine nodes, enforcing $\lambda<1$ (required to be r-robust) in their guarantees leads to tolerate only $O(1/\sqrt{H})$.

Corollary 4.7 Too Good to Be True

We clarify here the notation $Var_H(x^t)$, which converges in $O(1/T)$. Recall that $Var_{H}(x^t)=1/H\sum_{i\in H}|x_i^t-\bar{x}_H^t|^2$.

It thus quantifies how far honest parameters are from each other, called 'variance among honest nodes'. This may converge to 0 quicker than $O(1/T)$: for an optimization step size $\eta_{op}=0$, the algorithm boils down to (robust) gossip averaging, and the variance converges linearly to 0. Crucially, $Var_{H}(x)$ does not correspond to a stochastic variance due to SGD.

PS: Cor. 4.7 statement had a typo: the expectation operator was missing, it might have driven the confusion. Exact result is $E[Var_{H}(x^T)]\in O((1+\zeta^2/\sigma^2)/T)$, where the expectation is taken over SGD randomness.

Experiments

We provide additional experiments ( https://anonymous.4open.science/r/rebutal_files-342B/. ), which are described in Reviewer GrPa's answer.

Breakdown Point Limit is Not Fundamental

We highlight that Thm 3.5 only assumptions are:

• Algorithm is decentralized, nodes communicate within a graph
• Algorithm is $r$-robust on this graph
• Byzantine nodes are unknown.

Thus we make very few assumptions on the nature of the algorithms involved. The r-robustness assumption is only used as a definition of a robust algorithm. Crucially, Thm 3.5 does not apply only to F-RG framework.

Hence we do not fully understand the remark on the lack of generality of our breakdown point limit. Would the reviewer know of a method not respecting this limit?

To clarify this section, we will highlight the assumptions of this breakdown point limit more precisely and change the section's title to Fundamental Limits of r-Robust Algorithms.

Linking $(\alpha,\lambda)$-reduction and $r$-robustness

We agree $(\alpha,\lambda)$-reduction and $r$-robustness are closely related quantities. While $(\alpha,\lambda)$-reduction measures with two different constants how the bias $|\bar{x_i}^t-\bar{x_H}^0|$ and the variance $H^{-1}\sum_{i\in H}\|x_i^t-\bar{x}_H^t\|^2$ evolve during a step of communication, our definition of r-robustness criterion directly quantifies the of the mean square error, i.e. the bias + the variance. Both are linked using:

1. $(\alpha,\lambda)$-reduction implies r-robustness with $r=\alpha+\lambda$
2. r-robustness implies $(\alpha,\lambda)$-reduction with $\alpha=\lambda=r$

The notion of r-robustness aims at defining what it means to be a "robust decentralized communication algorithm". Indeed, r-robustness with r<1 expresses that "nodes benefit from communicating" more directly than enforcing both $\alpha<1$ and $\lambda<1$. Moreover, the results provided are tighter with this notion of robustness.

Conclusion

We hope that we have adequately addressed all concerns and that these revisions will reflect positively in the reviewer’s final assessment. Otherwise, we would be delighted to engage in further discussion. [1] He et al. Arxiv 2023 [2] Wu et al. IEEE 2023 [3] Farhadkhani et al. ICML 2023 [4] Fang et al. IEEE 2022