Poster
DP-PCA: Statistically Optimal and Differentially Private PCA
Xiyang Liu · Weihao Kong · Prateek Jain · Sewoong Oh
Hall J (level 1) #538
Keywords: [ private estimation ] [ differential privacy ] [ principal component analysis ]
Abstract:
We study the canonical statistical task of computing the principal component from i.i.d.~data under differential privacy. Although extensively studied in literature, existing solutions fall short on two key aspects: () even for Gaussian data, existing private algorithms require the number of samples to scale super-linearly with , i.e., , to obtain non-trivial results while non-private PCA requires only , and () existing techniques suffer from a large error even when the variance in each data point is small. We propose DP-PCA method that uses a single-pass minibatch gradient descent style algorithm to overcome the above limitations. For sub-Gaussian data, we provide nearly optimal statistical error rates even for .
Chat is not available.