Adaptive Power Iteration Method for Differentially Private PCA
Organizations: Department of Computer Science, Boston University · Khoury College of Computer and Information Science, Northeastern University
Abstract
We study -differentially private algorithms for the problem of approximately computing the top singular vector of a matrix where each row of is a data point in . Following Dwork-Talwar-Thakurta-Zhang (STOC 2014), we consider the privacy model where neighboring inputs differ by one single row. We give a novel algorithm that achieves beyond-worst-case guarantees for input matrices with low coherence, which is a structural property of matrices in many applications, including but not limited to i.i.d. data. Our algorithm contributes to the extensive literature on private power iteration methods, where we introduce a new filtering technique which adapts to this coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which achieves beyond-worst-case guarantees for the more restrictive privacy model where neighboring inputs differ in one single entry by at most 1.
Figures & tables
| Algorithm | -Error | Condition | |
|---|---|---|---|
| Deterministic data | [ 20 , 18 ] (Entry private 1 1 1 This result is presented in Theorem 1.3 in [ 12 ] . ) | ||
| [ 20 , 18 ] + Composition | |||
| [ 12 ] 2 2 2 [ 20 , 18 , 12 ] use a different symmetrization \Big(\begin{array}[]{cc}0&A\\ A^{\top}&0\end{array}\Big) . These results are for approximating a vector in the span of where is the top left and is the top right singular vectors of . When using , we can compute the bound by [ 12 ] as , matching the bound of [ 17 ] . | |||
| [ 17 ] | |||
| Our algorithm (Cor. 1.1 ) | |||
| Gaussian i.i.d. data | [ 26 ] Algorithm 2 |
Principal Component Analysis
Principal component analysis (PCA) finds orthogonal directions of greatest variance for data compression, visualization, denoising, and feature discovery.
See all 72 papers