mlsanityData to 14 Oct 2026

Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes

arXiv 2404.17714 ↗First posted 26 Apr 2024cs.DS cs.CR cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We prove lower bounds on the number of samples needed to privately estimate the covariance matrix of a Gaussian distribution. Our bounds match existing upper bounds in the widest known setting of parameters. Our analysis relies on the Stein-Haff identity, an extension of the classical Stein's identity used in previous fingerprinting lemma arguments.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 22 of its 43 references that are in the map. First posted on arXiv 26 Apr 2024.

Builds on

22 of 43 references.

References · 22

  1. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  2. 2018Privately Learning High-Dimensional Distributionscited by 104
  3. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  4. 2021Differential privacy and robust statistics in high dimensionscited by 64
  5. 2019Private Hypothesis Selectioncited by 60
  6. 2015Between Pure and Approximate Differential Privacycited by 56
  7. 2020Differentially Private Assouad, Fano, and Le Camcited by 55
  8. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  9. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  10. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  11. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  12. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
10 more
  1. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  2. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  3. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  4. 2016Make Up Your Mind: The Price of Online Queries in Differential Privacycited by 26
  5. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  6. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  7. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
  8. 2022Differentially Private Covariance Revisitedcited by 15
  9. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  10. 2020Multivariate Gaussian Variational Inference by Natural Gradient Descentcited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

9 papers.

  1. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
  2. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  3. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  4. 2025Private Statistical Estimation via Truncationcited by 1
  5. 2025Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyondcited by 1
  6. 2026Minimax and Adaptive Covariance Matrix Estimation under Differential Privacycited by 1
  7. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  8. 2025Private Training & Data Generation by Clustering Embeddingscited by 0
  9. 2025Lower Bounds for Public-Private Learning under Distribution Shiftcited by 0