mlsanityData to 14 Oct 2026

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

arXiv 1704.03866 ↗First posted 12 Apr 2017cs.DS cs.IT cs.LGcited by 39

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 7; 2023: 4; 2024: 9; 2025: 5; 2026: 3.

39 papers.

Sort:

By area:

  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  3. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  4. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  5. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  6. 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
  7. 2021Robust Estimation for Random Graphscited by 8
  8. 2024A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motioncited by 8
  9. 2021SoS Degree Reduction with Applications to Clustering and Robust Moment Estimationcited by 7
  10. 2023Spectral clustering in the Gaussian mixture block modelcited by 7
  11. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  12. 2024Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussianscited by 7
27 more
  1. 2021Kalman Filtering with Adversarial Corruptionscited by 6
  2. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  3. 2025Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contaminationcited by 6
  4. 2022Efficient List-Decodable Regression using Batchescited by 5
  5. 2024Robust Distribution Learning with Local and Global Adversarial Corruptionscited by 5
  6. 2021Robust Online Convex Optimization in the Presence of Outlierscited by 4
  7. 2022Robust estimation algorithms don't need to know the corruption levelcited by 4
  8. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  9. 2024Distribution Learnability and Robustnesscited by 4
  10. 2021Exponential Weights Algorithms for Selective Learningcited by 2
  11. 2023Learning Mixtures of Gaussians with Censored Datacited by 2
  12. 2023CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruptioncited by 2
  13. 2024Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contaminationcited by 2
  14. 2024Multigroup Robustnesscited by 2
  15. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  16. 2025Learning High-dimensional Gaussians from Censored Datacited by 2
  17. 2021Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Errorcited by 1
  18. 2022Nearly minimax robust estimator of the mean vector by iterative spectral dimension reductioncited by 1
  19. 2024Distribution Learning Meets Graph Structure Samplingcited by 1
  20. 2024Robust Mixture Learning when Outliers Overwhelm Small Groupscited by 1
  21. 2025On the Learnability of Distribution Classes with Adaptive Adversariescited by 1
  22. 2025Linear Regression under Missing or Corrupted Coordinatescited by 1
  23. 2026High-Dimensional Gaussian Mean Estimation under Realizable Contaminationcited by 1
  24. 2026Robust Learning with Optimal Errorcited by 1
  25. 2022Privately Estimating a Gaussian: Efficient, Robust and Optimalcited by 0
  26. 2025Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Pointcited by 0
  27. 2026Beyond Heuristic Prompting: A Concept-Guided Bayesian Framework for Zero-Shot Image Recognitioncited by 0