Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers federated learning over non-iid data in the presence of Byzantine nodes. The authors propose to use a technique linear scalarizatoin (LS) to help other aggregators to achieve better performance. For example, instead of applying coordinate-wise median (CM) directly,  the CM+LS algorithm computes an aggregation weight for each gradient inversely proportional to their distance to the median. In this way, LS does not discard gradients but gives higher weight to good gradients. The empirical performance looks very nice but no theoretical guarantee is provided.
strength_and_weaknesses: Strength:
- Good empirical performance.

Weakness:
- I am not convinced that LS addresses the essence of the non-iid issue, although it may reduce the influence of non-IID data distribution. Take CM+LS (algorithm 2) in the appendix for example. If there is no Byzantine workers and 49% of gradients are 0 while 51% of gradients are 1, then the output of CM+LS will be the same as CM which is 1. However, an ideal aggregation is expected to output something close to 0.5. 

- There is no convergence guarantee as has been mentioned in the paper. A theoretical convergence guarantee is quite important because Byzantine robustness is designed to defend for all possible attacks. On the other hand, empirical evaluation only demonstrates its performance on a few attacks ---- there may exist some attacks that are designed to attack LS.

- Not clear how the number of tolerated Byzantine nodes changes with LS technique.


clarity,_quality,_novelty_and_reproducibility: This paper is mostly clear and novel but I am worried about its guarantees.
summary_of_the_review: I would recommend borderline rejection because it does not address the main problem studied in the paper (non-iid) and there is no convergence guarantee.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The focus of this paper is on Byzantine-robust distributed learning. The authors in particular emphasize the setup where there is non-iid data across different clients. The main contribution in the paper is an algorithm in which the gradients from the clients are combined using a convex linear combination where the coefficients in the combination come from one of the robust aggregation rules that exist in the literature. The paper then provides several numerical results to showcase the benefits of the proposed algorithm.
strength_and_weaknesses: **Strengths**

- The results reported in the paper highlight the usefulness of the proposed method.

**Weaknesses**

- The paper has an incremental nature and the main contribution is minor in nature, which involves taking a convex linear combination of the gradients. There are no theoretical guarantees for the proposed algorithm and all the aggregation rules discussed in the paper have already been studied in the literature, along with rigorous guarantees. The connections to multi-objective optimization are also tenuous.
- Some of the claims made in the paper are either incorrect or misleading. E.g., "the main Byzantine defenses rely on the IID assumption causing them to fail when data distribution is non-IID even with no attack" is an incorrect statement (see, e.g., the supplementary material in BRIDGE: Byzantine-Resilient Decentralized Gradient Descent). Similarly, "Another weakness of current aggregations is that they all aim at totally discarding outliers for the sake of granting resilience." is a misleading statement. In the case of coordinate-wise trimmed mean, e.g., the final gradient typically gathers information from all the clients. And in the case of other aggregation rules, even when a client is excluded in one iteration, it can come back into the calculations in another iteration. The point of this discussion is not to dispute the idea that a better aggregation rule, such as the one proposed in this paper, might lead to better outcomes. The purpose is, however, to emphasize that the authors need to think a bit harder about their claims and reframe their contributions in light of these facts.
clarity,_quality,_novelty_and_reproducibility: - The paper is well written and is of good quality. The novelty of this work is limited because of its incremental nature.
- Since there is no link to a public repo provided in the paper, this reviewer cannot comment on the reproducibility.
summary_of_the_review: While the paper is studying an important problem and the approach taken in the paper seems to be effective, the authors should build further on this work. Some more insights into the strength of this work as well as theoretical contributions would make this a stronger paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper focuses on Byzantine-robust learning when the data is heterogeneous. The authors propose a novel Linear Scalarization (LS). LS first uses RAGG to split gradients into honest gradients and suspected malicious gradients. Then, LS uses a selection criterion to compute weights for all gradients. In particular, LS assigns higher (lower) weights for honest (suspected malicious) gradients. Finally, LS computes the weighted average as the aggregated gradient.
strength_and_weaknesses: strength:

* The idea of trading off between granting Byzantine resilience and inclusion when the data is heterogeneous is interesting.

weaknesses:

* Proposed LS is not applicable to all RAGGs. Many RAGGs do not split gradients into honest gradients and suspected malicious gradients, e.g., trimmed mean [1], and geometric median [2]. How can LS enhance these methods?

* The selection criterion $C_{R_i}$ is important for LS. Elaborate more on how to choose an appropriate $C_{R_i}$.

