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