Smooth Sensitivity Based Approach for Differentially Private PCA

Alon Gonem, Ram Gilad-Bachrach
Proceedings of Algorithmic Learning Theory, PMLR 83:438-450, 2018.

Abstract

We consider the challenge of differentially private PCA. Currently known methods for this task either employ the computationally intensive 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 Kapralov et al. 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 global sensitivity associated with publishing the leading eigenvector. We tackle this issue by adopting a 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-gonem18a, title = {Smooth Sensitivity Based Approach for Differentially Private PCA}, author = {Gonem, Alon and Gilad-Bachrach, Ram}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {438--450}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/gonem18a/gonem18a.pdf}, url = {https://proceedings.mlr.press/v83/gonem18a.html}, abstract = {We consider the challenge of differentially private PCA. Currently known methods for this task either employ the computationally intensive 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 Kapralov et al. 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 global sensitivity associated with publishing the leading eigenvector. We tackle this issue by adopting a 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.} }
Endnote
%0 Conference Paper %T Smooth Sensitivity Based Approach for Differentially Private PCA %A Alon Gonem %A Ram Gilad-Bachrach %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-gonem18a %I PMLR %P 438--450 %U https://proceedings.mlr.press/v83/gonem18a.html %V 83 %X We consider the challenge of differentially private PCA. Currently known methods for this task either employ the computationally intensive 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 Kapralov et al. 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 global sensitivity associated with publishing the leading eigenvector. We tackle this issue by adopting a 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.
APA
Gonem, A. & Gilad-Bachrach, R.. (2018). Smooth Sensitivity Based Approach for Differentially Private PCA. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:438-450 Available from https://proceedings.mlr.press/v83/gonem18a.html.

Related Material