mlsanityData to 14 Oct 2026

Differentially Private Covariance Revisited

arXiv 2205.14324 ↗First posted 28 May 2022cs.CR cs.DS cs.LGcited by 15

Not on the map. Why?

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.

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

16 of 40 references.

References · 16

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  2. 2019Differentially Private Learning with Adaptive Clippingcited by 220
  3. 2018Privately Learning High-Dimensional Distributionscited by 104
  4. 2019AdaCliP: Adaptive Clipping for Private SGDcited by 77
  5. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  6. 2021Differential privacy and robust statistics in high dimensionscited by 64
  7. 2019Private Hypothesis Selectioncited by 60
  8. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  9. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  10. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  11. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  12. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
4 more
  1. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  2. 2013Efficient Algorithms for Privately Releasing Marginals via Convex Relaxationscited by 17
  3. 2021Privately Learning Subspacescited by 16
  4. 2021Universal Private Estimatorscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 3; 2025: 5; 2026: 3.

15 papers.

Sort:

  1. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
  2. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 11
  3. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  4. 2022Private Query Release via the Johnson-Lindenstrauss Transformcited by 8
  5. 2023Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasetscited by 4
  6. 2023General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimationcited by 3
  7. 2024Perturb-and-Project: Differentially Private Similarities and Marginalscited by 1
  8. 2025High-Dimensional Differentially Private Quantile Regression: Distributed Estimation and Statistical Inferencecited by 1
  9. 2025Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyondcited by 1
  10. 2025On Purely Private Covariance Estimationcited by 1
  11. 2025Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptionscited by 1
  12. 2026Minimax and Adaptive Covariance Matrix Estimation under Differential Privacycited by 1
3 more
  1. 2025A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Inputcited by 0
  2. 2026Private Adaptive Covariance Estimation via Gaussian Graphical Modelscited by 0
  3. 2026Improved Private Sparse Covariance Estimation with Multiscale Threshold Testscited by 0