Differentially Private Covariance Revisited

2022/05/28 by Dong, Wei, Liang, Yuting, Yi, Ke · 4 citations
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2205.14324

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/4√(tr)/√(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>\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.

Cited by

• Black-Box Differentially Private Nonparametric Confidence Intervals Under Minimal Assumptions
• On Purely Private Covariance Estimation
• Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond
• High-Dimensional Differentially Private Quantile Regression: Distributed Estimation and Statistical Inference

Related

• On Purely Private Covariance Estimation
• Differentially Private High Dimensional Sparse Covariance Matrix Estimation
• Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
• New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation