Exploit Gradient Skew to Circumvent Byzantine Defenses for Federated Learning

We appreciate the time and effort you have dedicated to reviewing our work. We would like to address your major concerns as follows.

W1: Proposition 1 is not true as stated, and the proof of Lemma 1 is incorrect.

A1: We thank the reviewer for checking the details of the proof.

We acknowledge that Proposition 1 requires the distribution of honest gradients to be skewed enough. Yet we want to emphasize that the visualization in Figure 4, Appendix A verifies that honest gradient is highly skewed on various datasets. Similarly, the lower bound provided by (Xie et al., 2020) also requires the variance of honest gradients to be large enough. Therefore, we argue that it is reasonable to assume the distribution of honest gradients to be skewed enough.

We've fixed the proof for Lemma 1. To summarize, we added the missing radical signs, i.e., changed all $\mathbb{E}[\|\boldsymbol{X}\|^2]\mathbb{E}[[\|\boldsymbol{Y}\|^2]$ to $\sqrt{\mathbb{E}[\|\boldsymbol{X}\|^2]\mathbb{E}[[\|\boldsymbol{Y}\|^2]}$ in Eq. (26), (27), (28) and (29). We Please refer to Appendix B.1 for the fixed version.

W2: Proposition 2 is superfluous as the $\rho^2$ (should depend on by the way) in the lower bound is shown to vanish across iterations by Farhadkhani et al. (2022).

A2: Thanks for the thoughtful comment. We have carefully looked through Farhadkhani et al. (2022) and cannot find the statement that $\rho^2$ would vanish across iterations. In fact, even in the simplest case where the local loss functions on clients are convex, $\rho^2$ won't vanish across iterations as long as local loss functions have different minimizers (due to data heterogeneity).

W3: Performance against NNM proposed by Allouah et al. (2023).

A3: Thank you for the kind suggestion. We have supplemented the experiments and tested the proposed attack against NNM proposed by Allouah et al. (2023). The results are posted in Table 1 below. The results suggest that the proposed STRIKE attack still outperforms other baseline attacks against NNM.

Table 1. Accuracy under different attacks against different defenses on ImageNet-12. The best results are in bold. The lower, the better.

(Due to limited time, we only run experiments on the top-3 robust AGRs in the main experiment and the strongest attacks against these robust AGRs. We will provide more results in our final revision.)

We appreciate the time and effort you have dedicated to reviewing our work. We would like to address your minor concerns as follows.

Q4: The related work section is inaccurate.

A4: Thanks for pointing out this typo. We've corrected it as follows.

El-Mhamdi et al. (2021); Farhadkhani et al. (2022); Karimireddy et al. (2022) provide state-of-the-art theoretical analysis of Byzantine resilience under data heterogeneity.

Please refer to Section 2 for details.

Q5: The term "skew" is repeatedly used without a proper definition, although a formal definition is given in page 4 without intuition on what skewness means. It seems throughout the paper that it can be replaced by gradient heterogeneity/dissimilarity. In that case, the insights given are very similar to those of Karimireddy et al., (2021), Allouah et al. (2023), etc.. In fact, skewness is a confusing term; it is widely used when referring to probability distributions, but that definition is quite different from what paper suggests. But again, a proper definition would have cleared this issue.

A5: The term "skew" is formally defined in Definition 2. The intuition is already provided in 4-th paragraph, Section 1 in the original paper together with an intuitive visualization. The sentence is "the majority of honest gradients skew away from the optimal gradient". In this case, the skew is totally different from the gradient heterogeneity/dissimilarity defined in the previous paper. "Skewness" is formally defined in Definition 2, and is totally different from one defined in probability theory.

Q6: "Skewed majority" is inaccurate.

A6: Thank you for pointing this out. We have changed it to a more accurate representation, "skewed honest gradients" in revision.

Q7: The last sentence in Section 4.2 is incorrect.

A7: We thank the reviewer for pointing out this typo. The corrected version of this sentence is as follows.

Note that we do not require the loss function to be \textcolor{blue}{convex}, which implies that Proposition 2 also applies to more challenging \textcolor{blue}{non-convex} loss functions.

Please refer to Section 4.2 in revision for the corrected version.

Q8: Justification of the search direction.

A8: Thank you for the insightful suggestion. We acknowledge that more justification can help readers to better get the reasonableness and effectiveness of search direction.

We visualize the Byzantine gradients together with honest gradients under STRIKE attack against Median AGR on CIFAR-10 in the non-IID setting in Figure 5, Appendix A. The visualization shows that Byzantine gradients can hide within the skewed honest gradients well. This justifies that the heuristic search in the first stage of STRIKE attack can effectively find the skewed honest gradients, i.e., the search direction is effective.

Q9: Redundant parameter $\nu$.

A9: Thank you for the thoughtful comment.

While STRIKE with $\nu=1$ can outperform most SOTA attacks, an appropriate $\nu$ can further improve the effectiveness of STRIKE against some particular defenses significantly, e.g., the accuracy of STRIKE ($\nu=2.0$) is 5% lower than the accuracy of STRIKE ($\nu=1.0$) as shown in Figure 6, Appendix D.2.1. Thus, we leave open to future researchers the possibility to carefully choose $\nu$ value to boost the performance of STRIKE.

