Comparison under optimal attacks: We compare the different defense algorithms under optimal attack scenarios. Figure REF  compares our scheme Aspis with the baseline implementation of coordinate-wise median (\(\epsilon =0.133, 0.267\)  for \(q=2,4\) , respectively) and DETOX with median-of-means (\(\epsilon =0.2, 0.4\)  for \(q=2,4\) , respectively) under the ALIE attack. Aspis converges faster and achieves at least a 35% average accuracy overhead (at the end of the training) for both values of \(q\)  (\(\epsilon ^{Aspis}=0.004, 0.062\)  for \(q=2,4\) , respectively). In Figures REF , REF  we observe similar trends in our experiments with Bulyan and Multi-Krum where Aspis significantly outperforms these techniques. For the current setup, Bulyan is not applicable for \(q=4\)  since \(K = 15 < 4c_{\mathrm {max}}^{(q)}+3 = 4q+3 = 19\) . Also, neither Bulyan nor Multi-Krum can be paired with DETOX for \(q \ge 1\)  since the inequalities \(f \ge 4c_{\mathrm {max}}^{(q)}+3\)  and \(f \ge 2c_{\mathrm {max}}^{(q)}+3\)  cannot be satisfied. Please refer to Section REF  and Appendix Section REF  for more details on these requirements and the values of \(c_{\mathrm {max}}^{(q)}\)  and \(\epsilon \)  each scheme can achieve. The results for the reversed gradient attack are shown in Figures REF , REF  and REF . Given that this is a much weaker attack [1]}, [2]} all of the schemes considered, including the baseline methods, are expected to perform well; indeed in most of the cases, the model converges to approximately 80% accuracy. However, DETOX fails to converge to high accuracy for \(q=4\)  as in the case of ALIE; one explanation is that \(\epsilon ^{DETOX}=0.4\)  for \(q=4\) . Under the Fall of Empires (FoE) distortion (cf. Figure REF ) our method still enjoys an accuracy advantage over the baseline and DETOX schemes; this accuracy gap becomes more important as the number of Byzantines in the cluster increases.
