mlsanityData to 7 Oct 2026

New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma

arXiv 2205.08532 ↗First posted 17 May 2022cs.DS cs.CR stat.MLcited by 32

Not on the map. Why?

Abstract (arXiv)

We prove new lower bounds for statistical estimation tasks under the constraint of (varepsilon, δ)-differential privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix in Frobenius norm requires Omega(d2) samples, and in spectral norm requires Omega(d3/2) samples, both matching upper bounds up to logarithmic factors. The latter bound verifies the existence of a conjectured statistical gap between the private and the non-private sample complexities for spectral estimation of Gaussian covariances. We prove these bounds via our main technical contribution, a broad generalization of the fingerprinting method to exponential families. Additionally, using the private Assouad method of Acharya, Sun, and Zhang, we show a tight Omega(d/(α2 varepsilon)) lower bound for estimating the mean of a distribution with bounded covariance to α-error in ℓ2-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of (varepsilon, 0)-differential privacy.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 34 of its 68 references that are in the map. First posted on arXiv 17 May 2022.

Builds on

34 of 68 references.

References · 34

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  3. 2018Privately Learning High-Dimensional Distributionscited by 103
  4. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  5. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  6. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  7. 2021Learning with User-Level Privacycited by 72
  8. 2021Differential privacy and robust statistics in high dimensionscited by 64
  9. 2019Private Hypothesis Selectioncited by 60
  10. 2015Between Pure and Approximate Differential Privacycited by 55
  11. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  12. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
22 more
  1. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  2. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  3. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  4. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  5. 2020Learning discrete distributions: user vs item-level privacycited by 41
  6. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  7. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  8. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  9. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  10. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  11. 2017Tight Lower Bounds for Differentially Private Selectioncited by 33
  12. 2020A Primer on Private Statisticscited by 30
  13. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  14. 2016Make Up Your Mind: The Price of Online Queries in Differential Privacycited by 26
  15. 2017Differentially Private Testing of Identity and Closeness of Discrete Distributionscited by 25
  16. 2020Differentially Private Confidence Intervalscited by 20
  17. 2020The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Boundscited by 15
  18. 2020Privately Learning Markov Random Fieldscited by 14
  19. 2020Optimal Private Median Estimation under Minimal Distributional Assumptionscited by 13
  20. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  21. 2018The Power of The Hybrid Model for Mean Estimationcited by 11
  22. 2019Differentially private sub-Gaussian location estimatorscited by 9

Built on by

Cited by year (2026 to 7 Oct)

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

32 papers.

Sort:

By area:

  1. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  2. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  3. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  4. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  5. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  6. 2022Differentially Private Covariance Revisitedcited by 15
  7. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  8. 2024Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimationcited by 11
  9. 2023Concentrated Differential Privacy for Banditscited by 10
  10. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  11. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  12. 2024Dimension-free Private Mean Estimation for Anisotropic Distributionscited by 6
20 more
  1. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  2. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  3. 2025Continual Release Moment Estimation with Differential Privacycited by 5
  4. 2024Distribution Learnability and Robustnesscited by 4
  5. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  6. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
  7. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  8. 2025Learning with Differentially Private (Sliced) Wasserstein Gradientscited by 2
  9. 2025Tukey Depth Mechanisms for Practical Private Mean Estimationcited by 2
  10. 2025Sample-Optimal Private Regression in Polynomial Timecited by 2
  11. 2025Private Statistical Estimation via Truncationcited by 1
  12. 2026Minimax and Adaptive Covariance Matrix Estimation under Differential Privacycited by 1
  13. 2022Privately Estimating a Gaussian: Efficient, Robust and Optimalcited by 0
  14. 2023Improving the Utility of Differentially Private Clustering through Dynamical Processingcited by 0
  15. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  16. 2025Bayesian Perspective on Memorization and Reconstructioncited by 0
  17. 2025Private Training & Data Generation by Clustering Embeddingscited by 0
  18. 2025Lower Bounds for Public-Private Learning under Distribution Shiftcited by 0
  19. 2026Minimax optimal differentially private synthetic data for smooth queriescited by 0
  20. 2026A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learningcited by 0