Abstract
In this paper, we study the sparse covariance matrix estimation problem in the local differential privacy model, and give a lower bound of Ω([Formula presented]) on the ϵ non-interactive private minimax risk in the metric of squared spectral norm, where s is the row sparsity of the underlying covariance matrix, n is the sample size, and p is the dimensionality of the data. 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.
Original language | English (US) |
---|---|
Pages (from-to) | 47-59 |
Number of pages | 13 |
Journal | Theoretical Computer Science |
Volume | 815 |
DOIs | |
State | Published - May 2 2020 |
Externally published | Yes |
Bibliographical note
Generated from Scopus record by KAUST IRTS on 2022-09-15ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science