Differentially Private Covariance Revisited
This work addresses privacy-preserving data analysis for statisticians and machine learning practitioners, offering incremental algorithmic improvements in differential privacy.
The paper tackles covariance estimation under concentrated differential privacy by introducing two new algorithms, with the first achieving a Frobenius error of $ ilde{O}(d^{1/4}\sqrt{\mathrm{tr}}/\sqrt{n} + \sqrt{d}/n)$ and improving worst-case bounds over the Gaussian mechanism for high-dimensional regimes, while the second provides tail-sensitive bounds for skewed data, with experiments showing significant improvements over prior work.
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Ω(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.