# New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma

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

## Key facts

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

## Builds on (most cited first, 30 of 34)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [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)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Learning discrete distributions: user vs item-level privacy](https://mlsanity.com/paper/2007.13660/) (2020)
- [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)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [A Primer on Private Statistics](https://mlsanity.com/paper/2005.00010/) (2020)
- [Differentially Private Algorithms for Learning Mixtures of Separated Gaussians](https://mlsanity.com/paper/1909.03951/) (2019)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Differentially Private Confidence Intervals](https://mlsanity.com/paper/2001.02285/) (2020)
- [The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds](https://mlsanity.com/paper/2011.03900/) (2020)
- [Privately Learning Markov Random Fields](https://mlsanity.com/paper/2002.09463/) (2020)

## Built on by (most cited first, 30 of 33)

- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation](https://mlsanity.com/paper/2402.13531/) (2024)
- [Concentrated Differential Privacy for Bandits](https://mlsanity.com/paper/2309.00557/) (2023)
- [Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes](https://mlsanity.com/paper/2404.17714/) (2024)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Not All Learnable Distribution Classes are Privately Learnable](https://mlsanity.com/paper/2402.00267/) (2024)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [Learning with Differentially Private (Sliced) Wasserstein Gradients](https://mlsanity.com/paper/2502.01701/) (2025)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Sample-Optimal Private Regression in Polynomial Time](https://mlsanity.com/paper/2503.24321/) (2025)
- [Private Statistical Estimation via Truncation](https://mlsanity.com/paper/2505.12541/) (2025)
- [Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy](https://mlsanity.com/paper/2603.19703/) (2026)
- [Privately Estimating a Gaussian: Efficient, Robust and Optimal](https://mlsanity.com/paper/2212.08018/) (2022)
- [Improving the Utility of Differentially Private Clustering through Dynamical Processing](https://mlsanity.com/paper/2304.13886/) (2023)
- [Sample-Efficient Private Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2411.02298/) (2024)
- [Bayesian Perspective on Memorization and Reconstruction](https://mlsanity.com/paper/2505.23658/) (2025)
- [Private Training & Data Generation by Clustering Embeddings](https://mlsanity.com/paper/2506.16661/) (2025)
- [Lower Bounds for Public-Private Learning under Distribution Shift](https://mlsanity.com/paper/2507.17895/) (2025)

## 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.