An Iterative Algorithm for Differentially Private $k$ -PCA with Adaptive Noise

Given

n

i.i.d.random matrices

A_{i} \in R^{d \times d}

that share common expectation

Σ

, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension

k

that captures the largest variance directions of

Σ

, while preserving differential privacy (DP) of each individual

A_{i}

Existing methods either

require the sample size $n$ to scale super-linearly with dimension $d$ , even under Gaussian assumptions on the $A_{i}$ , or
introduce excessive noise for DP even when the intrinsic randomness within $A_{i}$ is small. \citet{liu2022dp} addressed these issues for sub-Gaussian data but only for estimating the top eigenvector ( $k = 1$ ) using their algorithm DP-PCA.

We propose the first algorithm capable of estimating the top

k

eigenvectors for arbitrary

k \leq d

, whilst overcoming both limitations above.

For

k = 1

, our algorithm matches the utility guarantees of DP-PCA, achieving near-optimal statistical error even when

n = \tilde{O} (d)

. We further provide a lower bound for general

k > 1

, matching our upper bound up to a factor of

k

, and experimentally demonstrate the advantages of our algorithm over comparable baselines.