Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors consider Byzantine-robustness of a distributed learning system in the setting of non-iid data distribution. The bucketing technique is applied to reduce the heterogeneity across the workers. To further reduce the variance within each worker, the authors adopts the momentum technique. These two techniques can be combined with various robust aggregation rules. The authors prove the convergence of the combined methods, and show that they reach the lower bound. The authors also claim that for the over-parametrized case, the negative impact of data heterogeneity can be eliminated.
main_review: 0. The investigated problem, Byzantine-robust distributed learning over non-iid data, is important. The algorithm development and the analysis both contain new results
1. In the previous version of this paper, the authors propose resampling to reduce the heterogeneity across the workers. Why do the authors switch to bucketing in this version?
2. In Page 2, the authors claim that “none of these (non-iid Byzantine-robust) methods are applicable to the standard federated learning.” Please justify this claim.
3. Related to the above comment, the authors do not compare the proposed methods with any other non-iid Byzantine-robust methods.
4. Also about the numerical experiments, the MNIST dataset is too simple. Testing on one or two additional large datasets could make the results more convincing (in particular, for the over-parametrized case).
5. In Section 3.2, the mentioned mimic attack has appeared in other papers that investigate non-iid Byzantine-robustness. Please cite.
6. In Section 4.2, why place centered clipping here? It should be located in Section 3.
7. The role of momentum is not well investigated. The authors should indicate its contribution to the performance improvement. 
8. For the numerical experiments of the over-parametrized case, the authors use centered clipping as the basic aggregator. But centered clipping has certain robustness in the non-iid setting. Using other base aggregators, such as geometric median, could be better here.
9. Theorem IV requires that B^2 is sufficiently small. Please check whether this condition can be satisfied in the numerical experiments.

summary_of_the_review: Overall, this paper has publication merits, but some issues need to be addressed.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper focuses on Byzantine-robust federated learning, a learning paradigm where a centralized server coordinates learning across a data set partitioned across multiple worker nodes, some of which are adversarial. Typically this is done via robust aggregation schemes which ensure that adversarial nodes do not hinder learning.  In this setting, the author's main focus is on studying the setting where honest worker nodes own heterogeneous data sets. As the authors mention, the existing literature on Byzantine-robust federated learning focuses on the setting in which honest worker nodes draw iid samples from an underlying data distribution, and although there is also existing literature on (non-Byzantine) federated learning over heterogenous data distributions amongst nodes, this work brings these two strands of research together. 

The main results are the following: 
-Providing (simple) settings and empirical results wherein common aggregation methods fail in the presence of heterogeneous data, even when there are no adversarial nodes.
-Providing a specific attack vector for the heterogeneous Byzantine setting, whereby adversarial nodes choose an honest node to replicate ("Mimic" attack). This exposition comes with an efficient algorithm for computing the most "hurtful" choice of node to mimic, and the authors empirically demonstrate the potential of this attack against common aggregation methods
-Formally defining the design objective of "Agnostic Robust Aggregators", which quantifies degradation of aggregator performance as a function of byzantine tolerance and dataset heterogeneity.
-Providing a simple randomized bucketing scheme. Messages from nodes are randomly averaged in buckets, where the number of buckets is a free parameter. Increasing the number of buckets reduces the variance of bucket representatives, but potentially increases the number of byzantine agents (post-bucketing). If there is sufficient margin in existing aggregation protocols, performing judicious bucketing before applying the aggregation rule permits making Agnostic Robust Aggregators out of existing aggregation schemes (with specifically quantifiable guarantees). 
-The authors also theoretically study optimization methods that make use of aggregation methods (via stochastic gradient descent). In this setting they provide upper bounds on convergence rates of optimization using robust aggregators (in terms of the parameters that govern the robustness of aggregation method as per Definition A), and show that these upper bounds match existing upper bounds in the case where there are no byzantine agents (\delta = 0) or when data is homogeneous (\rho = 0). In the regime where these terms are non-zero, convergence is not guaranteed, but via information theoretic methods, the authors also provide a matching lower bound
-If heterogeneity bounds are more refined (whereby gradient variation is bounded by the order global gradient of the entire dataset), then the authors demonstrate convergence of robust aggregation methods on SGD. This setting applies when systems are over-parameterized. 
-Finally, the authors provide multiple experimental results that validate the theoretical findings of the work.
main_review: Strengths:
-I think that this is an elegant way of combining two key areas of work in the FL community: non-iid data sets + Byzantine nodes 
-Empirical results seem robust
-The bucketing model is simple, believable, and it is nice that it composes well with existing methods. 
-The theoretical analysis of the model is extensive: it matches existing bounds when \delta or \rho=0, and the lower bound matches the non-trivial term that occurs when both \delta,\rho \neq 0. 

