Outlier Robust Mean Estimation with Subgaussian Rates via Stability

Abstract

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.

References in corpus (7)

• Geometric median and robust estimation in Banach spaces
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Being Robust (in High Dimensions) Can Be Practical
• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
• Generalized Resilience and Robust Statistics
• A Unified Approach to Robust Mean Estimation
• High-Dimensional Robust Mean Estimation via Gradient Descent

Cited by in corpus (8)

• Sample Selection with Uncertainty of Losses for Learning with Noisy Labels
• Generalized Resilience and Robust Statistics
• Concentration study of M-estimators using the influence function
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
• Heavy-tailed Streaming Statistical Estimation
• Adversarially robust change point detection
• Adversarial robust weighted Huber regression
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion