Stress Testing Byzantine Robustness in Distributed Learning

We thank you for your comments and address your concerns below. We hope that you re-evaluate our paper in this light, and we are happy to answer any further questions.

Although the adversary model (P) looks reasonable, it seems oversimplified in section 3

We agree that the simplifications may seem to degrade the power of the adversary. In fact, we dedicate Section 4 to explaining why these simplifications $*only marginally*$ degrade the strength of the attacker. For example, regarding the collinearity constraint brought up by the reviewer, we show in Section 4.1 that removing this constraint does not improve the attack by much, since the main ingredient of the attack is to overshoot minima, i.e., going in the same direction as the average of honest gradient, which is allowed by our collinearity constraint.

The proposed attack requires much more information than existing attacks

We acknowledge that our attack is open-box and has full knowledge of the system and defense. This is currently stated clearly in sections 1.1 and 2. The purpose of our paper is not to propose a realistic or black-box attack. Rather, we (i) formulate and study the strategy followed by the optimal attack (i.e., solving (P)) in sections 2 and 4, respectively, and (ii) propose a tractable attack which retains most of the strength of the worst-case attack by building on the same strategy, as explained in Section 4. We recall that the aforementioned strategy consists in overshooting minima by amplifying the direction of the average honest gradient, at the right moment of training by being aware of the loss landscape. Furthermore, based on our result, we provide researchers with a tool to stress test the strength of their defenses in the worst case, using one attack, since it is theoretically claimed by Byzantine-robust defenses (Allouah et al. 2023, Karimireddy et al. 2021, 2022, Farhadkhani et al. 2022) to be able to withstand any attack. For example, even with the full knowledge of our attack, the SOTA defenses all perform well under low data heterogeneity, which actually confirms existing theory in the i.i.d. setting (Farhadkhani et al. 2022).

Besides, our attack does not need to know all the data of honest clients; it only needs to know the average of honest gradients (see Algorithm 1) and some proxy data of the same (global) distribution. Although this is not a concern in this paper, but in practice it can be done by eavesdropping and data reconstruction attacks (e.g., gradient inversion). We will emphasize this point further in the paper.

Finally, Shejwalkar & Houmansadr (2021) analyze state-of-the-art attacks which possess the same level of knowledge as Jump, i.e., knowledge of the system, honest updates and global distribution. Our work belongs to the same line of research.

JUMP seems to have a much higher computation cost than existing attacks such as ALIE and FOE. However, there is neither a theoretical analysis of the time complexity nor the experimental results of the running time in the main text

We provide an analysis in Section A of the computational cost and also its trade-off with the power of the attack for various segment lengths. Notably, the greedy version of Jump $(\tau=1)$ has a reasonable runtime, especially when considering that future benchmarks will only need to run Jump instead of several other attacks. We could not include this discussion in the main body due to lack of space, and because we admittedly focus on a worst-case unbounded adversary.

Clarifying remarks

Our attack is not simply an optimization of FOE. We show in Section 4.2, among other factors, that allowing the attack vector to be in the same direction as the true gradient is essential to Jump, and is a key reason to its superiority over FOE. Also, directly maximizing the honest loss grants adversaries the ability to circumvent at the right moment during training. Finally, Jump enables adversaries to plan ahead when $\tau>1$ and maximize the training loss across iterations, which is not possible with FOE and other attacks.

Thank you for the detailed response. However, the concerns listed below have not been adequately addressed.

1. My concern about the oversimplification of the model (P) remains. The simplified adversary model $(P_l)$ loses many possibilities of potential attack strategies. Moreover, the greedy version ($\tau=1$) of Jump is quite close to the existing attack FOE, while the run time significantly increases when $\tau$ increases as shown in Section A.

2. The proposed attack requires the knowledge of the workers' average gradient, the server's defense strategy, and some proxy data of the global distribution, which is unrealistic. The authors claim they are to provide researchers with a tool to stress test the strength of their defenses. However, the contribution is quite limited since the attack in the test can be rarely operated in the real world.

