Distributed Learning without Distress: Privacy-Preserving Empirical Risk Minimization

Bargav Jayaraman, Lingxiao Wang, David Evans, Quanquan GuNeurIPS 2018 · OpenReview

Introduction

Training machine learning models across multiple data owners—such as different hospitals or financial institutions—presents a significant challenge: how can organizations collaborate to build better AI models without exposing sensitive raw data?

By combining Differential Privacy (DP) with Secure Multi-Party Computation (MPC), this paper introduces a method to achieve the same level of accuracy as a centralized system while adding significantly less noise than previous distributed methods. The result is a robust framework that protects against privacy attacks without rendering the final model useless.

The Privacy-Utility Trade-off

Traditionally, there are two main ways to handle distributed, privacy-preserving machine learning, but both have critical flaws:

  1. Secure Multi-Party Computation (MPC): This cryptographic approach keeps the training process private. However, the final model itself is still exposed and can "leak" information about the individuals in the training set through membership inference attacks.
  2. Distributed Differential Privacy: To protect the final model, participants usually add random noise to their local data or gradients before sharing. Unfortunately, in a distributed setting, if every participant adds their own noise, the total noise "piles up." This accumulation often destroys the model's accuracy.

The core problem addressed by the authors is bridging this gap: achieving the rigorous, mathematical privacy guarantees of DP without the massive accuracy hit typically seen in decentralized learning.

Proposed Methodology

The paper proposes two primary strategies, both centered on a clever architectural shift: adding noise inside the secure computation.

  • Output Perturbation (MPC Out P): Each party computes a local model. These models are then aggregated inside an MPC protocol. Crucially, the DP noise (Laplace noise) is generated and added within the MPC environment before the final model is revealed. This ensures that only a single "dose" of noise is added to the total, rather than $m$ separate doses from $m$ parties.
  • Gradient Perturbation (MPC Grad P): This is an iterative approach akin to Stochastic Gradient Descent. In each round, parties aggregate their gradients inside an MPC, add Gaussian noise collaboratively, and update a global model.
  • Zero-Concentrated Differential Privacy (zCDP): For the iterative gradient method, the authors utilize zCDP for privacy accounting. This provides a tighter, more modern way to track how much privacy "budget" is spent over many training rounds, leading to vastly improved accuracy compared to older accounting methods.

Experimental Results

The authors evaluated their methods on three well-known benchmarks: KDDCup99 (network intrusion detection), the Adult Dataset (census income prediction), and KDDCup98 (demographic regression).

Key Insights

  • The Power of Centralized Noise in a Decentralized World: MPC allows a group of untrusting parties to act like a single trusted entity. By generating noise collaboratively inside the MPC, the noise scales with the total dataset size rather than the local dataset size.
  • Asymptotic Improvement: The authors mathematically prove that their method reduces noise by a factor of $m$ (for output perturbation) or $\sqrt{m}$ (for gradient perturbation) compared to previous state-of-the-art distributed methods.
  • Robustness to Data Partitioning: The Gradient Perturbation method maintains high accuracy even when the data is split among thousands of parties—even if each party only holds a single data point.
Table comparing analytical bounds and generated noise across different distributed privacy methods.

As shown in the results, the proposed MPC Grad P method achieved an optimality gap (measuring how far the private model is from a perfect non-private model) on the order of $10^{-3}$. Previous baselines, such as the Pathak method, generated orders of magnitude more noise and were significantly less accurate. For typical privacy requirements (e.g., $\epsilon = 0.5$), the proposed methods produce models that are nearly as accurate as non-private models trained on a central server. Furthermore, the approach scales effectively, remaining viable even in extremely fragmented federated learning scenarios with up to 50,000 parties.

Limitations and Future Work

While highly effective at preserving utility, the approach has a few limitations:

  • MPC Overhead: While the noise is reduced, MPC itself is computationally expensive and requires significant network communication. It is practical, but inherently slower than non-secure distributed learning.
  • Semi-Honest Assumption: The current protocol assumes participants are "semi-honest" (they follow the rules but try to learn what they can from the messages they receive). Hardening the protocol against "malicious" actors who actively cheat is possible but would further increase computational costs.
  • Hyperparameter Tuning: Like most DP methods, performance depends heavily on choosing the right number of iterations ($T$) and regularization parameters ($\lambda$). Tuning these without "peeking" at the data and wasting the privacy budget remains a practical challenge.

Summary updated

Abstract

Distributed learning allows a group of independent data owners to collaboratively learn a model over their data sets without exposing their private data. We present a distributed learning approach that combines differential privacy with secure multi-party computation. We explore two popular methods of differential privacy, output perturbation and gradient perturbation, and advance the state-of-the-art for both methods in the distributed learning setting. In our output perturbation method, the parties combine local models within a secure computation and then add the required differential privacy noise before revealing the model. In our gradient perturbation method, the data owners collaboratively train a global model via an iterative learning algorithm. At each iteration, the parties aggregate their local gradients within a secure computation, adding sufficient noise to ensure privacy before the gradient updates are revealed. For both methods, we show that the noise can be reduced in the multi-party setting by adding the noise inside the secure computation after aggregation, asymptotically improving upon the best previous results. Experiments on real world data sets demonstrate that our methods provide substantial utility gains for typical privacy requirements.
BibTeX
@inproceedings{jayaraman2018distributed,
  author = {Bargav Jayaraman and Lingxiao Wang and David Evans and Quanquan Gu},
  title = {{Distributed Learning without Distress: Privacy-Preserving Empirical Risk Minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HJNYtvZ_-H},
}
Figure