Decentralized Differentially Private Power Method

Andrew Campbell, Anna Scaglione, Sean Peisert · 2025

Read Decentralized Differentially Private Power Method by Andrew Campbell, Anna Scaglione, Sean Peisert (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22849.txt.

Introduction

Andrew Campbell, Anna Scaglione, and Sean Peisert design a way for a network of agents to find shared patterns in data none of them fully sees, in a 2025 paper. Each agent holds only some rows of the data table, and there is no central collector. Their method runs a private version of the power method, the classic route to the top patterns, across the network.

Agents pass along only partial summaries of the current estimate, and rely on random starts plus tuned noise to meet a formal privacy guarantee. The authors prove both the privacy level and how fast it settles, with network shape built into the rates. On real data it beat naive local private methods, above all at middle privacy settings.

Catalog record

CREATORAndrew Campbell, Anna Scaglione, Sean Peisert
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22849

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decentralized Differentially Private Power Method Andrew Campbell, Anna Scaglione, Sean Peisert Abstract We propose a novel Decentralized Differentially Private Power Method (D-DP-PM) for performing Principal Component Analysis (PCA) in networked multi-agent settings. Unlike conventional decentralized PCA approaches where each agent accesses the full n-dimensional sample space, we address the challenging scenario where each agent observes only a subset of dimensions through row-wise data partitioning. Our method ensures ( ϵ , δ ) (\epsilon,\delta) -Differential Privacy (DP) while enabling collaborative estimation of global eigenvectors across the network without requiring a central aggregator. We achieve this by having agents share only local embeddings of the current eigenvector iterate, leveraging both the inherent privacy from random initialization and carefully calibrated Gaussian noise additions. We prove that our algorithm satisfies the prescribed ( ϵ , δ ) (\epsilon,\delta) -DP guarantee and establish convergence rates that explicitly characterize the impact of the network topology. Our theoretical analysis, based on linear dynamics and high-dimensional probability theory, provides tight bounds on both privacy and utility. Experiments on real-world datasets demonstrate that D-DP-PM achieves superior privacy-utility tradeoffs compared to naive local DP approaches, with particularly strong performance in moderate privacy regimes ( ϵ ∈ [ 2 , 5 ] \epsilon\in[2,5] ). The method converges rapidly, allowing practitioners to trade iterations for enhanced privacy while maintaining competitive utility. I Introduction The goal of computing the singular vectors of decentralized data is a critical data analysis task used in both research and commercial settings. For example, the eigenvector estimation of the covariance matrix of a dataset {\bm{X}}\in\mathbb{R}^{n\times d} can be used for learning distance embeddings, performing a dimensionality reduction, or for the construction of a similarity matrix. However, as the big data paradigm becomes more popular there is a growing need for incorporating privacy into data analysis pipelines. While distributed Principal Component Analysis (PCA) methods [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] provide some degree of privacy, Differentially Privacy (DP) is required to make formal privacy guarantees. [ 8 ] demonstrated that the eigenvectors, whether produced in a centralized or decentralized setting, are vulnerable to the membership inference attack unless DP is included. In this paper we focus on the Decentralized Power Method (D-PM) [ 1 ] and its adaptions to the DP setting. In this work, we aim to estimate the eigenvectors of the covariance matrix {\bm{X}}{\bm{X}}^{\top} in a decentralized manner (or left singular vectors of {\bm{X}} ), given a data matrix {\bm{X}}\in\mathbb{R}^{n\times d} . Here, n represents the number of data samples, each of dimension d . We assume that our dataset is partitioned row-wise among m agents in a network. Specifically, each agent i holds a data matrix {\bm{X}}_{i}\in\mathbb{R}^{n_{i}\times d} where \sum_{i=1}^{m}n_{i}=n . , such that: \displaystyle{\bm{X}}=\begin{bmatrix}{\bm{X}}_{1}\\ \vdots\\ {\bm{X}}_{m}\end{bmatrix}. (1) This is a different set up from the prior art which assumes two different scenarios. The most common one, as in [ 5 , 9 , 10 , 11 , 12 ] distributes the data column wise, i.e each agent has {\bm{X}}_{i}\in\mathbb{R}^{n\times d_{i}} where \displaystyle{\bm{X}}=\begin{bmatrix}{\bm{X}}_{1}&\ldots&{\bm{X}}_{m}\end{bmatrix}. (2) See Figure 1 for a visualization of the two methods. The second case considered in the literature, as in [ 13 , 14 , 15 ] , assume each agent has a portion of {\bm{X}}{\bm{X}}^{\top} , denoted {\bm{A}}_{i} where \displaystyle{\bm{X}}{\bm{X}}^{\top}=\sum_{i=1}^{m}{\bm{A}}_{i}. (3) This is not possible in our case, since the agents only have access to the block diagonal elements of {\bm{X}}{\bm{X}}^{\top} ( {\bm{X}}_{i}{\bm{X}}_{i}^{\top} ). It is worth noting that the partitioning schemes in ( 1 ),( 2 ), and ( 3 ) are fundamentally different and require different solutions. To elucidate this, consider the sample wise data splitting in ( 1 ): each agent lacks the full dimensional space of the eigenvectors. Alternatively, consider case ( 2 ) or ( 3 ): each agent has the full dimension of the eigenvectors. Before continuing we clarify the notation and define some preliminaries. I-A Notation and Preliminaries {\bm{X}}\in\mathbb{R}^{n\times d} is the global data matrix with n samples of d dimension. Each of the m agents, denoted by its index i , has local dataset {\bm{X}}_{i}\in\mathbb{R}^{n_{i}\times d} where \sum_{i=1}^{m}n_{i}=n . That is we only assume ( 1 ) from here on out. {\bm{U}}\bm{\Sigma}{\bm{V}}^{\top}={\bm{X}} refers to the Singular Value Decomposition (SVD) of {\bm{X}} and {\bm{U}}_{i}\bm{\Sigma}_{i}{\bm{V}}_{i}^{\top}={\bm{X}}_{i} the SVD of {\bm{X}}_{i} . Additionally, we always assume the goal is to approximate {\bm{U}} and not {\bm{V}}^{\top} . Generally \bm{\Sigma} refers to the covariance of a specific probability distribution, but in the occasion when it refers to the singular values of some matrix {\bm{A}} we will denote this by \bm{\Sigma}({\bm{A}}) . Similarly we let {\bm{U}}\bm{\Lambda}{\bm{U}}^{\top}={\bm{X}} refer to the eigen decomposition. \lambda_{j} refers to the j- th eigen value of {\bm{X}} . If if is ambiguous as to which eigen value we refer to, we will use the following notation, \lambda_{j}({\bm{A}}) to identify the j eigen value of matrix {\bm{A}} . Eigen values are always assumed to be in descending order, i.e. \lambda_{j}\geq\lambda_{j+1} . Let {\bm{v}} refer to the principal eigenvector of {\bm{X}}{\bm{X}}^{\top} and let {\bm{q}} refer to its decentralized power method approximation. As in the case with the matrix decomposition, {\bm{q}}_{i}\in\mathbb{R}^{n_{i}} refers to agent i ’s portion of the eigenvector where \displaystyle{\bm{q}}=\begin{bmatrix}{\bm{q}}_{1}\\ \vdots\\ {\bm{q}}_{m}\end{bmatrix}. (4) In regards to differential privacy we consider the Probabilistic DP definition which is a strictly tighter notion of DP [ 16 ] . The classical (\epsilon,\delta)- DP is defined below followed by the (\epsilon,\delta)- PDP definition that we use. Definition 1 ( (\epsilon,\delta)-DP [ 17 ] ) . Let {\mathcal{M}} be a randomized algorithm for publishing a query defined over set of databases \bm{{\mathcal{D}}} . Then \forall\bm{{\bm{X}}},\bm{{\bm{X}}}^{\prime}\in\bm{{\mathcal{D}}} such that {\bm{X}} and {\bm{X}}^{\prime} are adjacent, {\mathcal{M}} is (\epsilon,\delta)- DP if \forall{\mathcal{S}}\subset\operatorname{Range}({\mathcal{M}}) \displaystyle\Pr\left[{\mathcal{M}}({\bm{X}})\in{\mathcal{S}}\right]\leq e^{\epsilon}\Pr\left[{\mathcal{M}}({\bm{X}}^{\prime})\in{\mathcal{S}}\right]+\delta. (5) Definition 2 ( (\epsilon,\delta)-PDP [ 18 ] ) . Let {\bm{X}},{\bm{X}}^{\prime}\in\mathcal{D} be adjacent data sets in database \mathcal{D} . Let \mathcal{M} denote a query mechanism over \mathcal{D} with output given by \tilde{q} and where \tilde{q}\sim f(\tilde{q}|{\bm{X}}) . We say \mathcal{M} is PDP if \displaystyle\Pr\left(\left|\ln\dfrac{f(\tilde{q}|{\bm{X}})}{f(\tilde{q}|{\bm{X}}^{\prime})}\right|>\epsilon\right)\leq\delta. (6) We chose Definition 2 as it provides a more intuitive understanding of DP since it connects DP with the hypothesis testing over probability distributions. However, to have a useful notion of privacy we need to formally define the threat model. Fig. 1: Left: The state split we consider. Right: the standard data split considered by the literature. The color represents a unique agent’s dataset. Threat Model : We assume that each agent behaves collaboratively—it will not inject false data, ignore received information, collude, etc.—but remains curious and thus potentially attempts to infer the data held by other agents. No agent communicates with the outside world meaning the privacy leakage is only with respect to the agents. More formally, each agent should be prevented from reconstructing the specific data used by other agents for the principal components computation. Furthermore, given that our setup assumes no trustworthy centralized node, it falls under the Local Differentially Privacy (LDP) setting [ 19 ] . We are interested in providing guarantees on the privacy leakage of node i with respect to (w.r.t) node j . That is, given the information node j has available locally and the information node j has received from the network, we want to formally bound node j ’s

Read the complete text