Given the reasons above, my rating remains.

We thank you for your encouraging comments and address your concerns below. We hope that you re-evaluate our paper in this light, and we are happy to answer any further questions.

Could the authors clarify more on if the same gradient sampling noise is used in the solver and true algorithm update or different realizations are used?

In the results shown in our paper, the attack uses the same noise realizations as those of the honest workers. This is in line with our threat model, where the adversary has full knowledge, including which batches are used by honest workers. Interestingly, even with this knowledge, the SOTA defenses all perform well under low data heterogeneity, which confirms existing theory in the i.i.d. setting (Farhadkhani et al. 2022). We will include a discussion on this point in the paper.

The JUMP optimization problem seems to assume realized gradient sampling which might be a bit strong in practice, it can be possibly formulated into an robust or expectation optimization problem without assuming noise is realized.

We appreciate your advice on loosening our assumption by formulating our problem into a robust optimization problem without assuming noise is realized. We agree this could yield more realistic attacks, but we recall that our goal is to propose a worst-case attack of a truly Byzantine adversary, i.e., has full knowledge and controls all malicious workers. Indeed, theoretical works in our line of research (Allouah et al. 2023, Karimireddy et al. 2021, 2022, Farhadkhani et al. 2022) claim to defend against such a worst-case adversary, yet we argue that they do not actually implement the latter in their validation experiments.

We thank you for your encouraging comments and address your concerns below. We hope that you re-evaluate our paper in this light, and we are happy to answer any further questions.

Shejwalkar & Houmansadr (2021) also use something similar to Jump’s malicious gradient in (4); e.g., in equation (6) of Shejwalkar & Houmansadr (2021) attack, if we substitute $\eta_t = (1 - \lambda_t)$ while $p_t = -\bar{g}^H_t$ we get the Jump attack. Given this I think authors should discuss the distinction between the two attacks more explicitly.

We have included in Section 4.2 a comparison with the attacks developed by Shejwalkar & Houmansadr (2021).

There, among other factors, we explain that a key difference is that Jump allows the perturbation vector to be in the $*same direction*$ as the average honest gradient, in order to overshoot minima. For Shejwalkar & Houmansadr's (2021) attacks, because of the optimization scheme they use, the adversary can only try to deviate from the direction of the average honest gradient (the scale factor is positive).

Furthermore, Shejwalkar & Houmansadr (2021) focus on the i.i.d. setting, which is arguably not the norm in real-world scenarios, and do not extensively investigate the heterogeneous case. In our work, we consider different levels of heterogeneity, using Dirichlet sampling. In terms of threat model, the strongest one considered by Shejwalkar & Houmansadr (2021) also assumes full knowledge. Yet, their attacks only leverage the knowledge of the aggregation and honest updates, while our attack also utilizes the global honest loss function. We will also include this discussion in the paper.

Experimental evaluation is on very small settings: total number of clients is 12 which is very small for the FL settings that are vulnerable to model poisoning in practice [1]. This does not discount the utility of the work, but authors should be clear in terms of the goals of the work and where it is useful, especially positioning it with the conclusions of [1] so that readers will understand how to use this work.

We acknowledge that our experiments are not large-scale, since our work is directed towards researchers who need strong attacks to verify their theoretical worst-case Byzantine robustness claims. We will emphasize this point further in the paper.

Besides, regarding how challenging the datasets are, we use heterogeneous variants of MNIST and CIFAR-10, where the extreme heterogeneity scenario is challenging and is common in Byzantine-robustness works (Allouah et al. 2023, Karimireddy et al. 2022). In any case, note that the more challenging the task, the harder it is for the defender and not the attacker, which is why we focus on moderate heterogeneity, or low fraction of Byzantine workers.

Next, I think the experiments performed are not fair: Jump attack uses the knowledge of the robust aggregation but the attacks it is compared with are aggregation-agnostic attacks; authors should provide a fair comparison, i.e., compare with aggregation-tailored attacks of Shejwalkar & Houmansadr (2021).

