# Outlier Robust Mean Estimation with Subgaussian Rates via Stability

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

## Key facts

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

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

- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Sample Selection with Uncertainty of Losses for Learning with Noisy Labels](https://mlsanity.com/paper/2106.00445/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Corruption Robust Offline Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2402.06734/) (2024)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Adaptive Gradient Clipping for Robust Federated Learning](https://mlsanity.com/paper/2405.14432/) (2024)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackers](https://mlsanity.com/paper/2307.13352/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (2022)
- [Byzantine-Resilient Federated Learning at Edge](https://mlsanity.com/paper/2303.10434/) (2023)
- [On Corruption-Robustness in Performative Reinforcement Learning](https://mlsanity.com/paper/2505.05609/) (2025)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Robust Online and Distributed Mean Estimation Under Adversarial Data Corruption](https://mlsanity.com/paper/2209.09624/) (2022)
- [High-dimensional Location Estimation via Norm Concentration for Subgamma Vectors](https://mlsanity.com/paper/2302.02497/) (2023)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Robust Estimation for Nonparametric Families via Generative Adversarial Networks](https://mlsanity.com/paper/2202.01269/) (2022)
- [Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians](https://mlsanity.com/paper/2301.09024/) (2023)
- [Robust Stochastic Optimization via Gradient Quantile Clipping](https://mlsanity.com/paper/2309.17316/) (2023)
- [Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation](https://mlsanity.com/paper/2312.11769/) (2023)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing](https://mlsanity.com/paper/2403.10547/) (2024)
- [The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli](https://mlsanity.com/paper/2410.02835/) (2024)

## 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.