A Framework for Private Matrix Analysis in Sliding Window Model
Jalaj Upadhyay, Sarvagya Upadhyay
Abstract
We perform a rigorous study of private matrix analysis when only the last $W$ updates to matrices are considered useful for analysis. We show the existing framework in the non-private setting is not robust to noise required for privacy. We then propose a framework robust to noise and use it to give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis (PCA), multi-response linear regression, sparse PCA, and non-negative PCA. Prior to our work, no such result was known for sparse and non-negative differentially private PCA even in the static data setting. We also give a lower bound to demonstrate the cost of privacy in the sliding window model.
BibTeX
@InProceedings{pmlr-v139-upadhyay21a,
title = {A Framework for Private Matrix Analysis in Sliding Window Model},
author = {Upadhyay, Jalaj and Upadhyay, Sarvagya},
booktitle = {Proceedings of the 38th International Conference on Machine Learning},
pages = {10465--10475},
year = {2021},
editor = {Meila, Marina and Zhang, Tong},
volume = {139},
series = {Proceedings of Machine Learning Research},
month = {18--24 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v139/upadhyay21a/upadhyay21a.pdf},
url = {https://proceedings.mlr.press/v139/upadhyay21a.html},
abstract = {We perform a rigorous study of private matrix analysis when only the last $W$ updates to matrices are considered useful for analysis. We show the existing framework in the non-private setting is not robust to noise required for privacy. We then propose a framework robust to noise and use it to give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis (PCA), multi-response linear regression, sparse PCA, and non-negative PCA. Prior to our work, no such result was known for sparse and non-negative differentially private PCA even in the static data setting. We also give a lower bound to demonstrate the cost of privacy in the sliding window model.}
}