We believe that it would be inadequate to compare Jump to aggregation-tailored attacks of Shejwalkar & Houmansadr (2021), given that these attacks choose perturbation vectors depending on the defense, unlike Jump. Now, to automatically choose a perturbation vector for any aggregation rule, Shejwalkar & Houmansadr (2021) propose to simulate a smaller FL system and evaluate aggregation-tailored attacks with all possible perturbation vectors, then pick the best. However, it is unclear how this can be implemented outside the i.i.d. setting they were intended for, since reproducing the data heterogeneity of the original system is not straightforward. We will include this discussion in the paper.

For completeness, $**we updated our paper with results**$ of our experiments with the aggregation-tailored attack of Shejwalkar & Houmansadr (2021) that uses the inverse unit perturbation vector as an example (see Section 4.2). The main change in our results of Table 1 (Section 5) is that when $f=3$ using Krum with NNM, our attack becomes comparable to aggregation-tailored attack (``AGRT'' in Table 1). Otherwise, our conclusions still hold.

We thank you for your response and follow up on them below. We hope that you re-evaluate our paper in this light.

About the evaluation setup comparison: I agree that i.i.d. FL is not practical and I appreciate that the current work sticks to non-i.i.d. setting. However, it is more difficult to attack i.i.d. settings than to attack non-i.i.d. settings as the latter allows attacker much more leeway to craft malicious vectors while remaining undetected.

We agree with both statements. This is why we focus in the main paper on a moderate heterogeneity setting ($\alpha=1$), which is both practical and challenging to attackers. In addition, we have results of experiments on low, moderate, and high data heterogeneity in the appendix.

Nevertheless, if you really want to stress-test FL (as your next answer mentions) you should consider both full and partial knowledge attacks as in SH21.

We stress test Byzantine robustness in distributed learning against an open-box adversary. We agree that the partial knowledge setting is interesting on its own, but is out of the scope of our work.

But IMO, it will be much more useful if you increase the total number of clients from 13/15/17 to 1000 for MNIST or CIFAR10, consider cross-device setting (along with cross-silo).

We thank the reviewer for their suggestion. We agree that a larger scale experiment can be an interesting addition. However, we chose to focus on FL settings that are reasonably easy for the defender, and where theoretical defenses have tight guarantees. In contrast, cross-device settings, where client subsampling and local steps are used, have considerably weaker and fewer theoretical guarantees.

The extreme heterogeneity you consider is dirichlet with $\alpha=0.1$ which is great, only if you have a very large number of clients. With small number of clients considered here, this distribution will not be extremely heterogeneous.

For the experiments we show, most clients have only one label in their dataset, which we believe is an extreme form of heterogeneity.

I agree that to stress-test defenses, one should make settings in favor of attacker, and that is exactly why I suggest you consider larger numbers of clients and cross-device settings.

For clarity, we would like to reemphasize that our goal is to stress test the worst-case guarantees of Byzantine-robust defenses, and thus we chose our FL settings to be reasonably $\underline{\text{in favor of the defender}}$ (not the attacker): low fraction of Byzantine workers, moderate heterogeneity, SOTA defenses for non-i.i.d. settings, etc...

AGRT of SH2021 are not defense dependent; at best, it is dataset dependent.

We believe that there is a misunderstanding: in Section IV.B, Shejwalkar & Houmansadr (2021) propose using different optimization formulations following the aggregation used. This led us to think that aggregation-tailored attacks are indeed defense-dependent.

Also, in Section VI.C, Shejwalkar & Houmansadr (2021) also utilize the knowledge of server’s aggregations to choose perturbation vectors. Figure 2 also shows that even with the same dataset, different aggregations sometimes have different best perturbation (like in CIFAR10, Krum's best perturbation vector is inverse unit vector, but Trimmed-mean's best perturbation is standard deviation).

The root of unfairness is the fact that JUMP attack uses all the available information, including honest local losses, defense, etc., while the baseline attacks do not, e.g., ALIE, Min-max, Mimic are defense-agnostic, LF, SF are very weak in general.

