Name
Title | ||
|---|---|---|
Smooth Sensitivity Based Approach for Differentially Private Principal Component Analysis. |
Abstract | ||
|---|---|---|
Currently known methods for this task either employ the computationally intensive emph{exponential mechanism} or require an access to the covariance matrix, and therefore fail to utilize potential sparsity of the data. The problem of designing simpler and more efficient methods for this task has been raised as an open problem in cite{kapralov2013differentially}. In this paper we address this problem by employing the output perturbation mechanism. Despite being arguably the simplest and most straightforward technique, it has been overlooked due to the large emph{global sensitivity} associated with publishing the leading eigenvector. We tackle this issue by adopting a emph{smooth sensitivity} based approach, which allows us to establish differential privacy (in a worst-case manner) and near-optimal sample complexity results under eigengap assumption. We consider both the pure and the approximate notions of differential privacy, and demonstrate a tradeoff between privacy level and sample complexity. We conclude by suggesting how our results can be extended to related problems. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Learning | Mathematical optimization,Open problem,Exponential function,Differential privacy,Eigengap,Covariance matrix,Eigenvalues and eigenvectors,Mathematics,Principal component analysis,Perturbation (astronomy) |
DocType | Volume | Citations |
Journal | abs/1710.10556 | 0 |
PageRank | References | Authors |
0.34 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alon Gonen | 1 | 104 | 9.76 |
| Ran Gilad-Bachrach | 2 | 10 | 1.89 |