Weaknesses:
-Are there more complicated examples of non-iid models under non-adversarial attacks that perform poorly? The Rademacher distribution is a good starting point to justify the analysis, but seeing the performance of existing aggregators on more complicated data sets when \delta=0 would be interesting. 
- Still not convinced about the upper bound on gradient norm in the over-parameterized setting (where the term is bounded by B \times \grad f(x)). Is this realistic? Perhaps I am not seeing how this falls out of over-parameterization. A note on this might be useful in the write-up of the paper.
-The lower bound analysis (Theorem 3) could have some more intuition as well, in terms of what the argument is like, and what the functions that are used consist of. In particular, it would be interesting to note whether the author thinks the adversarial functions for the bound are efficiently computable, and if not, whether hard functions can occur in practice over the byzantine nodes (could this happen without some amount of coordination amongst the byzantine nodes for example?)
-What about other types of attack objectives, i.e. backdoor attacks (this seems highly relevant in the non-iid setting, especially if the adversary has knowledge of which clients have which data)

summary_of_the_review: I recommend this paper for acceptance. This seems like a fitting extension of existing work, and the authors have provided a corresponding framework for quantifying performance loss in the presence of byzantine agents and heterogeneous data for federated learning. Their results match existing work in regimes when there are no byzantine agents, and when there is a lack of heterogenous data. Furthermore, the non-trivial loss of performance in the regime where both byzantine agents and heterogenous data is present is accounted for in a matching lower bound. These results will be of interest to the growing body of work in federated learning at ICLR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a bucketing scheme for robust distributed learning with heterogeneous data. Gradients are more homogeneous after bucketing, which will increase the robustness of existing algorithms. The author provides theoretical analysis as well as empirical results.
main_review: ## Strengths
The bucketing scheme proposed in this paper is interesting. It is easy to adopt and does not bring much extra computational cost, but can improve the performance of existing Byzantine-resilient algorithms, as shown in the empirical results. Also, I appreciate that the authors provide convergence results for general aggregation rules, together with precise analysis for three common aggregation rules in Theorem I.

## Weaknesses
When decreasing the heterogeneity, the bucketing scheme also reduces the number of candidate vectors (gradients). However, in the worst case, the number of corrupted vectors will remain the same. Thus, the number of Byzantine workers that can be tolerated will decrease to $1/s$ when adopting bucketing. Although the empirical results show that $s=2$ is sufficient to overcome heterogeneity, the number of Byzantine workers that can be tolerated already drops by half in this case. I am not aiming to criticize the bucketing scheme but to point out the limitation. I think that this problem has truly restricted the application prospects of bucketing in general cases.

summary_of_the_review: Although there are weaknesses in this work, considering the challenges from heterogeneity, I think this work is slightly above the threshold.

--------
(Post-rebuttal)
My major concerns have been properly addressed by the authors and the quality of this paper has been improved after revision. Thus, I have raised my rating.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: The paper provides a systematic and deep theoretical study of the problem of Byzantine-robustness in the heterogeneous setup, i.e., when workers have non-identical datasets and, as s result, their local loss functions are non-identical. The authors prove that even under bounded heterogeneity it is impossible to provably achieve any predefined accuracy of the solution by any method. Next, the authors propose and analyze an algorithmic tool called *bucketing* and show that it makes some known aggregators such as Krum, coordinate-wise median, and geometric median to be *agnostic* robust aggregators. Under bounded heterogeneity assumption, the authors derive that Robust Client Momentum method from (Karimireddy et al., 2021) converges for non-convex problems to a neighborhood of a stationary point. Next, it is shown that the size of the neighborhood can be made arbitrarily small for over-parameterized problems. Numerical experiments corroborate theoretical findings and, in particular, show the benefits of the proposed bucketing procedure.

