mlsanityData to 14 Oct 2026

Outlier Robust Mean Estimation with Subgaussian Rates via Stability

arXiv 2007.15618 ↗First posted 30 Jul 2020math.ST cs.DS cs.LGcited by 50

Not on the map. Why?

Abstract (arXiv)

We study the problem of outlier robust high-dimensional mean estimation under a finite covariance assumption, and more broadly under finite low-degree moment assumptions. We consider a standard stability condition from the recent robust statistics literature and prove that, except with exponentially small failure probability, there exists a large fraction of the inliers satisfying this condition. As a corollary, it follows that a number of recently developed algorithms for robust mean estimation, including iterative filtering and non-convex gradient descent, give optimal error estimators with (near-)subgaussian rates. Previous analyses of these algorithms gave significantly suboptimal rates. As a corollary of our approach, we obtain the first computationally efficient algorithm with subgaussian rate for outlier-robust mean estimation in the strong contamination model under a finite covariance assumption.

Key facts. Cited by 50 papers in the map (data through 14 Oct 2026). First posted on arXiv 30 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 11; 2023: 14; 2024: 11; 2025: 3; 2026: 5.

50 papers.

Sort:

By area:

  1. 2022Is Out-of-Distribution Detection Learnable?cited by 109
  2. 2021Sample Selection with Uncertainty of Losses for Learning with Noisy Labelscited by 79
  3. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  4. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  5. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
  6. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  7. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  8. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  9. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  10. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  11. 2024Adaptive Gradient Clipping for Robust Federated Learningcited by 11
  12. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
38 more
  1. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  2. 2023High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackerscited by 7
  3. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  4. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  5. 2022Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Modelscited by 6
  6. 2023Byzantine-Resilient Federated Learning at Edgecited by 6
  7. 2025On Corruption-Robustness in Performative Reinforcement Learningcited by 6
  8. 2022Robust Methods for High-Dimensional Linear Learningcited by 5
  9. 2022Robust Online and Distributed Mean Estimation Under Adversarial Data Corruptioncited by 5
  10. 2023High-dimensional Location Estimation via Norm Concentration for Subgamma Vectorscited by 5
  11. 2022Robust supervised learning with coordinate gradient descentcited by 3
  12. 2022Robust Estimation for Nonparametric Families via Generative Adversarial Networkscited by 3
  13. 2023Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussianscited by 3
  14. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  15. 2023Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separationcited by 3
  16. 2024SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and Morecited by 3
  17. 2024Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensingcited by 2
  18. 2024The Empirical Mean is Minimax Optimal for Local Glivenko-Cantellicited by 2
  19. 2024Robust Gradient Descent for Phase Retrievalcited by 2
  20. 2024Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Errorcited by 2
  21. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  22. 2021Robust Voting Rules from Algorithmic Robust Statisticscited by 1
  23. 2025Performance of the empirical median for location estimation in heteroscedastic settingscited by 1
  24. 2025Distributionally Robust Optimization with Adversarial Data Contaminationcited by 1
  25. 2026Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexitycited by 1
  26. 2022Robustifying Markowitzcited by 0
  27. 2023Robust Mean Estimation Without Moments for Symmetric Distributionscited by 0
  28. 2023Sparse Mean Estimation in Adversarial Settings via Incremental Learningcited by 0
  29. 2023Online Heavy-tailed Change-point detectioncited by 0
  30. 2023Empirical Risk Minimization for Losses without Variancecited by 0
  31. 2023Robust Online Covariance and Sparse Precision Estimation Under Arbitrary Data Corruptioncited by 0
  32. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  33. 2024Heavy-tailed Contamination is Easier than Adversarial Contaminationcited by 0
  34. 2024Optimal Rates for Robust Stochastic Convex Optimizationcited by 0
  35. 2026Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedbackcited by 0
  36. 2026Mean Testing under Truncation beyond Gaussiancited by 0
  37. 2026Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applicationscited by 0
  38. 2026Precise sample covariance spectral norm error -- an RDT viewcited by 0