Abstract
Differentially Private (DP) data release is a critical technique for disseminating information without compromising the privacy of individuals. While most existing research focuses on single-party scenarios, real-world data is often siloed across multiple stakeholders who own disjoint sets of attributes for the same group of subjects. This paper addresses the challenge of training linear regression models in such multi-party settings. We demonstrate that directly applying the Gaussian mechanism leads to the "small eigenvalue problem," causing model instability. We propose a novel Random Mixing Gaussian Mechanism (RMGM-OLS) that utilizes a shared random projection to ensure privacy while maintaining numerical stability. We prove that our method asymptotically converges to the optimal non-private solution and validate its performance across five real-world datasets.
Introduction
In many collaborative research environments, data is vertically partitioned. For example, multiple hospitals may hold different diagnostic records (e.g., blood tests, imaging, and clinical outcomes) for the same patient cohort. To build a comprehensive predictive model, these attributes must be combined. However, strict privacy regulations like GDPR and HIPAA prevent the sharing of raw data.
Differential Privacy (DP) provides a mathematical framework for sharing data by adding controlled noise. In a multi-party setting, if each party adds noise independently to their portion of the data, the resulting aggregate dataset often becomes unusable. This paper investigates how to release such data for linear regression in a way that is both private and statistically utility-preserving.
The Small Eigenvalue Problem
A standard approach to private linear regression is the De-biased Gaussian Mechanism (DGM-OLS). In this setup, each party adds Gaussian noise to their attributes. To account for the resulting statistical bias, the researcher subtracts the expected noise variance from the Hessian matrix ($X^TX$) during the training phase.
However, the authors identify a critical failure point: the "small eigenvalue problem." When the noise-adjusted Hessian matrix has very small eigenvalues, its inverse becomes extremely large. This causes the resulting model weights to explode, leading to high variance and inaccurate predictions, even as the sample size ($n$) increases.
Proposed Method: Random Mixing (RMGM-OLS)
To overcome the instability of de-biasing, the authors introduce RMGM-OLS (Random Mixing prior to Gaussian Mechanism). The process involves four key steps:
- Shared Random Projection: All parties agree on a public, shared random matrix (specifically a Bernoulli projection).
- Mixing: Each party projects their local data using this matrix before any noise is added. This "mixes" the sensitivity of individual data points across the entire released dataset.
- Noise Addition: Gaussian noise is added to the projected data. Because the projection spreads the signal, the relative amount of noise required to satisfy DP is smaller compared to the total signal as the dataset grows.
- Stable Estimation: Unlike DGM-OLS, this method does not require a subtraction-based de-biasing step. Standard Ordinary Least Squares (OLS) can be applied directly to the released data.
The authors provide a rigorous mathematical proof that RMGM-OLS is asymptotically optimal. As the number of data subjects ($n$) increases, the performance of the private model converges to that of the non-private model.
Experimental Evaluation
The researchers evaluated the proposed method against the de-biased baseline using synthetic data and five diverse real-world datasets: Insurance, Bike Sharing, Superconductor, GPU Kernel Performance, and Year Prediction MSD (Music Song).
Key Results
- Accuracy and Utility: RMGM-OLS outperformed the baseline in 12 out of 15 experimental settings. It consistently achieved lower Mean Squared Error (MSE) across various privacy budgets ($\epsilon$).
- Numerical Stability: Analysis of the Hessian matrices showed that while DGM-OLS suffered from error "explosions" when eigenvalues were small, RMGM-OLS remained stable and clustered near the optimal non-private solution.
- Scalability: On synthetic datasets, RMGM-OLS demonstrated clear asymptotic convergence. In contrast, the de-biased method often failed to improve even with sample sizes as large as 3 million, highlighting the persistent nature of the small eigenvalue problem in naive DP applications.
Discussion and Future Work
RMGM-OLS offers a robust solution for multi-party linear regression, successfully balancing the trade-off between privacy and numerical stability. By avoiding the risky subtraction of noise bias, it ensures that the learning algorithm remains well-conditioned.
However, some limitations remain. The current framework is specifically designed for linear regression; extending the "Random Mixing" logic to non-linear models like logistic regression or neural networks is a primary area for future research. Additionally, the model assumes perfect vertical alignment (the same subjects across all parties), which may not always hold in practice. Finally, while more efficient than cryptographic approaches, the method requires parties to coordinate on a shared random matrix, which may present communication challenges in very high-dimensional settings.
Summary updated