# Differentially Private Covariance Revisited

arXiv: https://arxiv.org/abs/2205.14324 · HTML: https://mlsanity.com/paper/2205.14324/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 28 May 2022.

## Builds on (most cited first, 16 of 16)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations](https://mlsanity.com/paper/1308.1385/) (2013)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Universal Private Estimators](https://mlsanity.com/paper/2111.02598/) (2021)

## Built on by (most cited first, 15 of 15)

- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices](https://mlsanity.com/paper/2401.03820/) (2024)
- [Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes](https://mlsanity.com/paper/2404.17714/) (2024)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation](https://mlsanity.com/paper/2301.13850/) (2023)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [High-Dimensional Differentially Private Quantile Regression: Distributed Estimation and Statistical Inference](https://mlsanity.com/paper/2508.05212/) (2025)
- [Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond](https://mlsanity.com/paper/2509.04919/) (2025)
- [On Purely Private Covariance Estimation](https://mlsanity.com/paper/2510.26717/) (2025)
- [Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions](https://mlsanity.com/paper/2511.01303/) (2025)
- [Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy](https://mlsanity.com/paper/2603.19703/) (2026)
- [A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input](https://mlsanity.com/paper/2505.14251/) (2025)
- [Private Adaptive Covariance Estimation via Gaussian Graphical Models](https://mlsanity.com/paper/2605.24295/) (2026)
- [Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests](https://mlsanity.com/paper/2609.22783/) (2026)

## Abstract (arXiv)

In this paper, we present two new algorithms for covariance estimation under concentrated differential privacy (zCDP). The first algorithm achieves a Frobenius error of tildeO(d1/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 tildeO(d1/4/√n), which improves the standard Gaussian mechanism's tildeO(d/n) for the regime d>widetildeOmega(n2/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.