Optimal Rates for Adaptive Private $k$-PCA

Given $n$ i.i.d. random matrices $A_i\in {\mathbb{R}}^{d\times d}$ with common expectation $\Sigma$, the goal of Differentially Private Stochastic PCA is to identify a $k$-dimensional subspace capturing the leading variance directions of $\Sigma$, while preserving differential privacy (DP) for each individual sample $A_i$. Düngler & Sanyal [2025] introduced $k$-DP-PCA, the first algorithm to simultaneously (1) achieve sample complexity $n=\tilde{O}(d)$ for sub-Gaussian data, (2) adapt its privacy noise to the intrinsic randomness of the data, and (3) extend seamlessly to any target dimension $k\le d$. However, its sample complexity has a suboptimal dependence on $k$. We propose the first algorithm that achieves optimal sample complexity in both $d$ and $k$, while retaining (2) and (3) of $k$-DP-PCA. In addition, our method removes the exponential dependence on the eigengap that appears in the sample-size lower bound required by prior utility guarantees, and improves the dependence on spectral parameters to match known lower bounds for the spiked covariance model. Unlike deflation-based approaches like $k$-DP-PCA, our algorithm updates the full $d\times k$ subspace jointly rather than one eigenvector at a time. This non-deflation structure simplifies the algorithm, reduces the number of hyper-parameters, and improves computational efficiency, particularly when using block linear algebra libraries.