* Incomplete experiment results. The performance against attack BF on MNIST under $\beta=0.01$ is missing (Figure 3); the performance against attack BF on MNIST under $\delta=40\%$ is missing; the performance against attacks BF, IPM, and ALIE on SVHN is missing; the performance against attacks BF and ALIE on CIFAR-10 is missing,

* Experiments on different $\alpha_t$s and $\alpha_b$s are expected. I am particularly interested in the case where $\alpha_t=\alpha_b$.

* I am wondering about the effect of applying LS to a particular defense DnC [3]

* The introduction of different RAGGs in Section 3.1 seems unnecessary.

[1] Yin, Dong, et al. "Byzantine-robust distributed learning: Towards optimal statistical rates." *International Conference on Machine Learning*. PMLR, 2018.

[2] Pillutla, Krishna, Sham M. Kakade, and Zaid Harchaoui. "Robust aggregation for federated learning." *arXiv preprint arXiv:1912.13445* (2019).

[3] Shejwalkar, Virat, and Amir Houmansadr. "Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning." *NDSS*. 2021.
clarity,_quality,_novelty_and_reproducibility: The paper needs to be further polished. There are still important issues in the proposed defense that need to be addressed. The authors do not provide code for reproducibility.
summary_of_the_review: The idea of trading off between granting Byzantine resilience and inclusion when the data is heterogeneous is interesting. However, some details of the proposed method need to be specified, and further experiments are needed to validate the efficacy of LS. Therefore, I think the paper is below the bar of ICLR.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this work, the authors study Byzantine-robust distributed learning on heterogeneous data and propose a new method called linear scalarization, where derailed clients are penalized via a trade-off vector. The proposed method is empirically compared with existing methods on several datasets.
strength_and_weaknesses: The proposed method, called linear scalarization (LS), does not introduce too much computation cost and is easy to implement. However, there are also some concerns as follows.

1. The proposed method lacks enough theoretical support. LS is based on the existing aggregators RAGG, which are not robust on non-IID data, as mentioned in the paper. The split based on the chosen RAGG may be unreliable. Why the method based on a not robust aggregator is robust? It lacks theoretical support or even informal discussion about this.

2. There are two extra hyper-parameters $\alpha_t$ and $\alpha_b$ in the proposed method. However, there is not an adequate discussion on how to properly set the hyper-parameters. Meanwhile, the effect of the two hyper-parameters is not adequately studied in this work.

3. It is reported in [1] that bucketing with centered-clipping (CClip) and robust federated aggregation (RFA) has much better empirical performance. Given this, the comparison in this paper seems unfair.

4. In equation (2) (page 2), does it require that $\lambda_i \geq 0$? An explicit explanation is required here.

5. What is the definition of $\delta_{max}$ (page 2)? Is it the upper bound of $\delta$? Moreover, since there are $n$ clients in total, does $\delta<\frac{1}{2n}$ mean that there is no Byzantine client?

6. At the end of the paragraph about IID defenses (page 3), 'in the non-IID setting' --> ' in the IID setting'.

7. In the definition of CM (page 4), $M$ is defined to be an index while in the definition of Aksel, $M$ is defined to be a vector. The inconsistency will make readers confused. Meanwhile, it is suggested to represent vectors with bold letters, in order to avoid confusion.

8. What is the meaning of the abbreviation 'MOO' (the first paragraph of page 4)? Does it mean 'multi-objective optimization'? Readers can be confused by this.

9. There exist some typos and improper citation format. For example, there are several missing parentheses around the references in the paragraph about IID defense (page 2), in Section 3 (page 4), and in Section 4.1 (page 5). In the definition of Aksel (page 4), 'Combines' --> 'combines'. 

[1] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. "Byzantine-robust learning on heterogeneous datasets via bucketing." arXiv preprint arXiv:2006.09365 (2020).
clarity,_quality,_novelty_and_reproducibility: The readability of this paper is not good and many claims are not well-supported. Please see the concerns listed above for details.
summary_of_the_review: This paper is not well-written. Meanwhile, the claims lack theoretical support and the empirical comparison is not solid enough. Given the reasons, there is much room for improvement and this work is currently below the acceptance threshold.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies Byzantine-robust distributed learning. It proposes to use existing gradient aggregation rules to derive weights for each contribution, aiming to give higher weights to trusted collaborators.

Unfortunately concerns remained from the reviews both on fundamentals (such as the fact that no convergence guarantees are given) and experiments, as well as the applicability to the important case of heterogeneous data. 

We hope the detailed feedback helps to strengthen the paper for a future occasion.
justification_for_why_not_higher_score: Main concerns remained from all reviewers
Decision: Reject