# Secure and Efficient Federated Gradient Boosting Decision Trees
## 4 Secure and Efficient FL for GBDTs
### The Algorithm Description of SeFB  
1. Input LSH functions \(\{F_{k}\}_{k=1,2,\ldots,L}\), instance set for each participant \(I_{p}\), number of updates \(U\) and data set for each participant \(X_{p}\),
2. Data participants calculate the hash values of the local instances according to LSH functions, and upload them to coordinator GS.
3. GS constructs a global hash table according to the hash values and broadcasts it. At the same time, GS sends a request to participants to obtain the cumulative gradients of their local similar instances.
4. Data participants construct a matrix of similar instances \(s=S_{pq}^{i}\) according to the global hash table, and calculate the cumulative gradients \(\,G_{pq}^{i}\gets G_{pq}^{i}+S_{q}^{i}\), \(H_{pq}^{i}\gets G_{pq}^{i}+h_{q}^{i}\) of local similar instances according to the global hash table and upload them to GS.
5. GS counts the similar instance information of each participant, and selects the participant with the largest number of similar instances in turn as the builder B (the active party) of each update iteration.
6. GS calculates the weighted gradients \(G_{pq}^{i}\), \(H_{pq}^{i}\) of the B according to the similar information between each instance \(X_{q}^{b}\) in the \(I_{b}\) and \(I_{p}\).
7. GS sends datagram (weighted gradients and tree-building mark) to B.
8. [PERSON] uses the previous tree \(t_{j-1}\), data set \(X_{b}\) and weighted gradients \(G_{pq}^{i}\), \(H_{pq}^{i}\) rewrites the loss function according to Formula (8) and constructs the tree \(t_{j}\) according to Formula (4), and sends \(t_{j}\) to other participants.
9. Participants calculate the sum of gradients corresponding to each leaf according to \(t_{j}\) and data set \(X_{p}\) to obtain \(G_{p}\) and \(H_{p}\), and upload them to GS.
10. GS aggregates \(G_{p}\) and \(H_{p}\) of each participant to obtain \(G=\sum_{p\in P}\frac{n_{p}}{n}G_{p}\) and \(H=\sum_{p\in P}\frac{n_{p}}{n}H_{p}\), and calculates the global leaf weights \(\omega_{i}=-\frac{G}{H+\lambda}\) with \(G\) and \(H\), and then returns them to the participants.
11. Participants obtain the leaf weights \(\omega\), they combine the tree \(t_{j}\) with \(\omega\) and to obtain \(T_{j}\).
12. Repeat step5-step11, and output a decision tree in each cycle until the update iteration ends (\(j>U\)).
13. Output global model \(\{T_{1},\ldots,T_{U}\}\)  
In step 2, for each instance, the purpose of using LSH is to obtain similar instance IDs. In order to obtain the similar information between any two instances in the federated data without exposing the original data, the \(p\)-stable LSH function is adopted.  
In step 5, GS selects the participant with the largest number of similar instances as the builder after obtaining the cumulative gradients of local similar instances of each participant. In other words, the builder at this time is the participant with the best data quality and distribution.  
In step 6, the builder changes the local loss function through the weighted gradients. The weighted gradients at this time fully absorb the gradient information of all participants, which can ensure that the constructed model has better generalization.  
In step 7, GS can measure the importance of a participant's gradient to updating the tree model through \(\frac{n_{p}}{n}(n=\sum_{p=1}^{U}n_{p})\), improve the contribution of high-quality data sets, and thus speed up the convergence of the model.