Overall, the paper is well-motivated, clearly written, and contains solid contributions. There are also some minor inaccuracies in the proofs, small typos, and other minor weaknesses -- I list them below. I encourage the authors to address all of them.
main_review: ## Strengths
1. **Lower bounds for Byzantine-robust optimization under bounded heterogeneity.** In Theorem III, the authors prove that even in the case of bounded heterogeneity (in the classical sense for papers on FL) one cannot achieve any predefined accuracy even for the strongly convex problems. In particular, they prove that functional suboptimality cannot be made smaller than $\Omega(\frac{\delta \zeta^2}{\mu})$ ($\mu$ - str. convexity parameter, $\delta$ - fraction of Byzantines, $\zeta^2$ - dissimilarity measure of the gradients of local loss functions). Typically, $\mu$ is quite small and $\zeta^2$ can be large for some FL problems when the clients naturally have highly heterogeneous data. In such situations, the lower bound is really pessimistic. Although this fact (Theorem III) is expected for the experts in optimization, it is very important for the field of Byzantine-robust optimization: it creates a clear picture of the limits of robustness.

2. **New upper bounds for Byzantine-robust optimization under bounded heterogeneity.** The authors prove new complexity bounds for Byzantine-robust optimization under bounded heterogeneity in the non-convex case. The derived results match the established lower bound. Moreover, it is shown that one can achieve any predefined accuracy (Theorem IV) when the heterogeneity level at the point $x$ is proportional to $\|\nabla f(x)\|^2$ (can be seen as a strong growth condition from (Vaswani et al., 2019)).

3. **Bucketing as a tool to make Krum, Geometric Median, and Coordinate-wise Median robust.** (Karimireddy et al., 2021) show that even in the homogeneous case Krum, Geometric Median, and  Coordinate-wise Median are provably non-robust to Byzantine attacks. This work fixes this drawback of the mentioned aggregation rules (Theorem I) via a simple tool called bucketing. This result (together with Theorem II) is very important for Byzantine-tolerant optimization in the homogeneous case, since Krum, Geometric Median, and Coordinate-wise Median were not analyzed previously without restrictive assumptions. 

4. **Clarity.** The paper is well-motivated, clearly written, and has a good structure.

## Weaknesses
1. **Inaccuracies in the proofs.** I have checked all the proofs and noticed several inaccuracies and unexplained derivations. Although it is possible to fix all the issues, in the current shape, it is hard to follow some parts of the proofs. I list all my questions and comments in section **Questions and comments about the proofs** of my review.

2. **Comparison with related work.** Unfortunately, it is not trivial to compare the results from this paper with other related works given the information provided in the related work section. The current version of the related work section summarizes the known works without going into the details. However, it is important for the paper to provide an explicit comparison with the related works (with the discussion of the derived rates and assumptions). I strongly encourage the authors to provide such a comparison at least in the appendix. Moreover, the authors should pay a lot of attention to the comparison with Yang & Li (2021) since they also use bucketing.

## General questions and comments
1. **Abstract, sentence "Our work is the first...":** This sentence is not correct since Li et al. (2019) also derive convergence results under realistic assumptions for strongly convex problems. Perhaps, the authors wanted to emphasize that their work provides the first guarantees under the not too strong assumption in the non-convex case.

2. **Page 2, "However, none of these methods are applicable to the standard federated learning."** This claim requires additional clarifications. For example, it is not clear why the method from Li et al. (2019) is not applicable.

3. **Definition A:** I suggest the authors additionally emphasize that this definition is useful for both homogeneous and heterogeneous cases.

4. **Remark 3:** This is 1 iteration of CClip, which is not necessarily the output of the aggregator.

