# Covariance-Aware Private Mean Estimation Without Private Covariance Estimation

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 108 references that are in the map.
- First posted on arXiv 24 Jun 2021.

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

- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (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)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [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)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [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)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)

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

- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (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)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [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)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [A Fast Algorithm for Adaptive Private Mean Estimation](https://mlsanity.com/paper/2301.07078/) (2023)
- [Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices](https://mlsanity.com/paper/2401.03820/) (2024)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [(Nearly) Optimal Private Linear Regression via Adaptive Clipping](https://mlsanity.com/paper/2207.04686/) (2022)
- [PLAN: Variance-Aware Private Mean Estimation](https://mlsanity.com/paper/2306.08745/) (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)
- [Better Private Linear Regression Through Better Private Feature Selection](https://mlsanity.com/paper/2306.00920/) (2023)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- ["You Can't Fix What You Can't Measure": Privately Measuring Demographic Performance Disparities in Federated Learning](https://mlsanity.com/paper/2206.12183/) (2022)
- [Scalable Collaborative Learning via Representation Sharing](https://mlsanity.com/paper/2211.10943/) (2022)
- [Differentially private projection-depth-based medians](https://mlsanity.com/paper/2312.07792/) (2023)
- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)

## Abstract (arXiv)

We present two sample-efficient differentially private mean estimators for d-dimensional (sub)Gaussian distributions with unknown covariance. Informally, given n gtrsim d/α2 samples from such a distribution with mean μ and covariance Sigma, our estimators output tildeμ such that | tildeμ - μ |Sigma ≤ α, where | · |Sigma is the Mahalanobis distance. All previous estimators with the same guarantee either require strong a priori bounds on the covariance matrix or require Omega(d3/2) samples. Each of our estimators is based on a simple, general approach to designing differentially private mechanisms, but with novel technical steps to make the estimator private and sample-efficient. Our first estimator samples a point with approximately maximum Tukey depth using the exponential mechanism, but restricted to the set of points of large Tukey depth. Its accuracy guarantees hold even for data sets that have a small amount of adversarial corruption. Proving that this mechanism is private requires a novel analysis. Our second estimator perturbs the empirical mean of the data set with noise calibrated to the empirical covariance, without releasing the covariance itself. Its sample complexity guarantees hold more generally for subgaussian distributions, albeit with a slightly worse dependence on the privacy parameter. For both estimators, careful preprocessing of the data is required to satisfy differential privacy.