# A Private and Computationally-Efficient Estimator for Unbounded Gaussians

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 56 references that are in the map.
- First posted on arXiv 8 Nov 2021.

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

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [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)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (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)
- [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)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [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)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (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)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Differentially Private Confidence Intervals](https://mlsanity.com/paper/2001.02285/) (2020)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Privately Learning Markov Random Fields](https://mlsanity.com/paper/2002.09463/) (2020)
- [Optimal Private Median Estimation under Minimal Distributional Assumptions](https://mlsanity.com/paper/2011.06202/) (2020)

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

- [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)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (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)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (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)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [PLAN: Variance-Aware Private Mean Estimation](https://mlsanity.com/paper/2306.08745/) (2023)
- [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)
- [A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacy](https://mlsanity.com/paper/2312.11712/) (2023)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Not All Learnable Distribution Classes are Privately Learnable](https://mlsanity.com/paper/2402.00267/) (2024)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [On Differentially Private Subspace Estimation in a Distribution-Free Setting](https://mlsanity.com/paper/2402.06465/) (2024)
- [Optimal Differentially Private Sampling of Unbounded Gaussians](https://mlsanity.com/paper/2503.01766/) (2025)
- [DP-SPRT: Differentially Private Sequential Probability Ratio Tests](https://mlsanity.com/paper/2508.06377/) (2025)
- [Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy](https://mlsanity.com/paper/2603.19703/) (2026)

## Abstract (arXiv)

We give the first polynomial-time, polynomial-sample, differentially private estimator for the mean and covariance of an arbitrary Gaussian distribution N(μ,Sigma) in ℝd. All previous estimators are either nonconstructive, with unbounded running time, or require the user to specify a priori bounds on the parameters μ and Sigma. The primary new technical tool in our algorithm is a new differentially private preconditioner that takes samples from an arbitrary Gaussian N(0,Sigma) and returns a matrix A such that A Sigma AT has constant condition number.