5. **Second paragraph after Remark 4, "... which matches the optimal iid Byzantine robust rates of (Karimireddy et al., 2021)".** It is not clear why the mentioned rate is optimal (and in what setting). Karimireddy et al. (2021) do not prove the lower bound. Moreover, there is a recent work, where the better rate is achieved (in terms of the number of iterations): Gorbunov et al. "Secure Distributed Training at Scale." arXiv preprint arXiv:2106.11257 (2021).

6. **Page 7, the sentence above Theorem 7, "... typically holds in most realistic settings (Vaswani et al., 2019".** Vaswani et al. (2019) do not provide evidence that this assumption holds in most realistic settings. In fact, they show it (Strong Growth Condition) for an example of squared hinge-loss in the case of linearly separable data. They also prove that Strong Growth Condition follows from the interpolation condition when the summands in the loss function are smooth and the loss satisfies PL-condition. However, in this case, the known bound upper bound for $B$ is proportional to $\frac{L}{\mu}$ where $L$ is the maximal smoothness constant of $f_i$ and $\mu$ is the PL-parameter of $f$. Therefore, the current theoretical estimates for $B$ are quite large even for simple special cases.

7. **Theorem IV, condition $B^2 < \frac{1}{3c\delta}$.** In view of my previous comment, this requirement may imply that $\delta$ is tiny. I think the discussion of this requirement should be added to the paper.

8. **Missing reference.** This work also addresses the heterogeneous case for Byzantine-robust optimization: *Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583–4596, 2020.* Moreover, Wu et al. (2020) also prove convergence guarantees under similar assumptions. Therefore, a detailed comparison of the derived results should be added.