We have added results for AGRT, which has full knowledge, and is still outperformed by Jump. Besides, the fact that previous attacks have not utilized the open-box adversary's information is arguably not ``unfairness''. A major contribution of our work is precisely on how to leverage the full information to break defenses via the overshooting strategy of Jump.

You note on page 5 that this approach works for any variant of robust D-SGD - but how do these modifications influence the performance of your technique?

This is a good question. First, note that the SOTA defense in Byzantine ML is robust D-SGD with local momentum with pre-aggregation (Allouah et al. 2023, Karimireddy et al. 2022), so our experimental results are shown for this defense. We also test on other variants in Appendix C.2 with less or no local momentum, where we explain that our conclusions regarding the performance of Jump still hold.

Could you explain the segment length in additional detail? At the moment problem $P_l$ implies that the attacker only acts every steps - but this would appear to be contradicted by the loss subfigure from Figure 1.

We explain the steps of the \textsc{Jump} attack in Section 3.2. Segment length $\tau$ is the size of each subproblem $P_\ell$. In other words, we split the whole training process of $T$ iterations into $\lceil \frac{T}{\tau} \rceil$ segments with length $\tau$. Each time we solve a subproblem $P_\ell$, we obtain $\lambda_{(\ell-1)\tau+1}, \ldots, \lambda_{\ell \tau}$ which can be applied to training iterations $(\ell-1)\tau+1, \ldots, \ell \tau$. Hence, after we solve all subproblems, we obtain $\lambda_{1}, \ldots, \lambda_{T}$ which are used to generate the Byzantine vectors for the whole training process.

One of the reasons that JUMP is claimed to work is that it can force trajectory jumps over global minima - however this would seem to be an observation that would be very sensitive to the largest allowable trajectory jumps, and yet this doesn't seem to be a property that has been explored.

This is a very good question. An $*optimal*$ jump is indeed sensitive to the largest allowable trajectory jumps and to the loss landscape. Furthermore, the quality of the landing point influences the effectiveness of our attack, as we explain in Section 4. However, note that the learning rate used is tuned on the Byzantine-free case, and thus is not too large. In fact, we have tested with multiple learning rates, but the strategy followed by Jump, and the optimal attack obtained by solving Problem (P), does not change. This is because we use nonlinear programming (Powell's method in our experiments) to find an optimal jump strategy, including finding the optimal point to do a wise and precise jump, as explained in Section 4.

How would your technique perform in the context of a) more agents, or b) when the number of agents is fixed, but the proportion of byzantine agents increased?

To showcase the strength of our attack, we focus our experiments on small-scale tasks and a low fraction of Byzantine workers. Indeed, the more complex the task, and the larger the Byzantine fraction, the harder it is for the defender and not the attacker. This is why, given that we propose an attack, we focus on this harder setting for the attacker. Finally, we recall that we already conducted a larger number of experiments, for different levels of heterogeneity, on different datasets, and Byzantine fractions.

Clarifying remarks

``critical points'' are also called stationary/saddle points in non-convex optimization, and refer to model parameters where the gradient of the loss is zero.

``greedy'' refers to the attack obtained by setting $\tau$, the segment length, to $1$ in Jump (see Section 3.2). When $\tau>1$, the attack plans malicious gradients for the next $\tau$ iterations, which makes it a non-greedy approach.

``accuracy damage'' refers to the decrease in accuracy (i.e., accuracy with best existing attack accuracy minus accuracy with our attack) relative to the Byzantine-free baseline. We will make these clear in the paper.

We appreciate your response and detailed comments. We will carefully incorporate your writing advice in the paper. We believe we address your concerns below and hope that you re-evaluate our paper in this light. We are happy to answer any further questions.

Why does Table 1 show results that are only positive for your technique, whereas the "full numerical results" from Appendix C2 reveal ranges of setups where your technique is outperformed. This feels as if the main body contents have been pruned to show your technique in the best possible light. Could you explain the choices of content included in Table 1 vs C2?

