## 3 Results
### Construction of DP-BCD
For its length, we want to solve for \(R\)_  
\[\frac{2}{\Gamma(N/2)}\int_{0}^{R/(\sqrt{2}\sigma)}\mathrm{d}t\,r^{N-1}e^{-r^ {2}}=p\qquad,\text{with }p\in(0,1)\quad,\]  
_which transforms into_  
\[\frac{1}{\Gamma(N/2)}\int_{0}^{R^{2}/(2\sigma^{2})}\mathrm{d}t\,t^{(N/2)-1}e^ {-t}=p\]  
_and is solved by the inverse lower incomplete gamma function. This is problematic. The high dimension pushes the vector outwards, so that the noise vectors tend to get bigger with increasing number of observations. This leads to noise vectors overwhelming the data and a remainder that is larger than the input label._  
As explained before, only the first party needs to know the labels. Afterwards, during iteration \(t\), party \(j\) obtains the remainder  
\[\mathbf{v}_{t}^{(j)}=y-\sum_{i=1}^{2}\mathbf{X}^{(i)}\mathbf{\beta}_{t}^{(i)}\quad,\text{ where}\quad\mathbf{\beta}_{t}^{(i)}=\left\{ \begin{array}{ll}\sum_{s=1}^{t}\mathbf{\beta}_{(s)}^ {(i)},&\text{for }i<j\\ \sum_{s=1}^{t-1}\mathbf{\beta}_{(s)}^{(i)},&\text{for }i\geq j\end{array} \right.\]  
of the label that is not yet explained by party \(j-1\). From now on we will suppress the sub- and superscripts when possible. The local solution is given by  
\[0=\mathbf{X}^{T}(\mathbf{v}-\mathbf{X}\mathbf{\beta}^{*}-\mathbf{b})\qquad\Rightarrow\qquad\mathbf{ \beta}^{*}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}(\mathbf{v}-\mathbf{b}). \tag{9}\]  
There are two algorithms in use in the protocol. The first is used during the learning phase to communicate the missing part of the labels. It is given by  
\[\mathcal{A}_{t}(\mathbf{X})=\mathbf{v}-\mathbf{X}\mathbf{\beta}^{*}. \tag{10}\]  
The second is used in the revealing phase and is defined by  
\[\mathcal{A}_{r}(\mathbf{X})=\sum_{t=1}^{T}\mathbf{\beta}_{(t)}^{*}, \tag{11}\]  
where \(\mathbf{\beta}^{*}\) is in both cases defined in (9). In the special case of unperturbed learning, i.e., \(\mathbf{b}=0\), we call this solution \(\mathbf{\beta}^{*}\). We start with the privacy of the learning algorithm \(\mathcal{A}_{t}\). We sample \(\mathbf{b}=l\cdot\mathbf{s}\) with \(\mathbf{s}\in S^{N-1}\) uniformly and \(l\) with density \(2\sqrt{\frac{\varepsilon}{2\pi\xi^{2}}}\exp[-\frac{\varepsilon l^{2}}{2\xi^{2}}]\), so that  
\[p_{\xi,\varepsilon}(\mathbf{b})=\frac{\Gamma(\frac{N}{2})}{\pi^{\frac{N}{2}}}\sqrt {\frac{\varepsilon}{2\pi\xi^{2}}}\exp[-\frac{\varepsilon\|\mathbf{b}\|_{2}^{2}}{2 \xi^{2}}] \tag{12}\]  
Thus, the length of the perturbation vector is normally distributed and its direction is uniformly distributed. This ensures that the length of the perturbation vector is independent of the number of observations. The parameter \(\xi\) is the largest allowed value of \(\|\mathbf{v}_{out}\|\) for a successful protocol run. The standard deviation of the length of the perturbation vector is given by \(\xi/\sqrt{\varepsilon}\), where \(\varepsilon\) is the privacy budget for the round and  
\[\xi=\gamma\|\mathbf{v}-\mathbf{X}\mathbf{\beta}^{*}\|_{2}.\]  
The parameter \(\gamma>1\) gives the maximally allowable deterioration in performance compared to the unperturbed case. It is a new parameter introduced here. It must be chosen big enough to satisfy in every iteration \(t\)  
\[\|(\mathbf{v}_{in,(t)}-\mathbf{X}_{i}\mathbf{\beta}^{*}_{(t)})_{\perp_{i}}\|_{2}^{2}\leq\| \mathbf{v}_{in,(t)}-\mathbf{X}_{i}\mathbf{\beta}^{*}_{(t)}\|_{2}^{2}\leq\xi_{(t)}^{2}.\]  
This implies that in each iteration of the protocol, the loss scaling parameter must satisfy  
\[\gamma\geq\sup_{ \begin{subarray}{c}d(\mathbf{X},\mathbf{X})=1\\ m=\operatorname{rk}(\mathbf{X})=\operatorname{rk}(\mathbf{X})\end{subarray} }\Big{\{} \frac{\|\mathbf{v}-\mathbf{X}\mathbf{\beta}^{*}\|_{2}}{\|\mathbf{v}-\mathbf{\tilde{X}}\mathbf{\tilde{ \beta}^{*}}\|_{2}^{2}},\frac{\|\mathbf{v}-\mathbf{\tilde{X}}\mathbf{\tilde{\beta}^{*}}\|_{ 2}}{\|\mathbf{v}-\mathbf{X}\mathbf{\tilde{\beta}^{*}}\|_{2}}\Big{\}}. \tag{13}\]  
Thus, \(\gamma\) represents the cost per round of adding differential privacy to the learning algorithm.