Vertical federated learning based on DFP and BFGS

In vertical federated learning, [14] realizes classic logistic regression method. Let $X\in R^{N\times T}$ be a data set containing $T$ data samples, and each instance has $N$ features. Corresponding data label is $y\in\{-1,+1\}^{T}$. Suppose there are two honest but curious participants party A(host) and party B(guest). A has only the characteristics of the data. And B has not only the characteristics, but also the label of the data. So $X^{A}\in R^{N_{A}\times T}$ is owned by A and $X^{B}\in R^{N_{B}\times T}$ is owned by B. Each party has different data characteristics, but the sample id is the same. Therefore, the goal of optimization is to train classification model to solve

where $\boldsymbol{w}$ is the model parameters. So $\boldsymbol{w}=(\boldsymbol{w}^{A},\boldsymbol{w}^{B})$ where $\boldsymbol{w}^{A}\in R^{N_{A}}$ and $\boldsymbol{w}^{B}\in R^{N_{B}}$. Moreover $\boldsymbol{x}_{i}$ represents the feature of the i-th data instance and $y_{i}$ is the corresponding label. The loss function is negative log-likelihood

In [14], they use SGD to decrease gradient by exchanging encrypted middle information at each iteration. Party A and Party B hold vertically encrypted gradients $\boldsymbol{g}^{A}\in R^{n_{A}}$ and $\boldsymbol{g}^{B}\in R^{n_{B}}$ respectively, which can be decrypted by the third party C. Furthemore, to achieve secure multi-party computing, the additively homomorphic encryption is accepted. In the field of homomorphic encryption, a lot of works have been completed [15] [16]. Different computing requirements correspond to different encryption methods, such as PHE, SHE, FHE. After encryption, we can directly perform encrypted data with addition or multiplication operations, the value of decrypting the operation result is consistent with the result of the direct operation on the original data. That is $[\![m]\!]+[\![n]\!]=[\![m+n]\!]$ and $[\![m]\!]\cdot n=[\![m\cdot n]\!]$ with $[\![\cdot]\!]$ represent encryption method. However, homomorphic encryption has no idea to solve exponential calculation yet. So equation (2) cannot directly apply homomorphic encryption. We consider using Taylor expansion to approximate the loss function. Fortunately, it’s proposed in [14] as

The basic idea of newton’s method is to use the first-order gradient and the second-order gradient(Hessian) at the iteration point to approximate the objective function with the quadratic function, and then use the minimum point of the quadratic model as the new iteration point. This process is repeated until the approximate minimum value that satisfies the required accuracy. The newton’s method can highly approximate the optimal value and its speed is quite fast. Though it is very quickly, the calculation is extremely huge. For federated learning, this method is perfect when trading larger computational costs for smaller communication costs.

For convenience, we mainly discuss the one-dimensional situation. For an objective function $f(\boldsymbol{w})$, the problem of finding the extreme value of the function can be transformed into the derivative function $f^{\prime}(\boldsymbol{w})=0$, and the second-order Taylor expansion of the function $f(\boldsymbol{w})$ is obtained

and take the derivative of the above formula and set it to 0, then

it is further organized into the following iterative expression:

where $\lambda$ represent step-size and $H$ represent Hessian.

This formula is an iterative formula of newton method. But this method also has a fatal flaw, that is, in equation (7), the inverse of the Hessian matrix needs to be required. As we all know, not all matrices have inverses. And the computational complexity of the inversion operation is also very large. Therefore, there is quasi-newton methods. BFGS and DFP, approximate newton method.

The central idea of the quasi-newton method is getting a matrix similar to the Hessian inverse without computing the inverse of Hessian. Therefore, the expression of the quasi-newton method is similar to equation (7), as follows

where $C_{k}$ is the matrix used to approximate $H^{-1}$.

In contrast, the update formula is as follows in SGD

Different quasi-newton methods are inconsistent with the iterative formula of $C_{k}$. Therefore, we explain the iterative formula of DFP and BFGS on $C_{k}$ below.

The gradient and the Hessian of Taylor loss of the i-th data sample are given by $\boldsymbol{g}_{i}=\nabla l(\boldsymbol{w};\boldsymbol{x}_{i},y_{i})\approx(\frac{1}{4}\boldsymbol{w}^{T}\boldsymbol{x}_{i}-\frac{1}{2}y_{i})\boldsymbol{x}_{i}$, $H=\nabla^{2}l(\boldsymbol{w};\boldsymbol{x}_{i},y_{i})\approx\frac{1}{4}\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{T}$ respectively. For convenience, we calculate the intermediate variable $\boldsymbol{w}^{T}\boldsymbol{x}$ and express it

The first part is to compare SGD and quasi-Newton. It is applied to credit card dataset, which consists of 30000 instances and each instances holds 23 features. So, we shuffle the order of the instances. Party A holds 12 features, and Party B holds remaining 11 features and corresponding target. By using the two quasi-newton methods of DFP and BFGS, it is compared with the SGD method.

In the second part, to go further, we use BDFL(we proposed) and quasi-newton method to compare. Using the breast cancer dataset, which has 569 instances, 30 atrributes and label. Because there are 20% test dataset, so split them to $X_{A}\in R^{455\times 20}$, $X_{B}\in R^{455\times 10}$ and $Y_{B}\in R^{455\times 1}$. The attribute index held by Party A are from 10-29, and those held by Party B are from 0-9.

In figure 2, it is clear that BFGS is much faster than SGD. In figure 3, it shows BDFL is better than both DFP and BFGS. What is more, we run every model in test dataset.