# Secure and Efficient Federated Gradient Boosting Decision Trees
## 3 Preliminaries
### Federated Learning for GBDTs
#### 3.2.2 Horizontal Federated Learning for GBDTs  
Although GBDTs is applied to federated learning, the data distribution of weak learners leads to differences in their corresponding training processes. As the data distribution is horizontal, the horizontal federated learning for GBDTs is proposed, and its centralized training process is shown in Figure 2.  
Next, we briefly introduce the GBDTs training algorithm for federated learning. Formally, given a loss function \(l\) and a dataset with \(n\) instances and \(d\) features: \(D=\{(\mathsf{x}_{i},y_{i})\}(|D|=n,x_{i}\in R^{d},y_{i}\in R)\), GBDTs minimizes the following objective functions [22]:  
\[\widetilde{L}=\sum_{i}l(\hat{y}_{i},y_{i})+\sum_{k}\Omega(f_{k}) \tag{3}\]  
Figure 1: An example of GBDTs.  
Figure 2: Horizontal federated learning for GBDTs.  
where, \(L\) is the loss function, \(y_{i}\) represents the \(i\)th target value, \(\hat{y}_{i}\) represents the predicted value of the previous tree, \(\Omega(f)\) represents the penalty term of tree complexity, \(T_{1}\) represents the number of leaves and \(\omega\) represents the weight of leaves. Each \(f_{k}\) corresponds to a decision tree. By training the model additively, GBDTs minimizes the following objective function at the \(t\)th iteration:  
\[\widetilde{L}^{(t)}=\sum\limits_{i=1}^{N}\biggl{[}g_{i}f_{t}(x_{i})+\frac{h_{ i}f_{t}^{2}(x_{i})}{2}\biggr{]}+\Omega(f_{t}) \tag{4}\]  
where, \(g_{i}=\partial_{g^{(t-1)}}l\left(y_{i},\vartheta^{(t-1)}\right)\) and \(h_{i}=\partial_{g^{(t-1)}}^{2}l\left(y_{i},\vartheta^{(t-1)}\right)\) are the first-order and second-order gradient statistics of the loss function. Let \(I=I_{L}\cup I_{R}\), where \(I\) represents the instance set of the parent node. \(I_{L}\) and \(I_{R}\) represent the instance set of the left child node and the right child node after splitting the parent node, respectively. The gain value of each split is expressed as:  
\[L_{split}=\frac{1}{2}\biggl{[}\frac{\left(\sum\limits_{i\in I_{L}}g_{i} \right)^{2}}{\sum\limits_{i\in I_{L}}h_{i}+\lambda}+\frac{\left(\sum\limits_ {i\in I_{R}}g_{i}\right)^{2}}{\sum\limits_{i\in I_{R}}h_{i}+\lambda}-\frac{ \left(\sum\limits_{i\in I}g_{i}\right)^{2}}{\sum\limits_{i\in I_{R}}h_{i}+ \lambda}\biggr{]}-\gamma \tag{5}\]  
Since the loss function is quadratic, the leaf weight \(\hat{w}_{j}\) and the splitting score of a node can be expressed as follows.  
\[\hat{\omega}_{j}=-\frac{\sum\limits_{i\in I_{j}}g_{i}}{\sum\limits_{i\in I_{ j}}h_{i}+\lambda} \tag{6}\]  
\[score=\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{G ^{2}}{H+\lambda} \tag{7}\]  
where \(G_{L}\) and \(G_{R}\) (or \(H_{L}\) and \(H_{R}\)) represent the sum of the data \(g\) (or \(h\)) after splitting the left and right nodes, respectively.  
The literature [22] shows that gradient can represent the importance of an instance. For an instance \(X_{q}^{b}\in I_{b}\), let \(W_{hq}^{p}=\left\{k\middle|S_{hq}^{p}=q\right\}\),which contains the IDs of the instances in \(I_{p}\) that are similar with \(X_{q}^{b}\). Let \(g_{q}^{b}\) and \(h_{q}^{b}\) denote the first order and second order gradients of loss function at \(X_{q}^{b}\), respectively. When the builder B is building a new tree at the t-th iteration, WGB minimizes the following objective function [36].  
\[L_{w}^{(t)}=\sum\limits_{x_{q}^{b}\in I_{b}}\left[G_{hq}f_{t}(X_{q}^{b})+\frac {1}{2}H_{hq}f_{t}^{2}(X_{q}^{b})\right]+\Omega(f_{t}) \tag{8}\]  
where \(G_{hq}=\sum\limits_{p}\sum\limits_{i\in W_{hq}^{p}}g_{i}^{p},H_{hq}=\sum \limits_{p}\sum\limits_{i\in W_{hq}^{p}}h_{i}^{p}\)  
Compared with the objective in Equation (4), Equation (8) only uses the instances of \(I_{b}\).