Differentially Private Covariance Revisited

Code

• github.com/hkustdb/privatecovariance
  OfficialIn paperpytorch★ 1
• github.com/opencode2022/privatecovariance
  OfficialIn paperpytorch★ 0

Abstract

In this paper, we present two new algorithms for covariance estimation under concentrated differential privacy (zCDP). The first algorithm achieves a Frobenius error of O(d^1/4tr/n + d/n), where tr is the trace of the covariance matrix. By taking tr=1, this also implies a worst-case error bound of O(d^1/4/n), which improves the standard Gaussian mechanism's O(d/n) for the regime d>(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.

Reproductions