Privacy-Preserving Distributed Optimisation using Stochastic PDMM

Sebastian O. Jordan, Qiongxiu Li, Richard HeusdensICASSP 2024 · OpenReview

TL;DR

This paper tackles the challenge of protecting private data in distributed optimization algorithms, specifically for asynchronous network updates. They introduce a method that guarantees better privacy than previous synchronous approaches without sacrificing accuracy, by deriving a lower bound on noise variance for asynchronous schemes.

What Problem Does This Paper Address?

In today's interconnected world, many applications involve distributed systems where multiple devices (nodes) collaborate to solve a common problem, like signal processing or machine learning. A key challenge is that these nodes often hold sensitive private data (e.g., medical records, financial information). While distributed optimization algorithms allow nodes to work together without a central authority, they typically involve exchanging information, which can lead to privacy leaks. Traditional methods like homomorphic encryption are computationally too expensive for iterative algorithms. A recent approach, "subspace perturbation," offers a lightweight solution by adding noise to specific parts of the data updates. However, this method was designed for synchronous systems, where all nodes update at the same time. This paper addresses the gap for asynchronous systems, where nodes update at different times, a more realistic scenario for many networks. The core problem is how to achieve robust privacy in these asynchronous settings, where the structure that subspace perturbation relies on is absent.

Methods

The authors extend the "subspace perturbation" method, originally developed for synchronous distributed optimization, to asynchronous settings. The Primal-Dual Method of Multipliers (PDMM) is used as the underlying optimization algorithm. For synchronous updates, subspace perturbation works by exploiting a specific subspace of the auxiliary variables that remains unchanged during iterations, allowing noise to be added there without affecting the final solution. In asynchronous systems, this invariant subspace doesn't exist.

The paper's key contribution is deriving a lower bound on the noise variance needed to ensure privacy in asynchronous PDMM. This bound is derived by analyzing the update equations for auxiliary variables in a stochastic setting, where node updates are governed by random variables. They leverage properties of conditional expectation and projection operators, particularly focusing on the component of the auxiliary variable in the orthogonal complement subspace (which is relevant for privacy). The derived bound shows that asynchronous schemes inherently offer a privacy level that is at least as good as, and often better than, synchronous schemes.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations using synthetic data generated for the experiments.

Key Insights and Ideas

  • Asynchronous Advantage: The paper demonstrates that asynchronous distributed optimization schemes, when properly secured, can inherently offer better privacy than their synchronous counterparts. This is a significant finding as asynchronous updates are more common in real-world networks.
  • Noise Variance as a Privacy Metric: The core idea is that by strategically adding noise to auxiliary variables, private data can be obfuscated. The paper quantifies the minimum amount of noise required for a given privacy level in asynchronous settings.
  • Subspace Perturbation's Adaptability: The research shows that the principles of subspace perturbation can be adapted to asynchronous scenarios, overcoming the lack of a fixed invariant subspace by focusing on the statistical properties of the auxiliary variables.
  • Mutual Information as a Privacy Measure: The paper uses mutual information to quantify privacy, which is a well-established information-theoretic metric. This allows for a rigorous comparison of privacy levels.

Key Results

  • Theoretical Bound: The paper derives a lower bound on the noise variance for auxiliary variables in asynchronous PDMM. This bound is shown to be greater than or equal to the bound for synchronous schemes, implying better privacy.
  • Simulation Confirmation: Computer simulations validate the theoretical findings. They show that the variance of the auxiliary variable in the privacy-relevant subspace remains non-zero in asynchronous settings, unlike in synchronous settings where it can converge to zero.
  • Reduced Information Leakage: Simulations also demonstrate that asynchronous schemes lead to lower mutual information between private data and adversary observations compared to synchronous schemes, confirming the improved privacy. For instance, Figure 3 shows that the information loss is consistently lower for asynchronous updates across different initializations.

Limitations and Future Work

  • Assumptions: The analysis relies on certain assumptions, such as the probability of a node being updated being uniform and the existence of at least one honest neighbor. The paper notes that transmission losses would also affect convergence.
  • Specific PDMM Implementation: The results are derived for a specific PDMM formulation. While the authors suggest generalization is possible, further work might be needed for other distributed optimization algorithms.
  • Future Work: The paper suggests exploring more general update probabilities and network structures. Investigating the trade-off between privacy and accuracy in more detail for asynchronous schemes is also a potential avenue. The authors also mention that their work can be extended to other privacy-preserving distributed optimization methods.

Summary updated

Abstract

Privacy-preserving distributed processing has received considerable attention recently. The main purpose of these algorithms is to solve certain signal processing tasks over a network in a decentralised fashion without revealing private/secret data to the outside world. Because of the iterative nature of these distributed algorithms, computationally complex approaches such as (homomorphic) encryption are undesired. Recently, an information theoretic method called subspace perturbation has been introduced for synchronous update schemes. The main idea is to exploit a certain structure in the update equations for noise insertion such that the private data is protected without compromising the algorithm’s accuracy. This structure, however, is absent in asynchronous update schemes. In this paper we will investigate such asynchronous schemes and derive a lower bound on the noise variance after random initialisation of the algorithm. This bound shows that the privacy level of asynchronous schemes is always better than or at least equal to that of synchronous schemes. Computer simulations are conducted to consolidate our theoretical results.
BibTeX
@inproceedings{jordan2024privacy,
  author = {Sebastian O. Jordan and Qiongxiu Li and Richard Heusdens},
  title = {{Privacy-Preserving Distributed Optimisation using Stochastic PDMM}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=BOXzmP0Cdy},
}
Figure