Differentially Private Covariance Revisited
In this paper, we present two new algorithms for covariance estimation under concentrated differential privacy (zCDP). The first algorithm achieves a Frobenius error of $\tilde{O}(d^{1/4}\sqrt{\mathrm{tr}}/\sqrt{n} + \sqrt{d}/n)$, where $\mathrm{tr}$ is the trace of the covariance matrix. By taking $\mathrm{tr}=1$, this also implies a worst-case error bound of $\tilde{O}(d^{1/4}/\sqrt{n})$, which improves the standard Gaussian mechanism's $\tilde{O}(d/n)$ for the regime $d>\widetilde{\Omega}(n^{2/3})$. Our second algorithm offers a tail-sensitive bound that could be much better on skewed data. The corresponding algorithms are also simple and efficient. Experimental results show that they offer significant improvements over prior work.
Code (2)
Similar Papers 제목 키워드 기반
Differentially Private Matrix Completion Revisited
We provide the first provably joint differentially private algorithm with formal utility guarantees for the problem of user-level privacy-preserving collaborative filtering. Our algorithm is based on the Frank-Wolfe meth…
Collaborative FilteringMatrix CompletionPrivacy PreservingDifferentially Private Precision Matrix Estimation
In this paper, we study the problem of precision matrix estimation when the dataset contains sensitive information. In the differential privacy framework, we develop a differentially private ridge estimator by perturbing…
Differentially Private Covariance Estimation
The covariance matrix of a dataset is a fundamental statistic that can be used for calculating optimum regression weights as well as in many other learning and data analysis settings. For datasets containing private user…
Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
We present two sample-efficient differentially private mean estimators for $d$-dimensional (sub)Gaussian distributions with unknown covariance. Informally, given $n \gtrsim d/\alpha^2$ samples from such a distribution wi…
Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices
Estimating a covariance matrix and its associated principal components is a fundamental problem in contemporary statistics. While optimal estimation procedures have been developed with well-understood properties, the inc…
valid