mlsanityData to 7 Oct 2026

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation

arXiv 2310.06289 ↗First posted 10 Oct 2023math.ST cs.CR cs.DScited by 16

Not on the map. Why?

Abstract (arXiv)

We provide optimal lower bounds for two well-known parameter estimation (also known as statistical estimation) tasks in high dimensions with approximate differential privacy. First, we prove that for any α ≤ O(1), estimating the covariance of a Gaussian up to spectral error α requires tildeOmegaleft(fracd3/2α varepsilon + fracdα2right) samples, which is tight up to logarithmic factors. This result improves over previous work which established this for α ≤ Oleft(frac1√dright), and is also simpler than previous work. Next, we prove that estimating the mean of a heavy-tailed distribution with bounded kth moments requires tildeOmegaleft(fracdαk/(k-1) varepsilon + fracdα2right) samples. Previous work for this problem was only able to establish this lower bound against pure differential privacy, or in the special case of k = 2. Our techniques follow the method of fingerprinting and are generally quite simple. Our lower bound for heavy-tailed estimation is based on a black-box reduction from privately estimating identity-covariance Gaussians. Our lower bound for covariance estimation utilizes a Bayesian approach to show that, under an Inverse Wishart prior distribution for the covariance matrix, no private estimator can be accurate even in expectation, without sufficiently many samples.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 37 of its 53 references that are in the map. First posted on arXiv 10 Oct 2023.

Builds on

37 of 53 references.

References · 37

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  3. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  4. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  5. 2018Privately Learning High-Dimensional Distributionscited by 103
  6. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  7. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  8. 2021Learning with User-Level Privacycited by 72
  9. 2021Robust and Differentially Private Mean Estimationcited by 66
  10. 2021Differential privacy and robust statistics in high dimensionscited by 64
  11. 2019Private Hypothesis Selectioncited by 60
  12. 2015Between Pure and Approximate Differential Privacycited by 55
25 more
  1. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  2. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  3. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  4. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  5. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  6. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  7. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  8. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  9. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  10. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  11. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  12. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  13. 2017Tight Lower Bounds for Differentially Private Selectioncited by 33
  14. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  15. 2020A Primer on Private Statisticscited by 30
  16. 2016Make Up Your Mind: The Price of Online Queries in Differential Privacycited by 26
  17. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  18. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  19. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  20. 2013Efficient Algorithms for Privately Releasing Marginals via Convex Relaxationscited by 17
  21. 2022Differentially Private Covariance Revisitedcited by 15
  22. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  23. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  24. 2023Mean Estimation with User-level Privacy under Data Heterogeneitycited by 8
  25. 2018Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outlierscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 9; 2025: 4; 2026: 3.

16 papers.

Sort:

By area:

  1. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  2. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  3. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 10
  4. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  5. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  6. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  7. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
  8. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  9. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  10. 2025Private Statistical Estimation via Truncationcited by 1
  11. 2026Minimax and Adaptive Covariance Matrix Estimation under Differential Privacycited by 1
  12. 2026On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCAcited by 1
4 more
  1. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  2. 2025On Theoretical Limits of Learning with Label Differential Privacycited by 0
  3. 2025Lower Bounds for Public-Private Learning under Distribution Shiftcited by 0
  4. 2026Improved Private Sparse Covariance Estimation with Multiscale Threshold Testscited by 0