We recall that the results in the appendices essentially convey the same message as in Section 5, where JUMP outperforms existing attacks across the vast majority of scenarios. It is worth mentioning that the results for $\alpha = 10$ (i.e., low data heterogeneity) are slightly different than those of Section 5 because of the low data heterogeneity. Indeed, in the latter regime, the considered defenses all have excellent accuracies across all attacks, which is predicted by the theory in i.i.d. settings when using local momentum (Farhadkhani et al., 2022). In addition, since real-world federated learning datasets are typically non-i.i.d., we chose the results on CIFAR-10 under moderate heterogeneity setting to show in the table of the main paper.

The concept of robust aggregation processes is to filter out likely adversaries. If all adversaries are equal, then detecting this cluster would likely be a trivial inclusion into robust aggregation. How would your work perform if you were unable to impose uniformity among the adversary update vectors?

First, we agree that Byzantine gradients could be detected by having the aggregation eliminate identical inputs. Please note that it is standard in existing attacks and their implementation to have the Byzantine gradients be identical (Allouah et al. 2023, Karimireddy et al. 2021, 2022, Farhadkhani et al. 2022), since it is generally understood that adding small noise can make the malicious gradients nonidentical and still remain in a bad region of the space. However, such a defense (eliminating dense clusters) does not have theoretical guarantees and can easily be fooled in the presence of data heterogeneity, e.g., Byzantine gradients can gather around points they want to remove, which would be devastating if there is considerable heterogeneity. Also, in our threat model, we assume that one adversary controls several workers, or equivalently that Byzantine workers collude. This makes the problem clear, embodies the worst case, and is also standard in Byzantine Machine Learning works (Allouah et al. 2023, Karimireddy et al. 2021, 2022, Farhadkhani et al. 2022).

How reasonable is the assumption regarding the model dimension? Obviously this is a worst-case assumption, but if the adversary only has access to the local information on the set of compromised agents, does this assumption hold in practice?

We are unsure of what the reviewer meant by ``model dimension''. We assume that they refer to the threat model.

We acknowledge that our attack is open-box and has full knowledge of the system and defense. This is currently stated clearly in sections 1.1 and 2. The purpose of our paper is not to propose a realistic or black-box attack. Rather, we (i) formulate and study the strategy followed by the optimal attack (i.e., solving (P)) in sections 2 and 4, respectively, and (ii) propose a tractable attack which retains most of the strength of the worst-case attack by building on the same strategy, as explained in Section 4. We recall that the aforementioned strategy consists in overshooting minima by amplifying the direction of the average honest gradient, at the right moment of training by being aware of the loss landscape. Furthermore, based on our result, we provide researchers with a tool to stress test the strength of their defenses in the worst case, using one attack, since it is theoretically claimed by Byzantine-robust defenses (Allouah et al. 2023, Karimireddy et al. 2021, 2022, Farhadkhani et al. 2022) to be able to withstand any attack. For example, even with the full knowledge of our attack, the SOTA defenses all perform well under low data heterogeneity, which actually confirms existing theory in the i.i.d. setting (Farhadkhani et al. 2022).

Besides, our attack does not need to know all the data of honest clients; it only needs to know the average of honest gradients (see Algorithm 1) and some proxy data of the same (global) distribution. Although this is not a concern in this paper, but in practice it can be done by eavesdropping and data reconstruction attacks (e.g., gradient inversion). We will emphasize this point further in the paper.

We thank you for your encouraging comments and address your concerns below. We hope that you re-evaluate our paper in this light, and we are happy to answer any further questions.

The proposed JUMP attack assumes that Byzantine clients have access to all data of honest clients. This assumption is almost impossible to hold in real-world applications. I understand that the authors try to explore the worst-case behavior of Byzantine attacks. Given the unpractical assumption of the proposed attack, I still doubt whether these worst-case results make any sense.

