Venue: ICLR 2021 Conference

Reviews:

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

The paper proposes a method combining privacy and byzantine-robustness for distnace-based aggregation.  This is a relevant and interesting topic.

The paper assumes that it is not a problem that one of the server learns all pairwise distances.  Still, every known pairwise distance |&x_i-x_j|| more tightly connects the relative position of the points x_i together.  If the dimension of the vectors x_i isn't large, then knowledge of a limited set of x_i vectors may allow this server to deduce all other vectors (or may allow him to determine significant constraints all other vectors x_j must satisfy).

Once we accept the above assumption, the paper seems mostly sound, sometimes with minor issues in writing or precision (a few examples below).
The approach doesn't introduce fundamentally new techniques but combines existing ideas to realize a more powerful solution.  The text is quite well written.


DETAILS

* "WorkerSecretSharing (Figure 1a): ... This can be done e.g. by sampling a large noise \xi_i and then using x_i \pm \xi_i as the shares." -> as x_i must be the sum of the shares, I guess you mean the shares are (x_i+\xi_i)/2 and (x_i-\xi_i)/2
* Section 3.2: RobustWeightSelection (Figure 1b): seleced subset -> selected subset
* Section 3.2: RobustWeightSelection (Figure 1b): "S2 secret shares with S1 the values of {<p_i>}" -> please make clear what exactly is "secret-shares", it is not the secret sharing used by workers to split x=x_1+x_2.   (I guess you describe here step 3b in algo 2)
* "Compatibility with local differential privacy. One byproduct of our protocol can be used to convert differentially private mechanisms, such as (Abadi et al., 2016) which only of the aggregate model which guarantees privacy," -> the last "which only ..." subphrase needs a verb



review_title: When all assumptions hold a nice method

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work proposes a method to robustly (<.5 adversarial workers) aggregate model updates using two non-colluding servers. The proposed method scales well with the number of workers and is compatible with local DP and different robust aggregation protocols. Especially the scalability is a big improvement compared to previous methods. The authors discuss related work that relies on public key infrastructure and requires pairwise secrets between clients. One big advantage of the proposed protocol is that there is no communication between the workers.

Positives
- The paper is very well written and easy to follow. 
- The contributions are significant in terms of scalability, compared to other protocols discussed in the literature review. 
- The theoretical justifications seem sound and are relatively easy to follow, although I didn't verify the proofs in detail.

