Venue: ICLR 2021 Conference

Reviews:

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

The paper claims to be the first paper that simultaneously handles Byzantine threats while ensuring privacy in a federated learning setup. One of their main claims is that this is the first algorithm that provides dimension independent robustness guarantees against byzantine threats (I have some concerns regarding this claim). The algorithm first divides all the machines into shards. Within each shard there is secure aggregation. Finally, the outputs of each shard is robustly aggregated such that the error isn't dimension dependent.

**Strengths**
1. The problem of handling privacy and tolerance to Byzantine adversaries (including data poisoning adversaries) is indeed very important and relevant to federated learning. 
2. The paper provides dimension independent guarantees against Byzantine adversaries, which is of critical importance since modern models can have huge dimensionality.
3. The experiments show that the algorithm is better than other Byzantine resilient algorithms.

I like the clarification about the assumptions of Bulyan done in Section 2. This will make comparisons between related works easier.

**Concerns**
1. The proof of Theorem 2 seems to be missing.
2. I can see that Theorem 3 might be a direct corollary of Proposition 4.1 from (Steinhardt, 2018), but it would still be good to prove Theorem 3 for completeness.
3. I am not able to see how sharding helps non-iid data become iid. Corollary 1 (CLT) says that $\frac{1}{s_n}\sum_{i=1}^n (X_i - \mu_i) \stackrel{d}{\to} \mathcal{N}(0,1) $. However, what is needed for sharding to make data become iid would be something like $\frac{1}{n}\sum_{i=1}^n X_i \stackrel{d}{\to} \mathcal{N}(0,1)$. Note that there are two differences: The major difference is that we have $X_i$ instead of $X_i-\mu_i$. The second difference is we have $n$ in the denominator instead of $s_n$. Below, I give a concrete example how the CLT is not applicable for sharding.

Assume that we have $2n$ machines. We divided them into two shards of $n$ machines each (machines $1$ to $n$ go into shard $1$, and machines $n+1$ to $2n$ go into shard $2$). Now, what the paper claims would be that the mean of the two shards should converge to the same distribution, regardless of the distribution of the individual machine gradients. Now, assume that for some particular iteration, the gradient of the machines have the following distribution: Machines $1$ to $n$ have (iid) gradients equal to $1$ with probability $1$. Machines $n+1$ to $2n$ have (iid) gradients equal to $-1$ with probability $1$. Clearly, the mean of the first shard is the constant random variable $1$, whereas the mean of the second shard is the constant random variable $-1$. These two random variables don't have the same distribution. Thus, the distribution of the means of the shards is not identical and hence not iid.

4. If concern 3 is valid, then the algorithm would not work on heterogenous data. Further even if concern 3 is invalid the CLT only gives asymptotic result. A key point of this paper is dimension independent resilience. However, if the convergence given by the CLT is very slow as the dimensions increase, then the dimension independent resilience may no longer be valid. 

For these reasons, I think the paper needs some more justification for its theoretical claims.


**Suggestions**

I think there are some papers that use the dimension-independent robust mean estimation techniques for non-FL learning. For example (Yin et al., 2019) (this is different from the one cited in your paper). Also, Alistarh et al.(2018) give dimension independent guarantees. It would be good to talk about these in related works.

**Score justification**

As mentioned in the Concerns section, I think the paper might be missing some justifications for its theoretical claims.

**Post Author Feedback Comments**

The authors have tried to address my main concern by adding an assumption on the distributions of gradients. Essentially they have assumed that the gradient distributions are sampled from a small, finite set of distributions. I don't know how realistic this assumption is, because each client can potentially have a different distribution. However, in practice, this may be approximately true. A better assumption would have been based on probability distances (TV distance, Wasserstein distance, etc.). 

I have increased my score to 6.

**References**


