Private, Outlier-Robust PCA Over Peer-to-Peer Networks Without a Trusted Server

Principal component analysis (PCA), the standard way to find the few directions that explain most of a dataset's variation, measures fit with squared errors. Because errors are squared, one corrupted record can swing the recovered directions arbitrarily far. That fragility turns out to be the same obstacle faced by differential privacy (DP), the formal guarantee that the output barely changes when one person's record changes. If one record can move the answer a lot, then a lot of noise is needed to hide it. Differential privacy and robust statistics in high dimensions makes this connection precise through "resilience." Its algorithm, however, takes exponential time, and it assumes one curator who holds all the raw data. Many settings have no such curator: hospitals, sensor operators, and grid utilities each hold a data silo and are linked only to a few peers. Trusting a server in that setting is risky. Beyond Inferring Class Representatives shows that a curious aggregator can reconstruct individual clients' training samples from the updates they send.

We propose a decentralized PCA algorithm in which each node's outgoing message is built from a robust, subspace-aware reweighting of its own records, and each node adds DP noise to that message exactly once per iteration. Two properties follow. The reweighting both removes outliers that tilt the subspace and caps any single record's influence, so the same step provides robustness and bounded DP sensitivity. And because the network combines messages with a tracking recursion whose average telescopes, the injected noise does not pile up across iterations. That preserves the linear convergence rate of DeEPCA, and a fast rate means fewer noisy rounds, which means less privacy budget is spent.

Core Claim

The claim is that a node-local, residual-aware weighting inside a decentralized power iteration, with noise applied only to each node's local matrix product, yields three things together. First, sample-level $(\epsilon,\delta)$-DP holds against any coalition of other nodes, with no server, shuffler, or pair of non-colluding servers. Second, the method stays robust to a constant fraction of records that are corrupted off the subspace. Third, it converges linearly to a neighborhood whose radius is set by the current iteration's noise divided by the number of nodes, and that error does not accumulate over rounds.

The closest existing systems each deliver only part of this. DPS-PCA is private and distributed, but it needs a central coordinator and uses squared-loss covariance products, so it has no outlier protection. DeEPCA is fully decentralized and linearly convergent, but it sends raw iterates and uses a squared-loss objective. PRECAD combines clipping-based robustness with DP, but only by assuming two servers that never collude, and it targets smooth neural-network training rather than subspaces.

Research Program

The local message. Node $i$ holds records $x_{ij} \in \mathbb{R}^d$ and receives the current estimate $Q \in \mathbb{R}^{d\times k}$, a matrix with orthonormal columns spanning a $k$-dimensional subspace. It computes a weighted local product and then adds noise:

$$\tilde G_i = \sum_j w_{ij}\, x_{ij}\,(Q^\top x_{ij})^\top + Z_i, \qquad w_{ij} = \min\!\Big(1, \frac{\tau}{\|x_{ij} - QQ^\top x_{ij}\|}\Big)\cdot \min\!\Big(1, \frac{c}{\|x_{ij}\|\,\|Q^\top x_{ij}\|}\Big),$$

The symbols are as follows. $Z_i$ is Gaussian noise with a $d\times k$ entry for each coordinate. $\tau$ is a threshold on each record's residual, meaning its distance from the current subspace. $c$ bounds any one record's contribution to the product, and so bounds the DP sensitivity.

The first factor is an $L_{2,1}$/Huber-style reweighting in the spirit of Non-Greedy L21-Norm Maximization for PCA, which maximizes a norm that grows more slowly than squares for the same reason. Records far from the subspace are down-weighted by their residual, not by their raw size. The second factor is ordinary norm clipping. It can be set loosely, because the dangerous off-subspace records have already been shrunk by the first factor.

The network recursion. Nodes run DeEPCA's subspace tracking, a fixed number of local averaging rounds with neighbors, followed by its sign-alignment step. The input is the noisy $\tilde G_i$ rather than the exact local product. Each node then touches its data only through $\tilde G_i$, so everything it transmits is post-processing of $T$ Gaussian mechanisms. Privacy then follows from standard composition accounting, as in DP-ADMM.

Tracking keeps the invariant that the network average of the tracking variable equals the average of the current $\tilde G_i^{(t)}$. Noise from earlier rounds therefore cancels in the mean instead of compounding. This is the subspace analogue of the "exploding dual variable" failure that DP-Norm had to fix with an added regularizer, and here it is avoided by construction. Deviations of individual nodes from that average still carry noise, and the analysis must bound them.

Analysis. We will prove a per-iteration contraction of the principal-angle distance to the clean subspace, under a model with a corruption fraction $\eta$ and sub-Gaussian inliers. The perturbation term will be split into three parts: residual outlier leakage bounded by $\tau$, weighting bias on inliers, and noise of order $c\sqrt{T\log(1/\delta)}/(\epsilon N m)$. Here $N$ is the number of nodes and $m$ the silo size. The $\sqrt{T}$ comes from Gaussian composition and the $1/(Nm)$ from averaging. Because $T$ grows only like $\log(1/\text{accuracy})$ under a linear rate, the privacy cost is logarithmic in the target precision. Sublinear private schemes pay polynomially.