We acknowledge that our attack is open-box and has full knowledge of the system and defense. This is currently stated clearly in sections 1.1 and 2. The purpose of our paper is not to propose a realistic or black-box attack. Rather, we (i) formulate and study the strategy followed by the optimal attack (i.e., solving (P)) in sections 2 and 4, respectively, and (ii) propose a tractable attack which retains most of the strength of the worst-case attack by building on the same strategy, as explained in Section 4. We recall that the aforementioned strategy consists in overshooting minima by amplifying the direction of the average honest gradient, at the right moment of training by being aware of the loss landscape.

Furthermore, based on our result, we provide researchers with a tool to stress test the strength of their defenses in the worst case, using one attack, since it is theoretically claimed by Byzantine-robust defenses (Allouah et al. 2023, Karimireddy et al. 2021, 2022, Farhadkhani et al. 2022) to be able to withstand any attack. For example, even with the full knowledge of our attack, the SOTA defenses all perform well under low data heterogeneity, which actually confirms existing theory in the i.i.d. setting (Farhadkhani et al. 2022).

Besides, our attack does not need to know all the data of honest clients; it only needs to know the average of honest gradients (see Algorithm 1) and some proxy data of the same (global) distribution. Although this is not a concern in this paper, but in practice it can be done by eavesdropping and data reconstruction attacks (e.g., gradient inversion). We will emphasize this point further in the paper.

JUMP needs to repeatedly compute the gradients of all honest clients, which is computationally expensive. The computation complexity also increases linearly with the number of honest clients and segment length.

The greedy version of Jump ($\tau=1$, which is the one we recommend) does not need to recompute honest gradients. It only needs to know honest gradients' average of current round, which is common in existing attacks.

We provide an analysis in Section A of the computational cost and also its trade-off with the power of the attack for various segment lengths. Notably, the greedy version of Jump $(\tau=1)$ has a reasonable runtime, especially when considering that future benchmarks will only need to run Jump instead of several other attacks. We could not include this discussion in the main body due to lack of space, and because we admittedly focus on a worst-case unbounded adversary.

Thank you for the detailed responses.

As the author claimed in the response, the recommended greedy version of JUMP attack is effective and does not violate any privacy principle.

However, in this case, the proposed JUMP attack becomes an omniscient version of IPM attack proposed in [1]. And it is well-known that the omniscient version of different attacks can greatly improve their effectiveness [2]. Therefore, the novelty is quite limited.

Therefore, I still maintain my rating.

[1] Xie, Cong, Oluwasanmi Koyejo, and Indranil Gupta. "Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation." Uncertainty in Artificial Intelligence. PMLR, 2020.

[2] Shejwalkar, Virat, and Amir Houmansadr. "Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning." NDSS. 2021.

We thank you for your encouraging comments and address your concerns below. We hope that you re-evaluate our paper in this light, and we are happy to answer any further questions.

You claim that your attack breaks current defenses, but certain defenses in the distributed setting come with proofs (e.g., those based on robust aggregation that use robust statistics and or bagging that even comes with certification). So, how can you "break" a provable defense?

This is a very good question. The state-of-the-art convergence theory (Allouah et al. 2023, Karimireddy et al. 2022) under data heterogeneity only shows convergence to a neighborhood of a stationary point/minimum, where the radius of the neighborhood is proportional to a bound on gradient heterogeneity. Typically, these bounds may be extremely loose, and there is a considerable gap between the theoretical claims and empirical performance. On the other hand, in the homogeneous setting where the convergence neighborhood size can be made arbitrarily small (Farhadkhani et al. 2022), even our strong attack does not significantly hinder SOTA defenses, which in turn confirms existing theory.

The unification of some of the previous attacks as done in Section 4.2 is interesting. Though this framework is clearly not capturing all attacks on distributed learners.

We believe that there is a misunderstanding: we do not claim to unify existing attacks. In Section 4.2, we simply describe existing attacks in a generic way. It is true however that \textsc{Jump} captures several attacks as special cases, e.g., FOE and SF, but this is only a byproduct. We will make this clear in the paper.

The main weakness of the paper is that its attacks is not really "adaptive". Namely, with the assumptions made about the attack's performance (to make it feasible) it is rather easy to detect the Byzantine workers. (e.g., Property 1 and 2 make the adversary's shared values detectable).