9. **Conclusion, the last sentence, "... our results represent a major breakthrough..."** Although the work makes a strong contribution to the field, in my opinion, it cannot be called a breakthrough taking into account that many of the building blocks were known and analyzed to some extent (bucketing, client momentum). I think only a couple of papers can be called a breakthrough objectively (e.g., Nesterov's acceleration and discoveries of the same caliber). So, I suggest the authors rewrite the sentence: let the readers decide for themselves whether this paper is a breakthrough or not.

## Questions and comments about the proofs
1. **Proof of Lemma 1, formula for $\mathbb{E}_{\pi}[y_i | i \in \widetilde{\mathcal{G}}]$:** this is true, but the detailed derivation should be added.

2. **Lemma 7.** First of all, the lower and upper bounds should be multiplied by $n$. Moreover, I have the following question about the proof of the lower bound: does the described distribution of $y_i$ correspond to any distribution of the initial vectors $x_i$ before the bucketing? This is crucial for the correctness of the lower bound.

3. **Page 20, robustness of Krum.** The first formula is not proven. Moreover, it is not clear what is $S^{\ast}$. Next, in the formula above "Taking expectation now on both sides yields" the minimization should be taken over the sets $S$ such that $|S| = \frac{3m}{4}$. In the next formula, it seems that the numerator should contain $4n\tilde{\rho}^2$. After that, the sentence "Then, the number of Byzantine workers can be bounded as $|\tilde{\mathcal{B}}| \leq m(1/4 - \delta)$" should be rewritten as "Then, the number of Byzantine buckets can be bounded as $|\tilde{\mathcal{B}}| \leq m(1/4 - \nu)$". Finally, in the upper bound for $\mathbb{E}\|y_{k^\ast} - \bar{x}\|^2$ the denominator of the first fraction should have $\nu m$ instead of $\nu n$.

4. **Page 21, robustness of Geometric median.** In the third sentence, the word "worker" should be replaced by "set"/"bucket". There is also a typo in the formula after the words "Squaring both sides, expanding, ...": the sum in the first row should not have $\mathbb{E}$ inside.

5. **Appendix D, the proof of Theorem III.** The first formula should contain $\delta$ instead of $\hat\delta$. Next, the formula after the words "Note that the gradient heterogeneity ..." should be supported by the full derivation (or explained). It is true but requires few extra steps.

6. **Proof of Lemma 8** contains several inaccuracies and unexplained derivations. First of all, what is $\mathbb{E}[\cdot | i]$? If it is an expectation conditioned on $i$, then $\mathbb{E}[g_i(x^{t-1}) | i] \neq \nabla f_i(x^{t-1})$ since $x^{t-1}$ depends on the stochasticity not related to the choice of $i$. But the proof uses $\mathbb{E}[g_i(x^{t-1}) | i] = \nabla f_i(x^{t-1})$. This should be fixed (here and below). Next, it is not clear what is $\mathbb{E}_i[\cdot]$. The first formula on page 24 is incorrect due to the same reason as the first formula in the proof. This issue should be fixed as well. The second formula on page 24 is also inaccurate: the RHS should have $\zeta^2(1 - (1-\alpha)^t)$. Next, there is a typo in the sentence "This is because the randomness in the sampling...". Finally, the last sentence in the proof the authors claim that it is enough to apply Definition A, but it is not correct: this definition requires $\mathbb{E}\|m_i^t - m_j^t\|^2 \leq \rho_t^2$ while the authors prove a weaker result that $\mathbb{E}_i\|m_i^t - \bar{m}^t\|^2 \leq \rho_t^2$. Overall, the proof of Lemma 8 requires a major revision (and, probably, Definition A should also be changed to fit the proof).

7. **Lemma 10.** Numerical constants are incorrect: instead of $\frac{2\alpha}{5}$ the formula should have $\frac{5\alpha}{16}$ and instead of $\frac{\alpha}{10}$ one should have $\frac{3\alpha}{32}$.

8. **The proof of Theorem V** contains several places that should be better explained (and, most likely, corrected, because of the inaccuracies). First of all, it seems that the authors forgot to upper bound $\mathbb{E}\|m_t - \bar{m}_t\|^2$: it is contained in the RHS of the second formula in the proof, but it is omitted in the derivations on page 26. Next, the last formula on page 25 is inaccurate: one should have $\nabla f(x^{t-1})$ in the RHS. Moreover, the next step in the proof is unclear: it seems that a lot of derivations are omitted. For me, it is not clear how the term $\mathbb{E}\|m_t - \bar{m}_t\|^2$ is handled. Therefore, this derivation should be significantly rewritten and checked.

## Minor comments
1. **$|\mathcal{B}| = f$.** The symbol $f$ is already used to denote the objective function. I suggest using a different notation for the number of Byzantines.

2. **Lemma 1.** $\widetilde{\mathcal{G}}$ is defined only in the proof. The authors should add the definition in the statement of the lemma.

3. **Figure 9** contains low-resolution images. The authors should replace them with the ones with higher resolution.

4. **Page 18, the last formula:** full stop is missing in the end of the of the formula (please, check other formulas that end sentences as well).

5. **Page 19, the second sentence, "... each can belong to only 1 bucket each":** one "each" should be removed.

6. **Lemma 9.** In this lemma, the authors use $m_t$ instead of $m^t$. The notation should be unified.

7. **Lemma 10.** The authors use $x_{t-2}$ and $x^{t-1}$. The position of the indices should be unified.
summary_of_the_review: To sum up, I am sure that the paper should be accepted to the conference after minor improvements. If the authors apply all necessary corrections and address my comments properly, I will increase my score: the paper deserves acceptance as a spotlight or even oral talk.
review_title: null

Meta-review: This manuscript proposes and analyses a bucketing method for Byzantine-robustness in non-iid federated learning. The manuscript shows how existing Byzantine-robust methods suffer vulnerabilities when the devices are non-iid, and describe a simple coordinated attack that defeats many existing defenses. In response, the primary algorithmic contribution is a bucketing approach that aggregates subgroups of devices before robust aggregation. This approach is also easily composed with existing Byzantine-robust methods. The manuscript includes an analysis of the performance of the proposed approach, including an information-theoretic lower bound for certain settings.

During the review, the main concerns are related to the clarity of the technical contributions, and unclear technical statements. The authors respond to these concerns and have satisfied the reviewers. After discussion, reviewers are generally strongly positive about the strength of the manuscript contributions. The authors are reminded to make the final changes agreed in the public discussion e.g., discussion of the reduction to SGD when  $\delta=0$
Decision: Accept (Spotlight)