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

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

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 variables 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.

Introduction

In distributed signal processing, a network of nodes (such as sensors or mobile devices) collaborates to solve global optimization problems without centralizing raw data. However, the exchange of intermediate results between neighbors often leaks sensitive local information. Existing privacy-preserving techniques like Differential Privacy (DP) introduce a fundamental trade-off between privacy and accuracy, while Secure Multi-Party Computation (SMPC) is often too computationally expensive for resource-constrained IoT devices.

This paper introduces a "subspace perturbation" framework that achieves perfect accuracy while maintaining high privacy. By injecting noise into a specific "non-convergent" subspace of the algorithm's dual variables, the proposed method eliminates the traditional accuracy-privacy trade-off.

Methodology: Subspace Perturbation

The core innovation lies in the mathematical decomposition of the dual variables used in distributed optimizers like the Primal-Dual Method of Multipliers (PDMM) and ADMM.

Subspace Decomposition and Graph Topology

The authors prove that the dual variables evolve within a space that can be decomposed into a convergent subspace (which determines the final solution) and a non-convergent subspace (which does not). This decomposition is intrinsically linked to the graph topology of the network.

Figure 1: (a) A general graph $G$ with $n=5$ nodes and $m=6$ edges. (b) The bipartite graph representation of the node-edge incidence. (c) An alternative bipartite representation used for subspace analysis.

As illustrated in Figure 1, the relationship between nodes and edges defines the structure of the incidence matrix, which in turn determines the dimensions of these subspaces. For a non-empty non-convergent subspace to exist, the network typically requires the number of edges $m$ to be greater than or equal to the number of nodes $n$ ($m \ge n$).

Noise Insertion and Orthogonality

Nodes randomly initialize their dual variables with high-variance noise specifically within the non-convergent subspace. Because the primal optimization variables are mathematically orthogonal to this noisy subspace, the noise "cancels out" during the iterative process, ensuring convergence to the exact global optimum. Furthermore, the method leverages the broadcasting nature of certain optimizers to minimize the information exposed to potential eavesdroppers.

Experimental Evaluation

The framework was evaluated using simulated environments with randomly generated connected graphs ($n=20$ nodes). Private local data followed a Gaussian distribution. The method was tested on three benchmark problems: Distributed Average Consensus, Distributed Least Squares, and Distributed LASSO.

Key Results

  • Perfect Accuracy: Numerical tests demonstrated that the Mean Squared Error (MSE) reaches $10^{-10}$, effectively achieving zero error and matching non-private algorithms.
  • Comparison with Differential Privacy: Unlike DP, which hits an "accuracy floor" due to persistent noise, the subspace perturbation method continues to converge to the exact solution.
  • Privacy-Level Invariance: The convergence rate remains invariant regardless of the amount of noise added. This allows for near-perfect privacy (measured via mutual information) without sacrificing performance or speed.
  • Security: The method is robust against passive adversaries and eavesdroppers, provided an initial secure communication step is used for dual variable initialization.

Conclusion and Future Work

The subspace perturbation method offers a "free lunch" in privacy-preserving distributed optimization, where privacy does not come at the cost of accuracy. However, the method currently requires an initial secure communication round and assumes an "honest-but-curious" adversary model. Future research may focus on extending this framework to handle sparse networks where $m < n$ and developing robustness against malicious "Byzantine" nodes that might actively sabotage the global result.

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 variables 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},
}
Figure