Differentially Private Covariance Estimation

The task of privately estimating a covariance matrix is a popular one due to its applications to regression and PCA. While there are known methods for releasing private covariance matrices, these algorithms either achive only (,)-differential privacy or require very complicated sampling schemes, ultimately performing poorly in real data. In this work we propose a new -differentially private algorithm for computing the covariance matrix of a dataset that addresses both of these limitations. We show that it has lower error than existing state-of-the-art approaches, both analytically and empirically. In addition, the algorithm is significantly less complicated than other methods and can be efficiently implemented with rejection sampling.