Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Many existing researches on distributed deep learning works in byzantine robustness in a centralized PS setting under the assumption of i.i.d. data distribution on workers, e.g. KRUM. This paper presents a simple resampling scheme that adapts the existing robust algorithms to heterogeneous datasets (referred as KRUM-RS later in this review). It firstly proposes two new attacks under non-iid data distribution that fooled byzantine fault tolerant algorithms like KRUM, Coordinate Median (CM), and RFA (Normalized Median-NM or Geometric Median-GM). Then it proposes the RS algorithm and proved its theoretical convergence guarantee the of KRUM algorithm over non-iid data, and when the parameter server (PS) does not control the dataset distribution. Experiments showed the convergence guarantee over KRUM and even CM, NM/GM algorithm. 
 
The proposed resampling algorithm is somewhat novel and can be applied to KRUM to guarantee its convergence. The paper is technically sound. The organization of this paper is OK, but it lacks clarifications on its intuition on the sampling method (why and how it improves other methods by sampling). The technical part is not self-contained. For example, in Def. A, what does it mean for r=2,3,4 that E(F) <= E(G)?  More clear explanation and definition should be present.


This paper seems to over-claim some of its results: for example, this paper claims that "We propose a simple new resampling step which can be used before any existing robust aggregation rule", but the theoretical analysis only applies to the rule from KRUM. How could one should the new resampling method work for any robust aggregation rule? There seems to be a large gap here.

review_title: This paper proposes an attack on distributed training with heterogeneous data distribution, along with a defense to it  

final_score: rating: 7: Good paper, accept
review_content: In this paper, the authors propose the resampling mechanism to improve the performance of existing robust statistics method for Byzantine-robust distributed SGD. Both theoretical and empirical analysis are provided. In overall, the proposed method is technically sound, and works well in practice.

Here is some detailed comments:

1. According to my understanding, the resampling mechanism is actually trying to convert non-iid gradients into iid ones. If an averaged random subsample of gradients contains only good gradients, then sampling with replacement makes it an unbiased estimator. If the averaged random subsample contains Byzantine gradients, then it is corrupted anyway and we don't care it's biased or not. Thus, for the averaged subsamples containing no Byzantine gradients, they actually become iid. Is my understanding correct?

2. The idea is simple and easy to implement upon all the previous work. Some people may think this work is incremental, but I think the simplicity of the proposed method is an advantage.

3. It will be better if the authors also provide the convergence analysis of resampling with CM. For Krum, note that larger n (number of workers) actually results in worse convergence in Theorem II, which questions whether we should use distributed training.
review_title: Simple idea with good performance in practice and easy to implement, good paper

final_score: rating: 6: Marginally above acceptance threshold
review_content: Paper summary:

The paper studies Byzantine robustness in the context of distributed learning from heterogeneous datasets. This problem has been widely studied previously, but under the additional assumption that the data of the good workers is i.i.d.. The authors give examples of situations and poisoning attacks with which current defences designed for the i.i.d. situation can be overcome.  They also propose a simple resampling scheme that can be used as a preprocessing step before applying any standard robust aggregator from the i.i.d. literature. They provide theoretical guarantees for their resampling scheme when used together with KRUM. The also test their algorithm against the i.i.d. baselines and multiple attacks. 

##########################################################################

Pros:

- The paper is well-written and motivated and addresses an important problem. Indeed, in the context of distributed and federated learning, where privacy and communication costs are of particular importance, the problem of corrupted or adversarial updates becomes very relevant.
- The gap between existing defences and the non-i.i.d. setup is well-motivated, with various examples and attacks proposed in the paper.
- The proposed resampling scheme is simple and easy to incorporate into previously proposed algorithms. It is also amendable to theoretical analysis, as shown in the paper.
- The experimental evaluation does show clear improvements in many cases when the resampling scheme is used.
    
##########################################################################

Cons/suggestions:

- While heterogeneous data is allowed, the assumption on the top of page 2 that the variance between the gradients of the local datasets is bounded is somewhat unintuitive to me. It seems like this is not just the usual assumption that the variance of the stochastic updates is bounded, but it's also a measure of how non-i.i.d. the datasets are. Is there an intuitive explanation of what such a bound means in terms of how the distributions of the clients vary?
-  While the resampling method is indeed relatively simple and easy to understand, I think that the paper will benefit from a discussion on why it actually helps. For example Remark 1 could be followed by some examples of situations when mixing the gradients in advance will help or alternatively some comparison to other fields where such resampling approaches were found useful. Similarly, it would be interesting to see a discussion of how much and in what respect does the proof of Krum change once dependence between the vectors is introduced. 
- For the experiments, it would be nice to see plots for different values of $s$, not only $s = 2$, so as to see if the method effectively trades-off convergence speed with robustness, as claimed in Remark 1.
- It will also be nice to get more information about the data splits between the clients, as well as experiments with multiple repeats and error bars and/or multiple amount of heterogeneity introduced, so that the significance of the improvements can be easier to evaluate.
  
##########################################################################

Minor points:

- In Algorithm 1 the inputs passed on to Algorithm 2 are different that the inputs received in Algorithm 2. It would be nice to make these consistent.
- In Proposition 1 it is assumed that the input is a set of gradients. However, in the second bullet point $f$ gradients are assumed to be Byzantine. It's a bit unclear what this means given that we are just talking about $n$ arbitrary vectors. I think I understand what is meant, but it will be nice to clarify.


##########################################################################

Review summary:

The paper shows that a simple, but effective resampling scheme can be used to transfer i.i.d. Byzantine-robust algorithms to a non-i.i.d. setup. The paper is generally well-written and provides some theoretical and experimental evidence to support the proposed method. Therefore, I recommend acceptance, together with a few suggestions for improving the discussion and the experimental section. 

review_title: A good attempt towards robust federated learning

Meta-review: This paper presents an algorithm for distributed optimization in that aims to be "Byzantine-robust", in the sense that it learns successfully when some of the workers send arbitrary messages.  The goal in this work is to remain robust when each worker samples data from a different distribution.

While reviewers found the work interesting, issues about the theoretical development arose during the discussion period, and it appears that the paper cannot be accepted in its current form.

The most serious issue was with Proposition I, which appears to be incorrect.  In its putative proof, the authors write that each gradient is sampled at most $s$ times.  This naturally leads to the conclusion that, in Algorithm 2, when the Break statement is reached,  $g_{j_i}$ is not used to compute $\bar{g}_t$.

Given this interpretation of Algorithm 2, it seems that Proposition I cannot be true. For example, if $s=1$, once $t \geq n/2$, fairly often, gradients will be sampled that had previously been sampled. In such cases, would be zero, so that, on average, $\bar{g}_t$ would be biased toward zero in later rounds.

Their putative proof of Proposition I refers to a whole chapter of a statistics text. We couldn't find anything in that chapter that implies what they claim about Algorithm 2 (or that treats a sampling scheme like Algorithm 2 at all).

Throughout the paper, when the authors took expectations, it was not always clear what was random and what was fixed.  After some discussion, disagreement remained about how to interpret some of the assumptions.  This was true in particular about the assumption in the first displayed equation on page two.  
Decision: Reject