The weights depend on $Q$, so the weighted objective is nonconvex. Like PCA-$L_{2,1}$, we expect guarantees only near a good starting point. We will start from a noisy one-shot sketch, and we will measure how often initialization fails, since DPS-PCA reports that its analogous method is sensitive to the starting estimate.

Baselines

Do-nothing reference. The naive reference is noiseless DeEPCA on corrupted data. It shows how much outliers hurt with no privacy at all. Noiseless DeEPCA on clean data gives the accuracy ceiling. DeEPCA reports exact convergence on w8a and a9a with $K=5$ averaging rounds over random graphs with 50% link probability. It gives no numeric subspace error in the file, so we will reproduce that configuration and use it as the shared topology for every method.

Strongest existing private competitor. This is DPS-PCA, run with its coordinator replaced by the same peer-to-peer averaging so the topology matches, and also in its native star form as a stronger, more-trusting reference. No reported result found on Lacuna for DPS-PCA on the LIBSVM or occlusion benchmarks, or under outliers. We will tune it with the same budget of noise calibration and clipping grid points as our method, at matched $(\epsilon,\delta)$. Beating it means lower principal-angle error to the clean subspace at equal privacy once the corruption fraction exceeds a few percent, while roughly matching it on clean data.

Robust non-private reference. This is centralized PAMe for $L_1$-PCA from Linear Convergence of PAMe, which reports clustering accuracy 0.5808 and 14.95 s on real-sim. It shows what robustness costs when there is full trust and no privacy.

Ablation. The key ablation keeps everything identical but drops the residual factor from $w_{ij}$, leaving norm clipping only, tuned over the same grid. This isolates whether the subspace-aware weight, rather than clipping, provides the robustness.

Why not just…?

Why not just add noise to each node's covariance once, then run noiseless decentralized PCA? This is input perturbation, whose summed local noise Differentially Private ERM with Input Perturbation shows can match central objective perturbation. It is the most serious threat, because it has no composition cost. It has two limits. The noise is $d\times d$ rather than $d\times k$, which is prohibitive on news20 with 62,061 dimensions and dominates whenever $d/k$ exceeds the number of iterations. It also cannot use weights that depend on the evolving subspace, so it is robust only if a node can clean its data before seeing the global subspace. We will run it with local clipping, and on smaller $d$ it may win on clean data. The decisive check is the crossover in $d/k$ and in corruption fraction.

Why not just clip norms in a private DeEPCA? Norm clipping bounds sensitivity but keeps squared-loss geometry. A large off-subspace outlier is shrunk, yet it still points in the wrong direction. At the thresholds DP requires, clipping also shrinks legitimate high-variance records along the signal. This is plausible but unproven in the file, and the norm-clipping ablation above settles it directly. If that ablation matches the full method, we will report that the residual weight is unnecessary.

Why not just have each node filter its own outliers locally, or use cryptographic aggregation? Local filtering relies on a subspace estimated from one silo, which is poor when silos are small. We will vary the silo size $m$ to find where it breaks. Cryptographic aggregation removes neither the collusion assumption nor the output leakage. PRECAD needs two non-colluding servers and runs about 7x slower than plain local perturbation, and exact released subspaces carry no DP guarantee.

Proposed Experiments

Data. We will use four sources. The first is the synthetic Laplace-noise designs from PAMe, sizes $(4000, 2000)$ and $(2000, 4000)$, with planted subspaces. The second is LIBSVM w8a, a9a, real-sim, and news20. The third is occluded Yale and AR face images from the PCA-$L_{2,1}$ evaluation. The fourth is Wallflower background subtraction, where coherent "spiky" corruption is known to drive the success rate of convex robust PCA to 0% (Random Consensus Robust PCA).

Setup. Records are split across 20–100 nodes, with corruption spread across nodes or concentrated in a few nodes. Topologies are random graphs, rings, and graphs with dropped links.

Metrics. We measure principal-angle distance to the clean subspace, variance explained on held-out clean data, clustering accuracy on real-sim, reconstruction error on occluded faces, and communication rounds, all across $\epsilon \in [0.5, 8]$ and corruption fractions from 0 to 20%.

Decisive checks. Three results would support the claim. The error of the full method should level off as iterations increase, while an ablation that adds noise directly into the tracking state should drift upward. The full method should beat norm-clipping-only and DPS-PCA once corruption is nonzero. And the crossover against one-shot covariance perturbation should appear where the analysis predicts in $d/k$. If one-shot perturbation with local cleaning wins across the board, the iterative design is not justified, and we would report that result.