Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers federated learning with two non-colluding honest-but-curious servers and honest-but-curious clients, where a subset of clients can be faulty. It proposes a protocol to securely compute approximate median. The main idea is to use secure median algorithm from [Tueno et al. 2019] along with a bucketing trick proposed in [Corrigan-Gibbs and Boneh 2017] to reduce complexity. The paper gives convergence analysis for bucketed median under some strict assumptions.
main_review: The problem of achieving security as well as Byzantine robustness in federated learning is challenging, and there are only a few papers on this topic. In this sense, the paper is timely and relevant. However, the threat model considered in the paper is non-standard (and also a bit confusing). Furthermore, the novelty seems to be limited as the paper mainly combines two ideas from the literature: bucketing (from [Corrigan-Gibbs and Boneh 2017]) and secure median ([Tueno et al. 2019]). The detailed comments are as follows:

Major comments:

1. In the majority of papers that consider robust federated/distributed learning, it is assumed that Byzantine/adversarial clients can arbitrarily deviate from the protocol. The paper mentions in the abstract about adversarial updates, but also assumes that all clients honestly follow the protocol. This is somewhat non-standard threat model. Is it assumed that errors occur due to external factors such as hardware faults etc? If this is the case, then errors may occur while computing secret shares of the model as well. It is assumed that secret shares are computed perfectly, which does not seem practical. Also, first mentioning adversarial updates and then mentioning semi-honest clients can be a bit confusing. It would be important to add a discussion on this model, and explicitly mention how this differs from Byzantine or malicious setup considered in prior works.

2. The title of the paper says scalable robust federated learning, however experiments are performed with just 3 clients. This seems to be a bit too limited. Since MPC primitives will mainly be used between the two servers and clients simply secret share their updates, it is not clear why not to scale the protocol to a larger number of clients in the experiments. At the very least, can the authors comment on how would the bucketed median perform (without security constraints) for a larger number of clients, when a constant fraction of clients can be faulty?

3. Assumption 2 seems to require that each client has a very large dataset, and computes gradient descent on the entire dataset. Can the authors elaborate on this? This seems to limit the practicality. How the assumptions in the paper differ from typical assumptions, say those in [Yin et al. 2018]?

Taking this point further, the paper says (before Theorem 6.1) that [Yin et al. 2018] requires \alpha to be "smaller than an easily negative value". Can the authors give more details on what this means? Further, the authors say that they prove the robustness in a new way.  It will be helpful to elaborate what new techniques are used, and how they differ from [Yin et al. 2018].

4. In Algorithm 1, it is not at all clear how F^l_{Comp}(<\sum_{i}e_i>_j, n/2) can compute the median on buckets. Specifically, why does  the comparison algorithm take sum of shares as input? In general, it is a bit unclear how the frequency distribution of client updates is computed, or even how it is defined. It is important to give sufficient details here.

5. In Experimental Results, it would be important to give more details about the models considered. For instance, in the CNN for CIFAR-10, how many convolutional layers, what pooling etc.

Other comments:

1. The authors mention that best known approaches for median aggregation with MPC are slow, having quadratic computation cost (in terms of the number of clients). There are no citations given. Can the authors provide some references to support this claim?

2. The paper cites [Konecny et a. 2017] for MPC in federated learning at two instances in the first paragraph. This is incorrect as [Konecny et a. 2017] deals with reducing communication costs, and does not consider MPC.

3. Can the proposed protocol handle client dropouts? It would be helpful to mention this explicitly.

4. Secure comparison is a significantly complex computation. The complexity of the proposed algorithm is characterized in terms of number of calls to secure comparison. It would be helpful to elaborate on the complexity of secure comparison to give a fair idea to readers (who are less aware of MPC primitives).

5. The paper claims in the title that the proposed algorithm has provable security guarantees, but spends only a paragraph in the main paper about the security analysis. It would be helpful to add more details, as security considerations are important for the problem setup. 

