# Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2017.

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

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motion](https://mlsanity.com/paper/2404.11590/) (2024)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination](https://mlsanity.com/paper/2502.14772/) (2025)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Robust Distribution Learning with Local and Global Adversarial Corruptions](https://mlsanity.com/paper/2406.06509/) (2024)
- [Robust Online Convex Optimization in the Presence of Outliers](https://mlsanity.com/paper/2107.01881/) (2021)
- [Robust estimation algorithms don't need to know the corruption level](https://mlsanity.com/paper/2202.05453/) (2022)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Exponential Weights Algorithms for Selective Learning](https://mlsanity.com/paper/2106.15662/) (2021)
- [Learning Mixtures of Gaussians with Censored Data](https://mlsanity.com/paper/2305.04127/) (2023)
- [CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption](https://mlsanity.com/paper/2309.16563/) (2023)
- [Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination](https://mlsanity.com/paper/2403.10416/) (2024)
- [Multigroup Robustness](https://mlsanity.com/paper/2405.00614/) (2024)
- [The Broader Landscape of Robustness in Algorithmic Statistics](https://mlsanity.com/paper/2412.02670/) (2024)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error](https://mlsanity.com/paper/2112.13832/) (2021)
- [Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction](https://mlsanity.com/paper/2204.02323/) (2022)

## Abstract (arXiv)

We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an varepsilon-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error O(varepsilon) in the total variation distance, which is optimal up to a universal constant that is independent of the dimension. In the case where just the mean is unknown, our robustness guarantee is optimal up to a factor of √2 and the running time is polynomial in d and 1/ε. When both the mean and covariance are unknown, the running time is polynomial in d and quasipolynomial in 1/varepsilon. Moreover all of our algorithms require only a polynomial number of samples. Our work shows that the same sorts of error guarantees that were established over fifty years ago in the one-dimensional setting can also be achieved by efficient algorithms in high-dimensional settings.