A Unified Approach to Robust Mean Estimation

Abstract

In this paper, we develop connections between two seemingly disparate, but central, models in robust statistics: Huber's epsilon-contamination model and the heavy-tailed noise model. We provide conditions under which this connection provides near-statistically-optimal estimators. Building on this connection, we provide a simple variant of recent computationally-efficient algorithms for mean estimation in Huber's model, which given our connection entails that the same efficient sample-pruning based estimators is simultaneously robust to heavy-tailed noise and Huber contamination. Furthermore, we complement our efficient algorithms with statistically-optimal albeit computationally intractable estimators, which are simultaneously optimally robust in both models. We study the empirical performance of our proposed estimators on synthetic datasets, and find that our methods convincingly outperform a variety of practical baselines.

51 pages, 6 figures

References in corpus (7)

• Geometric median and robust estimation in Banach spaces
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
• High Dimensional Robust Sparse Regression
• Fast Mean Estimation with Sub-Gaussian Rates
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
• Sub-Gaussian estimators of the mean of a random vector

Cited by in corpus (10)

• Generalized Resilience and Robust Statistics
• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• Outlier Robust Mean Estimation with Subgaussian Rates via Stability
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
• Learning-Augmented $k$-means Clustering
• Robust Estimation of Covariance Matrices: Adversarial Contamination and Beyond
• Generalization Bounds in the Presence of Outliers: a Median-of-Means Study
• Estimating location parameters in entangled single-sample distributions
• Heavy-tailed Streaming Statistical Estimation
• Adversarially robust change point detection