Lower Bound of Locally Differentially Private Sparse Covariance Matrix Estimation
Abstract
In this paper, we study the sparse covariance matrix estimation problem in the local differential privacy model, and give a non-trivial lower bound on the non-interactive private minimax risk in the metric of squared spectral norm. We show that the lower bound is actually tight, as it matches a previous upper bound. Our main technique for achieving this lower bound is a general framework, called General Private Assouad Lemma, which is a considerable generalization of the previous private Assouad lemma and can be used as a general method for bounding the private minimax risk of matrix-related estimation problems.
Cite
Text
Wang and Xu. "Lower Bound of Locally Differentially Private Sparse Covariance Matrix Estimation." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/665Markdown
[Wang and Xu. "Lower Bound of Locally Differentially Private Sparse Covariance Matrix Estimation." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/wang2019ijcai-lower/) doi:10.24963/IJCAI.2019/665BibTeX
@inproceedings{wang2019ijcai-lower,
title = {{Lower Bound of Locally Differentially Private Sparse Covariance Matrix Estimation}},
author = {Wang, Di and Xu, Jinhui},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2019},
pages = {4788-4794},
doi = {10.24963/IJCAI.2019/665},
url = {https://mlanthology.org/ijcai/2019/wang2019ijcai-lower/}
}