Privacy-Preserving Distributed Optimization via Subspace Perturbation: A General Framework

Qiongxiu Li, Richard Heusdens, Mads Græsbøll Christensen

TL;DR

This paper introduces a novel "subspace perturbation" method that allows distributed networks to solve optimization problems with perfect accuracy while keeping local data private. By injecting noise into a specific "non-convergent" subspace of the algorithm's dual variables, the authors eliminate the traditional trade-off between privacy and accuracy found in methods like Differential Privacy.

What Problem Does This Paper Address?

In distributed signal processing, a network of nodes (like phones or sensors) works together to solve a global problem—such as training a machine learning model or calculating an average—without sending all data to a central server. However, to collaborate, nodes must exchange intermediate calculation results with their neighbors.

The problem is that these exchanged messages often leak sensitive local information (e.g., GPS coordinates, medical records, or power consumption). Existing solutions have major drawbacks:

  1. Differential Privacy (DP): Adds noise to the data, which protects privacy but inherently degrades the accuracy of the final result.
  2. Secure Multi-Party Computation (SMPC): Provides high security but is computationally heavy and requires significant communication overhead, making it impractical for resource-constrained IoT devices.

The authors seek a "best of both worlds" solution: an algorithm that is computationally light, requires no central coordinator, and achieves the exact optimal solution without leaking private data.

Methods

The core innovation is the Subspace Perturbation framework. The authors analyze the mathematical structure of popular distributed optimizers like the Primal-Dual Method of Multipliers (PDMM), ADMM, and Dual Ascent.

Key steps include:

  • Subspace Decomposition: They prove that the "dual variables" (internal markers used to enforce constraints between nodes) evolve within a space that can be split into two parts: a convergent subspace (which affects the final answer) and a non-convergent subspace (which does not).
  • Noise Insertion: Nodes randomly initialize their dual variables with high-variance noise specifically within the non-convergent subspace.
  • Orthogonality: Because the actual optimization variables are mathematically orthogonal to this noisy subspace, the noise "cancels out" during the calculation of the final result.
  • Broadcasting Property: The method leverages the broadcasting nature of PDMM, meaning nodes only need to share their updated optimization variables, further reducing the "surface area" for potential eavesdroppers.

Datasets

The paper evaluates the framework using simulated environments rather than static datasets, which is standard for theoretical optimization papers:

  • Network Topology: Randomly generated graphs with $n=20$ nodes, ensuring connectivity.
  • Data Generation: Private local data for each node was randomly generated from a Gaussian distribution with unit variance.
  • Applications: The framework was tested on three benchmark problems:
  • Distributed Average Consensus: Nodes finding the global average of their private values.
  • Distributed Least Squares: Solving overdetermined linear systems.
  • Distributed LASSO: Finding sparse solutions for underdetermined systems.

Key Insights and Ideas

  • The "Free Lunch" of Privacy: The most striking insight is that privacy does not have to cost accuracy. In this framework, the convergence to the exact global optimum is mathematically guaranteed regardless of how much noise is added.
  • Privacy-Level Invariance: Unlike Differential Privacy, where more privacy means slower convergence or worse results, here the convergence rate is invariant to the amount of noise. You can add massive amounts of noise to ensure near-perfect privacy without making the algorithm run longer.
  • Adversary Robustness: The method is shown to be secure against both passive adversaries (curious nodes following the protocol) and eavesdroppers (external parties intercepting messages), provided the first initialization step uses a secure channel.

Key Results

  • Accuracy: Numerical tests show that the Mean Squared Error (MSE) for the proposed method drops to $10^{-10}$ (effectively zero), matching the performance of non-private algorithms.
  • Comparison with DP: In head-to-head tests (Fig. 6), Differential Privacy methods hit an "accuracy floor" where they cannot get any closer to the true solution due to noise. The subspace perturbation method continues to converge to the exact solution.
  • Information Leakage: Using mutual information as a metric, the authors demonstrate that as the variance of the inserted noise increases, the information an adversary can learn about the private data approaches zero.

Limitations and Future Work

  • Initial Secure Step: The method requires one initial round of secure communication (e.g., via encrypted channels or a Trusted Third Party) to share the noisy starting dual variables. While this only happens once, it is a prerequisite.
  • Graph Topology Constraints: The "non-convergent subspace" must be non-empty for this to work. This generally requires the number of edges in the network to be greater than or equal to the number of nodes ($m \ge n$), which might not hold in very sparse networks.
  • Active Adversaries: The paper assumes "honest-but-curious" nodes. It does not account for "malicious" nodes that might intentionally send false data to sabotage the global result. Extending this to "Byzantine-robust" optimization is a likely future direction.

Summary updated

Abstract

As the modern world becomes increasingly digitized and interconnected, distributed signal processing has proven to be effective in processing its large volume of data. However, a main challenge limiting the broad use of distributed signal processing techniques is the issue of privacy in handling sensitive data. To address this privacy issue, we propose a novel yet general subspace perturbation method for privacy-preserving distributed optimization, which allows each node to obtain the desired solution while protecting its private data. In particular, we show that the dual variable introduced in each distributed optimizer will not converge in a certain subspace determined by the graph topology. Additionally, the optimization variable is ensured to converge to the desired solution, because it is orthogonal to this non-convergent subspace. We therefore propose to insert noise in the non-convergent subspace through the dual variable such that the private data are protected, and the accuracy of the desired solution is completely unaffected. Moreover, the proposed method is shown to be secure under two widely-used adversary models: passive and eavesdropping. Furthermore, we consider several distributed optimizers such as ADMM and PDMM to demonstrate the general applicability of the proposed method. Finally, we test the performance through a set of applications. Numerical tests indicate that the proposed method is superior to existing methods in terms of several parameters like estimated accuracy, privacy level, communication cost and convergence rate.
BibTeX
@article{li2020privacy,
  author = {Qiongxiu Li and Richard Heusdens and Mads Græsbøll Christensen},
  title = {{Privacy-Preserving Distributed Optimization via Subspace Perturbation: A General Framework}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=VpKMi7v5Gtr},
}

Loading related content...

Figure