Negatives
- The assumptions are still strong (non-colluding servers), but I am not very familiar with the literature to fully assess the implications. It would be great to put the strong assumption of non-colluding servers more into context. How does it compare to other protocols? (somewhat discussed in the lit section) 
- The experimental section is lacking a bit. It's not entirely clear what additional insights the provided analysis gives, especially also given the unrealistic setup of only five workers. It's not clear what the actual experiments are, referred to with S1 Avg, S2 Avg, S2 Krum (S1/S2 also refer to the servers in the rest of the paper). Is S2 Avg the proposed protocol, just w/o the robust computation? A more detailed discussion why the robust version increases the server communication significantly (even though the authors claim it doesn't. AFAICT it almost doubles the total cost) would be welcome. Is it because of the Beaver's triple communication to share the pairwise distances? (TBH, I am not sure this paper really needed an experimental section, but the current one has serious gaps).

While the paper proposes a novel idea with significant improvements, the paper is lacking wrt putting it into context of the existing field and a more detailed interpretation of the experiments would be welcome. For these reasons the recommendation is to reject the paper in it's current state.
review_title: Novel proposal of robust and secure federated learning

final_score: rating: 7: Good paper, accept
review_content: **Paper summary**

1. The paper introduces a two server protocol to handle privacy concerns and Byzantine threats in a Federated Learning system simultaneously.
2. In the protocol, each client secretly shares their model update with the two servers by splitting its model update such that neither server can know what the model update is without colluding with the other server. The servers are able to compute pairwise distances of all updates securely. These distances are used by byzantine robust aggregators to find a robust model update.


**Strengths**
1. The paper handles two very relevant and important issues with Federated Learning simultaneously - privacy and Byzantine resilience (which includes data poisoning attacks). 
2. The proposed algorithm is shown to have theoretical guarantees.
3. A wide array of byzantine robust aggregation rules can be incorporated easily into the framework.
5. There isn't much communication overhead between the workers and the server.
6. The two server protocol does not seem to be too difficult to implement in practice. The algorithm requires that the two servers should not collude. This requirement does not seem too difficult to be enforced onto big companies that will use FL.
7. In the absence of Byzantine machines, the non-robust protocol seems to be compatible with differential privacy.

**Concerns**
1. Can it be quantified (using some information theoretic bound) that only pairwise distances cannot leak much information? In the worst case, it can leak some information. For example if the pairwise distance is 0 for some pair, then each machine exactly knows the other's model update. However, I believe that using some assumption on distribution of model updates, we can still get some information theoretic guarantee. The three server algorithm in Appendix D seems to address this, but I wonder if we can say something for the two server algorithm too.
2. Can it be extended to dimension-independent robust mean estimation techniques? The paper only considers distance based aggregators (with the exception of  (Alistarh et al., 2018), which I discuss later). These aggregators all seem to suffer from an error that grows with dimensions as $\sqrt{d}$ (see section 2 in (Wang et al., 2020). A recent line of works has given robust mean estimators that have errors that are dimension independent (Dong et al., 2019; Diakonikolas et al., 2017; Diakonikolas et al., 2016; Lai et al., 2016). However these use second order information like the empirical covariance matrix too. Can the algorithm proposed in this paper be extended to these algorithms too? 

Alistarh et al. (2018) also give dimension independent guarantees, but they require the workers to sample a new data point at every iteration, which may not hold for many FL systems.

**Score justification**

The paper tackles a very relevant problem for Federated Learning. Further, the proposed algorithm has nice theoretical guarantees and it looks like the algorithm can be easily implemented in a variety of large FL systems.


**References**

Wang, L., Pang, Q., Wang, S. and Song, D., 2020. F2ED-Learning: Good Fences Make Good Neighbors. arXiv preprint arXiv:2010.01175.

Dong, Y., Hopkins, S. and Li, J., 2019. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. In Advances in Neural Information Processing Systems (pp. 6067-6077).

Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A. and Stewart, A., 2017. Being robust (in high dimensions) can be practical. arXiv preprint arXiv:1703.00893.

Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A. and Stewart, A., 2016, October. Robust Estimators in High Dimensions without the Computational Intractability. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 655-664).

Lai, K.A., Rao, A.B. and Vempala, S., 2016, October. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 665-674). IEEE.
review_title: A good paper that tackles both privacy and adversarial machines

final_score: rating: 3: Clear rejection
review_content: Summary:
The paper presents a system for collaborative training where two central servers compute the model update using two-party computation. There are two variants, one where the update are not checked, and one where the server use algorithm (Aggr) to weight the updates such that outliers are excluded.

Pros:
The basic ideas are presented succinctly, and the overall setup solves a relevant problem.

Cons:
- The main issue I have is that the authors claim in Section 4.3 that they "can" use full-precision (real) values in the computation but the underlying techniques (secret sharing and Beaver triples) have only been proposed for integer/quantized values. In particular, if the actual value is small, adding a large random value will override it due to rounding in floating-point representation. I cannot find any treatment of this issue or any reference to works to have tackled floating-point secure computation such as Aliasgari et al., NDSS '13.
- Similarly, the claim that the paper does not rely on cryptographic primitives seems exaggerated given the use of secret sharing and Beaver triples.
- The cost of generating Beaver triples is ignored. The paper does not estimate how many are needed.
- Claiming Byzantine robustness seems too strong when the two central servers have to be semi-honest.

Conclusion:
I recommend rejection because of the irrealistic approach regarding real-valued computation. The authors should either present credible secure floating-point computation or change their claim to quantized computation.

Minor issues:
3.1: x_i +- \xi_i is not an additive secret sharing of x_i but 2*x_i.
3.1: sum of (the) other share
3.1: "sum of other share" should be \sum *p_i* x_i^(2)?
3.1: It is not surprising that S2 does not learn anything in secure computation.
3.3: In particular, (unfinished sentence)
3.3: don't face
4.2: vetor (twice)
6: median and trimmed-mean -based (odd positioning of dash)

review_title: Failed assumptions regarding secure computation

Meta-review: This paper presents a secure aggregation method to ensure byzantine robustness. The reviewers thought that the idea was interesting, but had the following concerns.
* Relaxing the assumptions used in the theoretical analysis as much as possible
* Run more extensive experiments
I encourage the authors to their feedback into account when preparing the revised draft. 


Decision: Reject