REVIEW 4 major objections 6 minor 30 references
Decentralized Differentially Private Power Method
T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper claims that a power method for PCA can be made differentially private in a fully decentralized network with row-wise partitioned data, and that preserving Gaussianity yields a closed-form (ε,δ)-DP bound and a convergence rate…
desk verdict A clever algorithm for a genuinely underexplored row-wise decentralized PCA setting, but the central privacy proof conditions on hidden local randomness and never delivers the claimed marginal (ε,δ)-DP guarantee; the convergence theorem has its own unresolved fixed-point issue. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the Gaussian-process representation of the algorithm: with $q^{(0)} \sim \mathcal{N}(0, \sigma_q^2 I)$ and per-iteration $p^{(t)} \sim \mathcal{N}(0, \sigma_{p(t)}^2 I)$, the consensus-augmented linear dynamics give $y^{(T)} = M q^{(0)} + L P$ for an explicit block matrix pair $(M, L)$, and the final iterate satisfies $q^{(T)} \sim \mathcal{N}(0, \Omega)$ with $\Omega = \alpha^{2T} \sigma_q^2 (\Xi\Xi^\top)^T + \sum_{k} \alpha^{2(T-k)} \sigma_{p(k)}^2 (\Xi\Xi^\top)^{T-k}$. This single identity carries both analyses: the privacy bound computes the Rényi divergence between two such Gaussians after conditioning on the agent's own randomness, and the convergence bound applies Hanson–Wright to the quadratic form $s^\top Q s / s^\top \Omega s$ with $s \sim \mathcal{N}(0, I)$.
What would settle it
For a fixed two-agent ring graph, fix a pair of adjacent datasets differing in one row, run Monte Carlo draws of $q^{(0)}$ and all $p^{(t)}$, compute the release $y^{(T)}$ under both datasets, and estimate the tail probability $\Pr(\ln(f(y|X)/f(y|X')) > \epsilon)$; if this exceeds the paper's $\delta$ for any privacy schedule, then the conditional argument in Theorem 2 does not yield a valid marginal DP guarantee.
Extended reading notes
Core claim
The central discovery is that a deliberately Gaussian-preserving design—random Gaussian initialization, a fixed rescaling α instead of normalization, and Gaussian per-iteration noise—lets the entire decentralized power iteration be treated as a Gaussian process. The stacked vector of all releases $y^{(T)}$ satisfies $y^{(T)} = M q^{(0)} + L P$, so each agent's observed release conditional on its own randomness is Gaussian, and Theorem 2 bounds the privacy loss through the closed-form Rényi divergence of two Gaussians, establishing $(\epsilon,\delta)$-DP. The same representation gives $q^{(T)} \sim \mathcal{N}(0, \Omega)$, and applying Hanson–Wright and Davis–Kahan yields Theorem 3: the sine of the angle between the iterate and the true principal eigenvector is bounded by a Hanson–Wright term plus an explicit consensus-error term proportional to $\lambda_2(W)^c$ and a power-iteration term proportional to $(\mu_2/\mu_1)^{2T}$, showing convergence at essentially the centralized rate with additive floors set by consensus and DP noise.
Load-bearing premise
The privacy proof conditions on each agent's own random initialization and per-iteration noise as if the adversary knew them, and the paper does not supply the marginalization step that would turn those conditional Gaussian privacy losses into a uniform (ε,δ)-DP guarantee for the algorithm as a whole.
Editorial extensions
If this is right
- Practitioners can run private PCA on row-partitioned data in peer-to-peer networks without trusting any central node, with a formal $(\epsilon,\delta)$-DP guarantee.
- The convergence rate matches the centralized power method up to additive errors, so for moderate privacy budgets ($\epsilon \in [2,5]$) the method empirically beats adding Gaussian noise directly to the data.
- Agents can trade iterations for privacy: fast convergence means fewer power iterations reduce the number of noisy releases and lower $\delta$ for fixed $\epsilon$.
- Consensus rounds cost no extra privacy, since values shared during consensus are already part of the public release, so topology-induced error can be shrunk by increasing the number of consensus steps $c$.
Reading between the lines
- If the conditional-privacy argument can be upgraded to a marginal one, the same Gaussian structure would likely yield a concentrated differential privacy (zCDP) bound for the full mechanism, connecting directly to the DP toolkit used in federated PCA.
- The Gaussian-preserving trick may extend beyond the power method: any linear iterative algorithm with Gaussian initialization and additive Gaussian noise, such as decentralized SGD or ADMM, could inherit the same closed-form Rényi divergence analysis.
- A testable extension is to replace the fixed rescaling $\alpha$ with a per-iteration schedule that keeps the iterate norm near 1 while preserving Gaussianity, potentially reducing the saturation floor in Theorem 3.
- The empirical comparison is only against naive local DP; a head-to-head with column-partitioned DP-PCA methods on adapted data would clarify whether the row-partition setting is intrinsically harder or easier in terms of privacy-utility tradeoffs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes D-DP-PM, a decentralized differentially private power method for PCA when the data matrix is partitioned row-wise across agents. Each agent maintains a local portion q_i of the eigenvector iterate, computes local projections z_i = X_i^T q_i, aggregates them via average consensus, adds Gaussian noise, and rescales by a fixed factor alpha instead of normalizing, in order to preserve Gaussianity. The paper claims an (epsilon,delta)-DP guarantee via a Renyi-divergence argument on the stacked releases, and a high-probability convergence bound that separates the effects of consensus error and DP noise. Experiments on four datasets compare the method against a local-noise baseline.
Significance. If the analysis were correct, the paper would make a meaningful contribution: it appears to be the first decentralized DP power method for row-wise partitioned data without a central aggregator, and the Gaussian-preserving design yields a clean separation of utility and privacy terms. The convergence theorem's explicit dependence on the mixing matrix and the consensus steps is also valuable. However, both main theorems have serious flaws, so the paper does not currently establish its claimed privacy or utility guarantees.
major comments (4)
- [Section III.A.1, Theorem 2, Eqs. (25)-(30), Appendix B1] Theorem 2 bounds the tail of the privacy-loss random variable L_XX'(y_i) := ln[f(y_i | X, q_i^(0), p_i^(1..T)) / f(y_i | X', q_i^(0), p_i^(1..T))], conditioning on agent i's private randomness. This is not the privacy-loss random variable of the mechanism: Definitions 1 and 2 require the output distributions f(y_i | X) = E_{q_i,p_i}[f(y_i | X, q_i, p_i)] and f(y_i | X'), with all algorithm randomness marginalized. Because the adversary node j does not know q_i^(0) or p_i^(t), the conditional distributions are not the release distributions. The Renyi divergence in (33)-(34) depends on q_i^(0) and p_i^(t) through the mean of (29), and is not bounded uniformly; in the equal-covariance case the divergence grows with ||q_i^(0)||^2 + sum_t ||p_i^(t)||^2, which is unbounded. A per-realization Chernoff bound therefore does not imply a DP guarantee for the mixture. Thus Theorem 2 is vacuous as a privacy proof, and the delta values in Fig. 3 are not evidence for the headline privacy claim.
- [Section II.A threat model and Section III.A] The manuscript claims to bound node j's ability to infer node i's data, but the analysis bounds the privacy loss of y_i, agent i's own stacked releases, conditional on agent i's randomness. Node j's actual view consists of the messages it receives over the network (e.g., neighbors' z_j^(t) at each consensus step and the final shared q^(T)); this view is not defined or analyzed as a random variable. A bound on the privacy of y_i alone cannot bound inference from a different, potentially more informative, observation set. The conditional distribution in (29) is particularly inappropriate because it conditions on information the adversary does not possess.
- [Section III.B, Theorem 3, Appendix C1] The quantity Theta is defined as Theta = 1 - v^T v / Tr(Omega) + Delta, with Delta required to satisfy Delta >= [2||(Q - Theta Omega)||_F sqrt(log(1/gamma)) + 2||(Q - Theta Omega)||_2 log(1/gamma)] / Tr(Omega). Since Q - Theta Omega depends on Theta and hence on Delta, the displayed inequality is an implicit condition on Delta. The proof does not show that a Delta satisfying this condition exists, nor does it provide a value for the first term of (40). Consequently, the high-probability bound (40) is not established. Additionally, the theorem statement uses v^T v where the derivation leading to (70) uses v^T Omega v; the statement should be corrected.
- [Section III.B, Appendix C1, Eqs. (79)-(80)] The proof asserts E = ||Xi - X X^T|| <= n_i m lambda_c^2(W) without derivation. Eq. (14) and the consensus error bound in Appendix A1 only give ||Xi - X X^T|| = O(lambda_2(W)^c), with a constant depending on the local data through ||z - zbar||; the bound n_i m is not obtained. Since Assumption 3 only postulates E <= lambda_1 - lambda_2, the final additive term in (40) is unsupported.
minor comments (6)
- [Algorithm 1, line 3] The deflation step uses q_{l-1} z^{(T-1/2)}; for l=1, q_0 is undefined, and Section II.C indicates the update should use z^{(T+1/2)}. Please clarify.
- [Eq. (14)] The notation lambda_c^2(W) should be lambda_2(W)^c to avoid ambiguity with an eigenvalue squared.
- [Theorem 2 and Definitions 1-2] The subscript i in delta_i is introduced for the conditional probability in (30), but the connection to the unconditional delta in Definition 2 is not stated.
- [Section IV.B] The printed 4x4 mixing matrix W does not have all rows summing to 1 as displayed; please fix the formatting.
- [Section I.A] The claim that PDP is 'a strictly tighter notion of DP' is not justified; Definition 2 is a different privacy formulation, not necessarily a tightening of Definition 1.
- [Section IV] The experimental section does not report how the LDP noise variance was calibrated to the same (epsilon,delta) guarantees, nor how the parameter grid search used the unproven privacy bound; a reproducibility statement would be helpful.
Circularity Check
No significant circularity: the privacy and convergence bounds are derived from stated assumptions and standard inequalities, not from fitted inputs or self-citation chains.
full rationale
The paper's central claims are Theorem 2 (DP bound) and Theorem 3 (convergence bound). Theorem 2 is obtained from the explicit linear-Gaussian representation of the releases (Eqs. 16-19, 25-29), the closed-form Rényi divergence for Gaussians, and a Chernoff bound; none of these inputs contains the target (ε,δ)-DP guarantee as a premise, and no fitted parameter is renamed as a prediction. Theorem 3 is derived from the same linear dynamics, the spectrum of Ξ, Davis-Kahan perturbation bounds, and Hanson-Wright concentration, again without assuming the conclusion. The only self-citation is to the prior decentralized power method [1], which is used as a standard building block rather than as an authority that forces the paper's privacy or convergence conclusions. The conditioning in Theorem 2 on agent i's private randomness and the self-referential definition of Δ in Theorem 3 are potential correctness or soundness concerns, but they are not circular reductions: the paper does not define the target quantity in terms of the derived bound, nor does it fit parameters to the data and then present the fit as a prediction. The empirical section tunes hyperparameters and reports measured error and δ, but the headline claims rest on the analytical theorems, so the derivation chain is self-contained.
Assumptions & free parameters
free parameters (5)
- alpha (scaling factor) =
Not reported; chosen by grid search per dataset and epsilon
- sigma_q (initialization noise std) =
Suggested as 1/sqrt(n) but not fixed; can be tuned
- sigma_p(t) (per-iteration noise schedule) =
Not reported; chosen by grid search
- T (number of iterations) =
Set around T* from non-private convergence to 1e-3; tuned per epsilon
- c (consensus steps) =
Not explicitly reported in experiments
assumptions (4)
- standard math Assumption 1: Eigenvalues of XX^T are distinct and decreasing.
- domain assumption Assumption 2: Mixing matrix W is doubly stochastic, undirected, strongly connected.
- domain assumption Assumption 3: ||Xi - XX^T|| <= lambda_1 - lambda_2.
- domain assumption Adjacent datasets differ by a single row with ||X - X'|| <= 1.
Cite this review
Pith. "Pith review of Decentralized Differentially Private Power Method." pith.science (2026). https://pith.science/paper/RE4I3Z2V
@misc{pith2026250722849,
author = {Pith},
title = {Pith review of: Decentralized Differentially Private Power Method},
year = {2026},
howpublished = {\url{https://pith.science/paper/RE4I3Z2V}},
note = {Machine review of arXiv:2507.22849}
}
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 ($\epsilon\in[2, 5]$). The method converges rapidly, allowing practitioners to trade iterations for enhanced privacy while maintaining competitive utility.
Figures
Reference graph
Works this paper leans on
-
[13]
Differentially private and decentralized randomized power method
J. Nicolas, C. Sabater, M. Maouche, S. B. Mokhtar, and M. Coates, “Differentially private and decentralized randomized power method,” arXiv preprint arXiv:2411.01931, 2024
work page Pith review arXiv 2024
-
[1]
The decentralized estimation of the sample covariance,
A. Scaglione, R. Pagliari, and H. Krim, “The decentralized estimation of the sample covariance,” in2008 42nd Asilomar Conference on Signals, Systems and Computers. IEEE, 2008, pp. 1722–1726
work page 2008
-
[2]
Incremental aggregated rieman- nian gradient method for distributed pca,
X. Wang, Y . Jiao, H.-T. Wai, and Y . Gu, “Incremental aggregated rieman- nian gradient method for distributed pca,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2023, pp. 7492–7510
work page 2023
-
[3]
Practical lossless federated singular vector decomposition over billion- scale data,
D. Chai, L. Wang, J. Zhang, L. Yang, S. Cai, K. Chen, and Q. Yang, “Practical lossless federated singular vector decomposition over billion- scale data,” inProceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, 2022, pp. 46–55
work page 2022
-
[4]
Scalable and privacy-preserving federated principal component analysis,
D. Froelicher, H. Cho, M. Edupalli, J. S. Sousa, J.-P. Bossuat, A. Pyrge- lis, J. R. Troncoso-Pastoriza, B. Berger, and J.-P. Hubaux, “Scalable and privacy-preserving federated principal component analysis,” in2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023, pp. 1908– 1925
work page 2023
-
[5]
Fed- erated principal component analysis,
A. Grammenos, R. Mendoza Smith, J. Crowcroft, and C. Mascolo, “Fed- erated principal component analysis,”Advances in neural information processing systems, vol. 33, pp. 6453–6464, 2020
work page 2020
-
[6]
Principal component analysis for dimension reduction in massive distributed data sets,
Y . Qu, G. Ostrouchov, N. Samatova, and A. Geist, “Principal component analysis for dimension reduction in massive distributed data sets,” in Proceedings of IEEE International Conference on Data Mining (ICDM), vol. 1318, no. 1784, 2002, p. 1788
work page 2002
-
[7]
Im- proved distributed principal component analysis,
Y . Liang, M.-F. F. Balcan, V . Kanchanapally, and D. Woodruff, “Im- proved distributed principal component analysis,” inAdvances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, Eds., vol. 27. Curran Associates, Inc., 2014
work page 2014
Show all 30 references
-
[8]
Membership inference attack against principal component analysis,
O. Zari, J. Parra-Arnau, A. ¨Unsal, T. Strufe, and M. ¨Onen, “Membership inference attack against principal component analysis,” inInternational Conference on Privacy in Statistical Databases. Springer, 2022, pp. 269–282
2022
-
[9]
Differentially private principal component analysis over horizontally partitioned data,
S. Wang and J. M. Chang, “Differentially private principal component analysis over horizontally partitioned data,” in2018 IEEE Conference on Dependable and Secure Computing (DSC). IEEE, 2018, pp. 1–8
2018
-
[10]
Privacy-preserving source separation for distributed data using indepen- dent component analysis,
H. Imtiaz, R. Silva, B. Baker, S. M. Plis, A. D. Sarwate, and V . Calhoun, “Privacy-preserving source separation for distributed data using indepen- dent component analysis,” in2016 Annual Conference on Information Science and Systems (CISS). IEEE, 2016, pp. 123–127
2016
-
[11]
Minimax-optimal privacy- preserving sparse pca in distributed systems,
J. Ge, Z. Wang, M. Wang, and H. Liu, “Minimax-optimal privacy- preserving sparse pca in distributed systems,” inInternational Confer- ence on Artificial Intelligence and Statistics. PMLR, 2018, pp. 1589– 1598
2018
-
[12]
Principal component analysis in the local dif- ferential privacy model,
D. Wang and J. Xu, “Principal component analysis in the local dif- ferential privacy model,”Theoretical computer science, vol. 809, pp. 296–312, 2020
2020
-
[14]
An improved gap-dependency analysis of the noisy power method,
M.-F. Balcan, S. S. Du, Y . Wang, and A. W. Yu, “An improved gap-dependency analysis of the noisy power method,” in29th Annual Conference on Learning Theory, ser. Proceedings of Machine Learning Research, V . Feldman, A. Rakhlin, and O. Shamir, Eds., vol. 49. PMLR, 23–26 Jun 2...
2016
-
[15]
Fedpower: Privacy-preserving distributed eigenspace estimation,
X. Guo, X. Li, X. Chang, S. Wang, and Z. Zhang, “Fedpower: Privacy-preserving distributed eigenspace estimation,”arXiv preprint arXiv:2103.00704, 2021
2021 arXiv
-
[16]
Relaxations of differential privacy and risk/utility evalua- tions of synthetic data and fidelity measures,
D. McClure, “Relaxations of differential privacy and risk/utility evalua- tions of synthetic data and fidelity measures,” Ph.D. dissertation, Duke University, 2015
2015
-
[17]
The algorithmic foundations of differential privacy,
C. Dwork, A. Rothet al., “The algorithmic foundations of differential privacy,”Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014
2014
-
[18]
Privacy: Theory meets practice on the map,
A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber, “Privacy: Theory meets practice on the map,” in2008 IEEE 24th international conference on data engineering. IEEE, 2008, pp. 277– 286
2008
-
[19]
Our data, ourselves: Privacy via distributed noise generation,
C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” inAdvances in Cryptology-EUROCRYPT 2006: 24th Annual International Confer- ence on the Theory and Applications of Cryptographic Techniques, St. Peter...
2006
-
[20]
The noisy power method: A meta algorithm with applications,
M. Hardt and E. Price, “The noisy power method: A meta algorithm with applications,”Advances in neural information processing systems, vol. 27, 2014
2014
-
[21]
Differentially private clustering in high-dimensional euclidean spaces,
M.-F. Balcan, T. Dick, Y . Liang, W. Mou, and H. Zhang, “Differentially private clustering in high-dimensional euclidean spaces,” inInternational Conference on Machine Learning. PMLR, 2017, pp. 322–331
2017
-
[22]
Concentrated differential privacy: Simpli- fications, extensions, and lower bounds,
M. Bun and T. Steinke, “Concentrated differential privacy: Simpli- fications, extensions, and lower bounds,” inTheory of cryptography conference. Springer, 2016, pp. 635–658
2016
-
[23]
Vershynin,High-Dimensional Probability: An Introduction with Ap- plications in Data Science, ser
R. Vershynin,High-Dimensional Probability: An Introduction with Ap- plications in Data Science, ser. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
2018
-
[24]
Matrix computations third ed,
G. H. Golub and C. F. Van Loan, “Matrix computations third ed,” JohnHopkinsUniversityPress, Baltimor, 1996
1996
-
[25]
On r ´enyi divergence measures for continuous alphabet sources,
M. Gil, “On r ´enyi divergence measures for continuous alphabet sources,” PhD Thesis, 2011
2011
-
[26]
The rotation of eigenvectors by a perturbation. iii,
C. Davis and W. M. Kahan, “The rotation of eigenvectors by a perturbation. iii,”SIAM Journal on Numerical Analysis, vol. 7, no. 1, pp. 1–46, 1970
1970
-
[27]
Adaptive estimation of a quadratic functional by model selection,
B. Laurent and P. Massart, “Adaptive estimation of a quadratic functional by model selection,”Annals of statistics, pp. 1302–1338, 2000
2000
-
[28]
Least angle regression,
B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, “Least angle regression,” 2004
2004
-
[29]
Breast Cancer Wisconsin (Diagnostic),
W. Wolberg, O. Mangasarian, N. Street, and W. Street, “Breast Cancer Wisconsin (Diagnostic),” UCI Machine Learning Repository, 1993, DOI: https://doi.org/10.24432/C5DW2B
1993 doi
-
[30]
Aeberhard and M
S. Aeberhard and M. Forina, “Wine,” UCI Machine Learning Repository, 1992, DOI: https://doi.org/10.24432/C5PC7J
1992 doi
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.