We have included the above discussion in our revision to clarify the necessity of hyperparameter $\nu$.

We are happy that the reviewer found our paper to be interestingly motivated and well written. We hope that the following responses can address your concerns.

W1.1: The proposed STRIKE against robust SGD with momentum in (Karimireddy et al., 2021).

A1.1: Thank you for your insightful comment. We've tested the performance of the proposed STRIKE attack against CClip proposed by (Karimireddy et al., 2021) in Section 6. The empirical results suggest that our attack is still effective for robust SGD with momentum.

W1.2: Assumption 2 is confusing.

A1.2: Sorry that the typo confused the reviewer. Assumption 2 does not require to be IID. The corrected version of Assumption 2 is as follows.

Assumption 2 (Unbias). The stochastic gradients sampled from any local data distribution are unbiased estimators of local gradients for all clients, i.e.,

$$$$

\mathbb{E}[\boldsymbol{g}_i^t]=\nabla\mathcal{L}_{\textcolor{blue}{i}}(\boldsymbol{w}^t), \quad\forall i=1,\ldots n, t=0,\ldots,T-1.

We would like to gently remind the reviewer of any follow-up clarifications or questions that we can do our best to address in the remaining limited time. We hope our previous response has clarified your comments and has helped improve your opinion of our work. Please let us know if there are additional comments you have for us. Thank you once again for your valuable feedback on improving our work.

I thank the author for the clarification. The concerns in my initial review have been almost addressed. Meanwhile, I have noticed some concerns about the correctness raised by other reviewers. I was waiting to see if the concerns about the correctness could be properly addressed and I apologize for the late response. I will raise my rating if the concerns about the correctness are addressed.

We are happy that the reviewer find our work to be inspiring and well-supported theoretically and empirically. We would like to address your concerns as follows.

W1: The proposed attack requires adversary to know gradients of all honest participants.

A1: Thank you for the thoughtful comment. We also test the performance of the proposed STRIKE when only a certain proportion of honest gradients is known. In this case, STRIKE identifies $(n-2f) \cdot \theta$ honest gradients as skewed majority in the first stage, where $\theta$ is the ratio of known. The experiments are performed on the ImageNet-12 dataset. All other setups are identical to the experimental setups in Section 6.1. The results are posted in Table 1 below. As shown in Table 1, the accuracy is higher, STRIKE attack is still competitive when only a proportion of honest gradients is known.

Table 1. The accuracy of STRIKE when only a certain proportion of honest gradients is known on the ImageNet-12 dataset. The lower, the better.

W2: Lack of discussion on any potential adaptive defense methods against this attack.

A2: We are grateful for your kind suggestion.

In Section 4.2, we have discussed existing defenses such as Multi-Krum, RBTM and any other robust AGRs that satisfies Definition 1, against this attack and they cannot defend against our STRIKE attack as shown in Proposition 1 and 2.

The STRIKE relies on the gradient skew phenomenon, which is closely related to non-IIDness of data distribution. Therefore, defenses that can alleviate non-IID can potentially mitigate our STRIKE attack.

We have added the above discussion to the revision. Please refer to Section 7.

Q1: The performance of the proposed attack when there is no skew

A1: We acknowledge your concerns regarding the performance of the proposed STRIKE when there is no gradient skew.

We have supplemented new experiments about the performance of STRIKE in the IID setting. The results are posted in Table 2 below. The results in Table 2 show that when there is no gradient skew (IID), our STRIKE attack is still competitive compared with other SOTA attacks (average rank 3.71).

Table 2. The performance of the proposed attack in the IID setting on ImageNet-12. The lower, the better.

We sincerely appreciate your valuable feedback and the time you've dedicated to providing it. We are glad that you find our paper to be well-supported both theoretically and empirically. We would like to address your concerns as follows:

W1: Computation cost of the STRIKE attack.

A1: We thank the reviewer for the thoughtful comment.

Theoretically, the final optimization problem of the proposed STRIKE attack in Eq. (19) can be effectively solved by a bisection algorithm as discussed in Appendix C. The computation cost is $\mathcal{O}(-\log\epsilon)$, where $\epsilon$ is the error of $\alpha$. In experiments, we perform bisection only 8 times and make the error of $\alpha$ within $1$. Empirically, the attack time for STRIKE is 12.11s (13.47s for MinMax, 13.35s for MinSum) on ImageNet-12.

We've included the above content in our discussion. Please kindly find it in Appendix C.

W2: More discussion on the limitation.

A2: Thanks for the valuable comment.

A limitation is that the effectiveness of STRIKE attack relies on the existence of gradient skew. For example, when the data is IID, the performance could be limited.

We have also supplemented new experiments about the performance of STRIKE in the IID setting. The results are posted in Table 1 below. The results in Table 1 show that when there is no gradient skew (IID), our STRIKE attack is still competitive compared with other SOTA attacks (average rank 3.71).

Table 1. The performance of the proposed attack in the IID setting on ImageNet-12. The lower, the better.

We have included the above discussion of limitations in the revision. Please kindly find it in Section 7.