Abstract
Differentially Private (DP) data release is a promising technique to disseminate data without compromising the privacy of data subjects. However, the majority of prior work has focused on scenarios where a single party owns all the data. In this paper, we focus on the multi-party setting, where different stakeholders own disjoint sets of attributes belonging to the same group of data subjects. Within the context of linear regression that allows all parties to train models on the complete data without the ability to infer private attributes or identities of individuals, we start with directly applying the Gaussian mechanism and show it has the small eigenvalue problem. We further propose our novel method, RMGM-OLS, and prove it asymptotically converges to the optimal (non-private) solutions with increasing dataset size. We substantiate the theoretical results through experiments on both artificial and real-world datasets.
Introduction
Most research in differential privacy (DP) assumes a single party owns all the data. However, in many real-world scenarios—like healthcare—different organizations hold different pieces of the puzzle for the same individuals. For example, one clinic might have blood test results while another has CT images for the same set of patients.
The challenge is to release a combined, privacy-preserving dataset that allows researchers to train accurate linear regression models without compromising individual privacy or allowing the parties to "see" each other's raw data. A naive approach is to have each party add Gaussian noise to their data. However, to get an accurate model later, you have to "de-bias" the results by subtracting the noise's variance. This often leads to the small eigenvalue problem: the resulting matrices become nearly singular, causing the model's weights to explode and making the final results practically useless.
Methodology
This paper introduces RMGM-OLS, a novel algorithm for releasing datasets from multiple parties while maintaining differential privacy. By using a "random mixing" technique before adding noise, the authors overcome the numerical instability issues that plague standard DP linear regression methods.
The authors compare two main approaches:
- DGM-OLS (De-biased Gaussian Mechanism): Each party adds Gaussian noise directly to their local data. The central learner then attempts to remove the calculated bias from the Hessian matrix during training.
- RMGM-OLS (Random Mixing prior to Gaussian Mechanism): This is the paper's core contribution.
- Shared Projection: All parties share a random Bernoulli matrix $B$.
- Random Mixing: Each party projects their data along the sample-wise dimension ($BD^j/\sqrt{k}$) before adding a smaller amount of Gaussian noise.
- Vanilla Training: Because the noise is relatively small compared to the "mixed" signal, the learner can simply use standard Ordinary Least Squares (OLS) without a problematic de-biasing step.
The authors prove that RMGM-OLS is asymptotically optimal, meaning that as the dataset size grows, the private model's weights converge to the weights of a model trained on the original, non-private data.
Experimental Evaluation
The researchers evaluated their methods on a variety of datasets:
- Synthetic Dataset: Used to verify theoretical convergence properties with up to 3 million samples.
- Real-world Datasets (from UCI and Kaggle): Including Insurance (medical premiums), Bike (rental counts), Superconductor (critical temperatures), GPU (execution times), and Music Song (release years).
These datasets ranged from approximately 1,000 to over 400,000 samples, with feature counts from 9 to 90.
Key Insights
- The De-biasing Trap: While de-biasing works in expectation, a single "bad" sample of noise can create a Hessian matrix with near-zero eigenvalues. When you invert this matrix to solve for model weights, the error is magnified exponentially.
- Random Mixing as a Buffer: By projecting the data into a lower-dimensional space ($k < n$), the signal is "mixed" across samples. This allows the added noise to diminish relative to the signal as the number of samples $n$ increases, bypassing the need for explicit (and unstable) de-biasing.
- Stability over Pure Rate: While the DGM-OLS method theoretically has a faster convergence rate relative to $n$, its numerical instability makes it far worse in practice than RMGM-OLS, even with millions of data points.
Results
- Superior Accuracy: RMGM-OLS achieved the lowest Mean Squared Error (MSE) in 12 out of 15 experimental settings across the five real-world datasets.
- Empirical Convergence: In synthetic tests, RMGM-OLS showed clear convergence toward the optimal non-private solution as $n$ increased. In contrast, DGM-OLS failed to converge even at $n = 3,000,000$ due to the small eigenvalue problem.
- Privacy-Utility Trade-off: The method maintains high utility even with strict privacy budgets (low $\epsilon$ values), outperforming "biased" baselines that don't account for noise at all.
Conclusion and Future Work
RMGM-OLS provides a robust framework for multi-party linear regression under differential privacy. However, several avenues for future work remain:
- Model Scope: The current work is strictly focused on linear regression. Extending this "random mixing" framework to classification tasks (like logistic regression) is a key next step.
- Subject Alignment: The method assumes all parties have data for the exact same set of individuals. Future research could explore "relaxed" versions where the sets of individuals only partially overlap.
- Hyperparameter Tuning: The projection dimension $k$ is a critical hyperparameter that requires careful selection to balance the convergence rate and noise reduction.
Summary updated