Yin, D., Chen, Y., Kannan, R. and Bartlett, P., 2019, May. Defending against saddle point attack in Byzantine-robust distributed learning. In International Conference on Machine Learning (pp. 7074-7084). PMLR.
Alistarh, D., Allen-Zhu, Z. and Li, J., 2018. Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems (pp. 4613-4623).
review_title: Nice algorithm but missing some justifications

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: The authors consider federated learning setting and how to defend the overall learning task against malicious clients and a semi-honest centralized server. Though there are known ways to prevent attacks, they suffer from a large error in the estimator and also do not preserve privacy of updates since the server sees them in the clear in order to adjust for error. This paper proposes a sharding technique and use of the estimator method whose error does not depend on the number of dimensions as previous work.

Novelty:
1. the sharding approach allows the proposed method to use masking-like techniques to avoid the server seeing values of individual clients. That is, the server only sees aggregates in the shard
2. the paper proposes a different tradeoff in terms of the error of the estimate compared to mechanisms in related work. In particular, the error depends on the proportion of “malicious” clients.

Overall it is a very nicely written and presented paper.
I would suggest that the authors expand evaluation section to compare performance of the methods besides accuracy. That is how many rounds each algorithm takes, total communication cost and computation time of each approach.

Also I was not clear if one needs to make assumptions on the knowledge of the proportion of malicious clients in order to carry out the algorithm (Alg 2). Would that be known or there would be a known upper bound?

Please state if there is an assumption on non collusion between the server and the clients.
review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################

Paper summary:

The paper considers robustness to poisoning and backdoor attacks in the context of federated learning. It proposes a defence based  on splitting the clients into shards, averaging their updates via secure aggregation and then using a robust mean estimation on top to ensure robustness. The authors point out that controlling the number of shards is a way to trade-off privacy vs robustness, thus potentially dealing with both malicious clients and an honest, but curious server. The paper provides some theoretical justification for the algorithm, as well as an experimental evaluation where its performance is tested against multiple attacks and compared to other existing methods.

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

Pros:

- The paper studies an important problem. Federated learning is an increasingly popular way of training large-scale models. However, the privacy that it offers comes with the cost of vulnerability to training time attacks. Hence, the problem of guaranteeing robustness while preserving privacy is certainly important.
- I find the idea of splitting clients into groups to trade-off privacy vs robustness very interesting. To my awareness the idea is novel in the context of robust federated learning.
- Overall, the paper is well-written and it tries to justify the proposed method both theoretically and empirically. 


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

Cons:

1. While the papers aims to address the problem of robust federated learning, most of its theoretical analysis, as well as the optimization procedure that is described, is actually tailored to a classic (i.i.d.) distributed learning setting.

- The analysis is Section 4.1 and 4.2 assumes that the data of the good clients is i.i.d.. In section 4.3 an informal argument is made as to why this can be safely ignored because of the averaging inside the shards. However, I find the argument unconvincing for two reasons. First, the CLT argument is tailored to scalar random variables. Applying it to each dimension independently does not seem trivial to me and, if at all possible, might involve an unfortunate dependence in the dimension of the problem. Secondly, even on the intuitive level the resulting distributions will be close to identical only when all clients are good. If some of them can behave arbitrarily, they can shift the mean of their shard, thus breaking the i.i.d. property.

- Perhaps a smaller issue is that the plain optimization method considered in the paper (which is modified via the robust aggregation procedure later on) is SGD. In contrast, many federated learning algorithms, for example, FED-AVG, are based on averaging model parameters and in addition train a model for every client individually. It is unclear whether the analysis in this paper would transfer there as well.

- The baselines considered in the experimental section are also taken from papers that study the i.i.d. version of the problem. Since little information is given about how the training data is distributed across clients, it's hard to know if the comparison to the i.i.d. baselines is fair and also if the experimental setup corresponds to i.i.d. or non-i.i.d. data.

2. Overall, the theoretical analysis in the paper appears insufficient and is not backed up by any proofs.

