DP-PCA: Statistically Optimal and Differentially Private PCA
We study the canonical statistical task of computing the principal component
from $n$ i.i.d.~data in $d$ dimensions under
$(\varepsilon,\delta)$-differential privacy. Although extensively studied in
literature, existing solutions fall short on two key aspects: ($i$) even for
Gaussian data, existing private algorithms require the number of samples $n$ to
scale super-linearly with $d$, i.e., $n=\Omega(d^{3/2})$, to obtain non-trivial
results while non-private PCA requires only $n=O(d)$, and ($ii$) existing
techniques suffer from a non-vanishing error even when the randomness in each
data point is arbitrarily small. We propose DP-PCA, which is a single-pass
algorithm that overcomes both limitations. It is based on a private minibatch
gradient ascent method that relies on {\em private mean estimation}, which adds
minimal noise required to ensure privacy by adapting to the variance of a given
minibatch of gradients. For sub-Gaussian data, we provide nearly optimal
statistical error rates even for $n=\tilde O(d)$. Furthermore, we provide a
lower bound showing that sub-Gaussian style assumption is necessary in
obtaining the optimal error rate.