First, we agree that Byzantine gradients could be detected by having the aggregation eliminate identical inputs. Please note that it is standard in existing attacks and their implementation to have the Byzantine gradients be identical (Allouah et al. 2023, Karimireddy et al. 2021, 2022, Farhadkhani et al. 2022), since it is generally understood that adding small noise can make the malicious gradients nonidentical and still remain in a bad region of the space. However, such a defense (eliminating dense clusters) does not have theoretical guarantees and can easily be fooled in the presence of data heterogeneity, e.g., Byzantine gradients can gather around points they want to remove, which would be devastating if there is considerable data heterogeneity.

Second, we acknowledge that strong attacks ought to be adaptive, as is Jump and other mentioned attacks. This is not the only advantage of our attack. As we explain in Section 4, among other factors, the main advantage of Jump is its ability to overshoot minima. This requires planning, which is arguably a stronger form of adaptivity, and is enabled by collinearity and also the maximization of the loss across time within a certain segment length.

Clarifying remarks

We would like to clarify that the simplifications made to obtain Jump are not properties. We essentially go from a natural Byzantine attack formulation in (P) to a simpler optimization formulation. In Section 4, we show that each simplification only marginally reduces the strength of the ``strongest" attack obtained by solving (P) directly.

We thank you for your encouraging comments and address your concerns below. We hope that you re-evaluate our paper in this light, and we are happy to answer any further questions.

This paper remains focused on the most basic and standard problem setting, hence the novelty of this paper is limited in this sense.

We acknowledge that the Byzantine attack and defense problem in distributed learning systems is a well-studied problem. However, given the lack of works investigating worst-case Byzantine attacks in the standard Byzantine ML problem, we believe that our contribution is valuable to the community without the need to explore other variants of the problem. We will add the reference mentioned by the reviewer in our paper.

This paper simplifies the problem by restricting the solution space to rank-1 vectors that are co-linear with the average of honest workers. Although this idea is interesting, this paper missed many ideas and methods developed in recent years, e.g., by treating the original attack problem as a bilevel optimization problem and employing more sophisticated bilevel optimization algorithms. It remains unclear how well the simplified strategy in this paper will perform when compared to these methods. Also, how about other simplified and restricted solution spaces, e.g., rank-2, rank-3, etc.?

We recall that the approach leading to the simplified optimization problem of Jump is principled and does not necessitate exploring, e.g., rank-two solution spaces. Indeed, in Section 4, we show that the successive simplifications do not significantly degrade the power of the attack.

The solution quality of the Jump method clearly depends on the nonlinear optimization solver. The authors only used Powell's method. This paper can benefit from testing and comparing more nonlinear solvers, and analyzing the impact of different nonlinear solvers on the proposed Jump method.

In Section 3.2, we discuss appropriate nonlinear solvers for our tasks. We recall that the constraints of Problem $(P_\ell)$ are in general non-differentiable due to robust aggregation. This motivates the use of derivative-free non-linear solvers such as Powell’s (Powell, 1964), Nelder-Mead’s (Nelder & Mead, 1965), and Differential Evolution (Storn & Price, 1997). In fact, we have tested all the aforementioned methods on MNIST and our two-dimensional tasks. Our experiments have shown that Powell's method solver is most effective while Differential Evolution can obtain better solutions but is much slower than Powell's, so we use Powell's in our main experiments. We will add a detailed description in the paper.

Although the authors conducted extensive numerical studies, most of the experiments were conducted on CNN with MNIST and CIFAR-10, which is now considered relatively easy datasets.

We use heterogeneous variants of MNIST and CIFAR-10, where the extreme heterogeneity scenario is challenging and is common in Byzantine-robustness works (Allouah et al. 2023, Karimireddy et al. 2022). In any case, note that the more challenging the task, the harder it is for the defender and not the attacker, which is why we focus on moderate heterogeneity, or low fraction of Byzantine workers.