6. For label flipping, computing mean seems to perform better than computing median. It would be helpful to add a comment on why this is the case.
summary_of_the_review: The novelty seems to be fairly limited as the paper mainly combines two known ideas: bucketing and secure median. The threat model is somewhat non-standard, and experiments are conducted on only 3 clients.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a fast, secure, private and scalable approximate median aggregation approach for federated learning with two semi-honest non-colluding servers. The convergence analysis of the proposed approach for the IID case has been also provided under certain assumptions, which shows that the proposed approach converges with high probability if less than 1/2 of the clients are malicious. Finally, the experiments show that the proposed approach achieves similar robustness performance compared to the exact median based approach. 
main_review: The paper considers the two-server federated learning setting and proposes an interesting and simple approach for tolerating malicious users. The protocol is efficient as its complexity grows only linearly in the number of the users, whereas it grows quadratically in prior works.  The approximation is based on bucketing, which divides each dimension of the model into buckets and sends a unit vector that has a 1 in the bucket containing the client’s update and the median is approximated as the middle value of the range of this bucket. My main concern is that the paper does not consider some closely related works. Hence, it is not clear if the proposed approach is better. Below, I provide my detailed comments.

1- It is not clear for me how the proposed approach of this paper compares to other related works that are not mentioned as [1, 2]. The authors should make sure to include all relevant works along with comparisons that show the effectiveness of the proposed approach compared to these works. 

2- Typo in Page 2: "showe" -> show

3- Page 4: I find the static corruption model in Section 4.1 to be unrealistic as it assumes that the adversary chooses the parties to corrupt at the beginning of the protocol and cannot change them. In general, the corrupted parties may change dynamically while the protocol is running.  

4- Page 6: The convergence analysis only considers the IID case, how about the non-IID case?

5-  The following sentence should be illustrated more perhaps by providing numerical examples.  
"Note that the previous analysis on dimension-wise median in the FL setting (Yin et al., 2018) requires α to be smaller than an easily negative value"

6- The number of users considered in the experiments is too small to claim scalability. More experiments with large number of users need to be performed to show the effectiveness of the proposed approach in large-scale systems. 

7- Fig. 5 shows large gap between the proposed approach and the median approach, why this is the case?

References 

[1] Y. Khazbak et al. "MLGuard: Mitigating Poisoning Attacks in Privacy Preserving Distributed Collaborative Learning." , IEEE ICCCN, 2020.

[2] H. Fereidooni, et al. "SAFELearn: secure aggregation for private federated learning." 2021 IEEE Security and Privacy Workshops (SPW).
summary_of_the_review: The paper proposes an interesting approach approach for tolerating malicious users in FL, but it does not consider some prior works. Hence, I recommend revising the paper to include all relevant works and adding the comparisons. 

-- Post Rebuttal  --

I still do not see how the proposed approach in this paper compares to the related works I mentioned. While [1] does not provide server side running times, you should still evaluate their protocol and compare with your work. The responses to the non-IID issue and the scalability issue that I raised are not satisfying neither. Hence, I am keeping my score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to build privacy-preserving and robust federated learning systems. The proposed method includes two key ideas. The first idea is to propose an approximate, crypto-friendly median aggregation rule, which aims to achieve robustness. The second idea is to use cryto methods to implement this aggregation rule. Experiments were conducted to show that the proposed method is more efficient than cryto-based standard median implementation.  
main_review: Strengths

1. The topic is interesting. Achieving privacy and robustness is an important goal for federated learning. 

2. An approximate median aggregation rule is proposed. The proposed approximate median is crypto-friendly.

3. Some theoretical analysis about the approximate median is proposed. 

Weaknesses

1. The proposed crypto method assumes two non-colluding servers. This assumption may be unrealistic. 

2. The compared baseline seems too simple. Basically pairwise comparison is adopted as a baseline for implementing the standard median. How about median of median? We can divide the clients into groups, calculate median in each group, and then take median of median. This is another approximate method and is more efficient.

