Timezone: »

 
Poster
DP-PCA: Statistically Optimal and Differentially Private PCA
Xiyang Liu · Weihao Kong · Prateek Jain · Sewoong Oh

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #538
in Poster Session 5 »
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: ($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 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 $n=O(d \log d)$.
Keywords: differential privacy · principal component analysis · private estimation

Author Information

Xiyang Liu (University of Washington)
Weihao Kong (Google Research)
Prateek Jain (Google Research)
Sewoong Oh (University of Washington)

More from the Same Authors