Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a novel setting for vertical federated learning in which labels are distributed among clients, and proposes a novel fast and secure protocol for this setting based on XGBoost . The protocol enables secure aggregation of gradients and hessians for XGBoost via (a) a masking scheme based on Diffie-Hellman key exchange and a key derivation function and (b) global differential privacy. Security analysis presented in the paper demonstrate that label/feature privacy is persevered even if n-2 clients collude. Finally, the efficacy of the proposed protocol is demonstrated via experimental evaluations on multiple datasets.
main_review: ### Strengths

1. The writing and figures are clear. 

2. Thorough review of background material.

3. Theoretical and empirical analysis of computation and communication costs demonstrate that the proposed approach compares very favorably to MPC-based solutions. 

4. Thorough security analysis proves that the proposed approach is robust to collusion of up to n-2 clients. 

5. The proposed combination of Diffie-Hellman key exchange and global differential privacy is ingenious and the experimental results demonstrate the clear advantage of using this combination compared to local differential privacy at each client.

6. The proposed novel setting for vertical federated learning with decentralized labels is very well motivated as shown from the COVID19 example highlighted in the paper. 


### Weaknesses 

1. The proposed method performs poorly on small datasets.





summary_of_the_review: The paper introduces a novel setting for VFL with decentralized labels, which is very well motivated, and proposes novel protocol for this setting, which is ingenious and shows significant advantages compared to existing methods.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a secure protocol in the FL setting for XGBoost where the dataset is vertically split. The proposed mechanism is based on masking and selecting a random client to generate DP noise.
main_review: 1. There are several writing issues with the paper -
i) There should be a background section that introduces the crypto primitives briefly - the main body should be self-contained.
ii) Formal security theorems should be presented in the main paper - only full proofs should be in the Appendix.
iii) A copy-edit pass is required for the paper - some examples
"In practice, a VFL scheme supporting distributed labels
is of necessity." --> is necessary
"without disclosing both feature" --> without disclosing either ... or..
"where a single label is only associated with a client." - client is associated with a single label

2. There is a fundamental flaw in the security guarantee of the paper - the source client and the noise leader could collude, this would reveal the aggregation without noise (the noise can be subtracted out).
3. I could not understand the problem setting - the motivating examples are hospitals and banks. But would not every patient visit a particular hospital or a particular bank (based on locality etc), how is this different from horizontal data split?
4. I could understand why would the info that client A holds label a be made public (Sec 2.3)? Is not label privacy a goal of the scheme?
5. I was confused with the term label space $\mathcal{Y}=\{y_1,\cdots,y_m\}$ - it seems like the label set and not space (label space would be the space of classes like binary for covid test and so on). Also I am confused with the notation $X_j| j \in {1,\cdots, f\}$ since the number of features is $d$ (instead of $f$)?
6. Evaluation is inadequate - performance microbenchmarks such as break down of client/ noise leader and source client time, bandwidth analysis etc are missing.
summary_of_the_review: There are several writing issues in the paper. Additionally, the paper suffers from a security flaw.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies vertical federated learning for fast and secure XGBoost training where labels are distributed among multiple parties.  Most previous works focus on labels are centralized in one party and adapt cryptography such as homomorphic encryption, multi-party computation, and differential privacy to protect the data and label privacy. This paper instead assumes decentralized labels and combines existing secure aggregation and global differential privacy to safeguard the data and label privacy. 
main_review: Pros: 
1. The problem addressed in this paper is of practical importance for many real-world applications.
2. The challenges and the proposed solutions are well motivated.
3. The paper is also very well-written and has a nice flow.


Cons:
1. Several typos: for example:  “multiply hospitals” should be “multiple”.
2. The main contribution of the paper is to loose the assumption of centralized labels to decentralized labels. Adapting existing secure aggregation to outperform homomorphic encryption-based VFL on latency or differential privacy on accuracy is straightforward. As such, the paper has a limited novelty from the ML perspective.
3. The proposed method has shown improved performance over HE on the aspect of training time and DP on the aspect of accuracy. The paper, however, fails to compare with HE on the aspect of accuracy and DP HE on the aspect of latency. 

summary_of_the_review: The problem addressed in this paper is of practical importance for many real-world applications. Thus, I would like to see its presentation at the conference.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a new approach called FEVERLESS to conduct vertical federated learning over distributed labels. In the studied setting, the clients have different features of the same sample, and the labels are distributed over different clients. To get the gradients of the samples with missing labels, the clients utilize Diffie-Hellman key exchange, key derivation function, and differential privacy to send the masked gradients to the source client. Then, the source client computes the gain based on the gradients, and the split candidate with the maximum gain is selected as the split point. The authors prove that FEVERLESS protects label and data privacy against an adversary controlling at most n-2 clients. The experiments show that FEVERLESS can achieve comparable accuracy compared with XGBoost.
main_review: The paper provides a comprehensive security analysis of the proposed protocol. However, I have the following concerns.
1. The paper is not easy to read. The preliminary and many details about the algorithm are put into the appendix, which is not friendly to the readers.
2. The paper provides two examples (i.e., hospitals, bank branches) to demonstrate that the distributed label setting is common in practice. However, these two examples are not convincing. In these two examples, the training examples are usually distributed to the clients (e.g., customers are registered to distinct branches as mentioned in the paper), which is more like a horizontal federated learning setting.
3. In the proposed algorithm, the clients send the sum of the gradients $G$ to the source client. However, the source client needs to know $G_L$ and $G_R$ to compute the gain.  How does the client split the received $G$ into $G_L$ and $G_R$?
4. For a missing label of the source client, there may be multiple clients that hold the label. Then, the noises are injected into the gradients of the same sample. In this case, what is the overall privacy budget for the sample? Also, does the algorithm still work in such as case?
5. The datasets used in the experiments are small. The authors should better conduct experiments on a dataset with at least a million samples.
6. It is not clear to compare the exact performance of different approaches in Figure 2 and Figure 4. The authors can add a table to show the accuracy and time of different approaches with a default depth and number of trees.
7. In the computation cost, the time complexity of generated masks is O(xxx * n), while the overall complexity is O(xxx + n). Is it a typo?

summary_of_the_review: Overall, I think the paper can be significantly improved in writing. The paper does not convince me about the importance of the distributed label setting. Moreover, I do not fully understand how the algorithm work. Please refer to my main reviews.
review_title: null

Meta-review: The reviewers agree that the problem tackled is important but raise several substantial issues that justify not to accept the paper in its current form. I would encourage the authors to clarify further the crypto part of the paper (dHiP, 2., 4.) and work on how to relax or improve the model assumptions (NGrb). Also, the author's reply to chCc, point 2. becomes more disputable as federated learning is further developed. The argument can be refined.

On a personal note, the statement of Theorem 3.3 could be made clearer, in particular in simplifying (while weakening a bit) the probability bound.

AC.
Decision: Reject