## 3 Results
### Construction of DP-BCD
A generalization to more parties is straightforward. ```
1:\(\epsilon^{\prime}>0\), \(T\in\mathbb{N}\) and \(\gamma>1\)
2:[PERSON] and [PERSON] initiate \(\mathbf{\beta}_{a}\leftarrow\mathbf{0}\) and \(\mathbf{\beta}_{b}\leftarrow\mathbf{0}\), respectively. 3:[PERSON] initiates \(\mathbf{v}_{b}\leftarrow\mathbf{y}\)
4:for\(t\in\{1,\dots,T\}\)do
5:player [PERSON] do
6:\(\xi_{a}=\gamma\|\mathbf{v}_{b}-\mathbf{X}_{a}\mathbf{\beta}^{*}_{a}\|_{2}\)
7:\(\mathbf{b}_{a}\sim p_{\xi_{a},\epsilon^{\prime}/(2T)}\)
8:\(\tilde{\mathbf{\beta}}_{a}\leftarrow(X_{a}^{T}\mathbf{X}_{d})^{-1}\mathbf{X}_{a}^{T}(\mathbf{v }_{b}-\mathbf{b}_{a})\)
9:\(\mathbf{\beta}_{a}\leftarrow\mathbf{\beta}_{a}+\tilde{\mathbf{\beta}}_{a}\)
10:\(\mathbf{v}_{a}\gets\mathbf{v}_{b}-\mathbf{X}_{a}\mathbf{\beta}_{a}\)
11:if\(\|\mathbf{v}_{a}\|_{2}\leq\xi_{a}\)then
12:send \(\mathbf{v}_{a}\) to [PERSON]
13:else
14: abort
15:endif
16:end player
17:player [PERSON] do
18:\(\tilde{\xi}_{b}=\gamma\|\mathbf{v}_{a}-\mathbf{X}_{b}\mathbf{\beta}^{*}_{b}\|_{2}\)
19:\(\mathbf{b}_{b}\sim p_{\xi_{b},\epsilon^{\prime}/(2T)}\)
20:\(\tilde{\mathbf{\beta}}_{b}\leftarrow(\mathbf{X}_{b}^{T}\mathbf{X}_{b})^{-1}\mathbf{X}_{b}^{T}( \mathbf{v}_{a}-\mathbf{b}_{b})\)
21:\(\mathbf{\beta}_{b}\leftarrow\mathbf{\beta}_{b}+\tilde{\mathbf{\beta}}_{b}\)
22:\(\mathbf{v}_{b}\leftarrow\mathbf{v}_{a}-\mathbf{X}_{b}\mathbf{\beta}_{b}\)
23:if\(\|\mathbf{v}_{b}\|_{2}\leq\tilde{\xi}_{b}\)then
24:send \(\mathbf{v}_{b}\) to [PERSON]
25:else
26: abort
27:endif
28:end player
29:endfor
30:[PERSON] sends \(\mathbf{\beta}_{a}\) to [PERSON]. 31:[PERSON] sends \(\mathbf{\beta}_{b}\) to [PERSON]. 32:[PERSON] and [PERSON] publish \((\mathbf{\beta}_{a},\mathbf{\beta}_{b})\). ```  
**Algorithm 2** Differentially private 2-party block coordinate descent algorithm Utility Bound  
During the protocol run, the participants must check in every iteration whether the loss increase is less that a factor \(\gamma\), as demanded in (13). If this is not the case, the protocol will be aborted by the participants, because a model with sufficient utility cannot be trained. Hence, at every single iteration the sum of squared errors, which is the unperturbed loss, is bounded by  
\[\|\mathbf{v}-\mathbf{X}\mathbf{\beta}^{*}\|_{2}^{2}\leq\gamma^{2}\|\mathbf{v}-\mathbf{X}\mathbf{\beta}^ {*}\|_{2}^{2}.\]  
This information can be used in another way. It is directly related to the utility loss and provides an upper bound for the utility loss. In a protocol run with \(k=2\) parties and \(T\) iterations, the sum of squared errors is at most a factor \(\gamma^{2 kT}\) larger than in the unperturbed case. If we denote with \(\mathbf{f}_{*}\) the differentially private predictions and with \(\mathbf{f}_{*}\) those without DP, then we observe that the utility measure  
\[R^{2}=1-\frac{\|\mathbf{y}-\mathbf{f}_{*}\|_{2}^{2}}{Var_{y}}\geq 1-\gamma^{2 kt}\frac{ \|\mathbf{y}-\mathbf{f}_{*}\|_{2}^{2}}{Var_{y}}=1-\gamma^{2 kt}(1-R_{*}^{2}). \tag{16}\]  
This shows that we obtain a utility guarantee along with the privacy guarantee. The additional utility loss is bounded by parameters that can be set before the start of the protocol. This proves the following theorem. **Theorem 1**. : _The linear regression of \(\mathbf{y}\), held by Alice, against the data \((\mathbf{X}_{a},\mathbf{X}_{b})\) can be approximated by Algorithm 2, provided that \(\operatorname{rk}(\mathbf{X}_{a})=m_{a}\) and \(\operatorname{rk}(\mathbf{X}_{b})=m_{b}\) are of full column rank and contain \(N\) data points, where \(N>m_{a}\) and \(N>m_{b}\). For \(T\in\mathbb{N}\), \(e^{\prime}>0\) and \(\gamma>1\) it is an \(\epsilon^{\prime}\)-differentially private algorithm. Furthermore, the utility is bounded from below by_  
\[\qquad=\frac{\mathbb{P}[\mathbf{b}_{1}\in\ker(\mathbf{X}_{1}^{T})+\mathbf{v} _{1,\perp_{1}}]}{\mathbb{P}[\mathbf{b}_{2}\in\ker(\mathbf{X}_{2}^{T})+\mathbf{v}_{2,\perp _{2}}]}\]0  
_where \(R_{*}^{2}\) is the utility of the block coordinate algorithm without differential privacy (Algorithm 1)._