Differentially Private Multi-Party Data Release for Linear Regression

Ruihan Wu, Xin Yang, Yuanshun Yao, Jiankai Sun, Tianyi Liu, Kilian Q. Weinberger, Chong Wang

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:

  1. Shared Random Projection: All parties agree on a public, shared random matrix (specifically a Bernoulli projection).
  2. 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.
  3. 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.
  4. 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

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 allow 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 Gaussian mechanism and show it has the small eigenvalue problem. We further propose our novel method 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.
BibTeX
@inproceedings{wu2022differentially,
  author = {Ruihan Wu and Xin Yang and Yuanshun Yao and Jiankai Sun and Tianyi Liu and Kilian Q. Weinberger and Chong Wang},
  title = {{Differentially Private Multi-Party Data Release for Linear Regression}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=SAlemvIoql9},
}
Figure