3. The evaluated Byzantine failures are too simple. Basically,  bit flips failure, label flip failure, and Gaussian noise failure are considered. I suggest the authors to consider more advanced attacks, e.g., the following:

a. A Little Is Enough: Circumventing Defenses For Distributed Learning. In NeurIPS, 2019.

b. Local Model Poisoning Attacks to Byzantine-Robust Federated Learning. In Usenix Security Symposium, 2020. 

If my comments, especially 2 and 3 are addressed, I'm happy to increase my rating score.  Overall, I think this is a promising direction. We can pick a robust federated learning method and then use cryptography to make it privacy preserving. However, we need to pick a really robust federated learning method. The paper picks Median, which shows some robustness but is not really robust. I think picking a method with provable robustness guarantee would make the paper stronger, e.g., the following:

c. Provably Secure Federated Learning against Malicious Clients. In AAAI, 2021.

d. CRFL: Certifiably Robust Federated Learning against Backdoor Attacks. In ICML, 2021.


summary_of_the_review: The paper studies privacy-preserving and robust federated learning. I think the paper would be stronger if my comments are addressed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: 
The paper proposes to use the median of model updates instead of the average of model updates in federated learning, and proposes an algorithm to perform the computation in a secret-sharing fashion by two independent servers.

main_review: 

The paper is understandable but contains quite a few language mistakes and suboptimal formulations.

The technical details (often in appendix) contain quite a few mistakes, it is unclear whether it is possible to fix them all while sticking to the current results.

For example, the robustness theorem (6.1) looks suspicious to me.  As it is formulated, there is no specification of how the adversarial vectors are generated.  There may exist schemes to generate these adversarial vectors which are compatible with the theorem formulation but cause a deviation in the median much larger than what the theorem promises.



A few details:

* Sec 4.2: In order to send their updates to the servers, clients additively secret-share their updates and sends one share to each server. -> send (plural)

* Algorithm 2, part 2, step 2. (d) : where is b defined ?  Or do you mean j instead of b ?

* In algorithm 1, 'b' is the number of buckets (a different meaning than the symbol 'b' in algorithm 2, it is preferable to avoid the same symbol having different meanings at different places).

* In Section 5, "instead of sending actual updates to the server, each client will send a unit vector that has a 1 in the bucket containing the client’s update, a": it therefore seems that as soon as the actual update has fewer bits than the number of buckets the original non-bucketed version may be cheaper from a communication point of view?

* Section 6.1: "Data individual loss function is denoted" -> an article is missing
* "if ratio of adversarial clients is" -> an article is missing for "ratio"

* We provide similar result -> a similar result

* Equation (3): I would have expected \|Med(\{\nabla {\hat F}_i(w) \}_{i=1}^{n_1} \cup \{v_i\}_{i_1}^{n_2}) - \nabla F(w) \|_\infty = \|Med(\{\nabla {\hat F}_i(w) - \nabla F(w) \}_{i=1}^{n_1} \cup \{v_i - \nabla F(w) \}_{i_1}^{n_2}) \|_\infty, but in Eq (3) in the paper the rightmost term of the righthandside of the equation doesn't have "- \nabla F(w)".

* Equation (4), please define (or remind the definition of) a_i.


summary_of_the_review: 
While the topic is interesting and the paper may have a valuable contribution, I don't succeed to verify the proofs of its theorems, and the way in which the theorems are stated lets me believe it is possible they are not correct.
review_title: null

Meta-review: There were concerns that the paper has a fairly limited novelty, being based on the combination of two known ideas: bucketing and 2-party secure median for distributed learning. Also, the scale of experiments is quite limited. Other issues include the lack of comparison to relevant related work, some doubts on correctness, and issues with independence and scalability that weren't fully resolved. Overall the reviewers felt that the paper shoud not be accepted in its current form.
Decision: Reject