- Some of the presented theorems and corollaries seem to come from prior work, while others seem to be novel. I am assuming that Theorem 1 is from Steinhardt (2018), while Theorem 2 and 3 are novel. I think this should be made more clear. 
- Theorem 2 and 3 are just stated without any proof. I was also unable to find proofs in the supplementary material. This, together with the lack of intuitive explanation about why these results should hold, makes it impossible to judge the validity and novelty of these results.
- Theorem 3 states that for small enough number of Byzantine workers, a dimension independent error can be obtained. To me this sounds rather vague. Does this mean that the mean of the true gradients can be estimated to a dimension-independent accuracy at each time step? Or does it mean that at the end the algorithm converges to an epsilon-stationary point, with a number of steps that features no dependence on the dimension of the problem? How would this compare to results in previous work on Byzantine robustness?

3. While experiments are provided on two datasets and against a large amount of attacks, some of the comparisons seem unfair to me. 

- In particular, all attacks apart from the backdoor one are tailored against some of the baselines. Naturally, the corresponding baselines compare badly against the attacks tailored to them. At the same time, Krum performs quite well against trimmed mean attacks and similarly the trimmed mean works well against the Krum attack. It therefore would be more fair to also create an attack specifically towards the algorithm proposed in the paper and check the performance under this attack. Alternatively, defence-independent attacks can be used. 
- It would be nice to include more details about how the data was split among workers, so that i.i.d. and non-i.i.d. situations can be spaced out.
- In the first set of experiments, what is the value of p? It would be interesting to see how the proposed algorithm performs for various values of p, both in terms of robustness and in terms of some notion of privacy.

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

Review summary:

I find the high-level idea and the approach taken in the paper quite interesting. However, due to a few concerns about the theoretical justification and the experimental setup I do not recommend acceptance. I believe that a more detailed theoretical analysis and a wider set of experiments are needed to strengthen the submission and make it easier to compare it to prior work.
review_title: Interesting idea, some concerns about the theory and experimental setup

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes a simple protocol to allow for both robust mean estimation and secure aggregation by sharding users, applying secure aggregation between shards and then doing robust mean estimation on the means returned by each shard.

Pros:

The proposed method is simple.

Experiments suggest the proposed method is more robust to various attacks than competitors.

Cons:

Generally the paper requires further editing as there are several places where the descriptions could be more clear (e.g. "achieves
optimal or sub-optimal performance").

In all Theorems it should be noted whether this result is by the authors or whether it is from Steinhardt (2018). Any Theorems which are quoted should be fully attributed, and any which are novel should be accompanied by formal proofs.

It is quite unclear what value the discussion of creating IID shards brings. Non-IID data between clients is a concern in federated learning, and it can cause issues such as diverging model parameters when each client takes multiple steps of GD locally. However this issue is not solved by sharding the users (as any averaging takes place after all local updates are made), nor is it clear if this solves any other issues. The authors should identify what value having these IID shards brings. Additionally it is unclear that the Lindeberg CLT is required here, as the shards draw directly from the mixture distribution induced by the clients $D_i$ distributions. 

The paper would benefit from a much stronger explanation of the value of the IID-ness of the shards and more exploration of the value added by sharding.
review_title: A protocol for protecting both clients and the server

Meta-review: The paper considers federated learning in the presence of malicious clients and a semi-honest centralized server. The authors provide a novel secure aggregation technique (i.e. split the clients into shards, and securely aggregate each shard’s updates, and the estimating things based on the updates from different shards) to protect clients from the server. Furthermore, an important property of the proposed protocol is that the estimation error is (provably) dimension-free against Byzantine malicious clients. The paper is well-written. 

The reviewers had a number of concerns many of which were addressed during the rebuttal phase. There was also another round of discussion after the rebuttal phase. Overall, the reviewers felt that there are still some issues that need to be resolved (see the updated reviews--the main issues are: (i) the assumption of non-collusion between the server and the clients, (ii) assumptions and analysis of the non-iid case, and (iii)  comparing to attacks that are specifically targeted against the baselines). I believe that once these issues are addressed, the paper will provide an important contribution to the area of federated learning. 


Decision: Reject