All-In-One Robust Estimator of the Gaussian Mean

Abstract

The goal of this paper is to show that a single robust estimator of the mean of a multivariate Gaussian distribution can enjoy five desirable properties. First, it is computationally tractable in the sense that it can be computed in a time which is at most polynomial in dimension, sample size and the logarithm of the inverse of the contamination rate. Second, it is equivariant by translations, uniform scaling and orthogonal transformations. Third, it has a high breakdown point equal to $0.5$, and a nearly-minimax-rate-breakdown point approximately equal to $0.28$. Fourth, it is minimax rate optimal, up to a logarithmic factor, when data consists of independent observations corrupted by adversarially chosen outliers. Fifth, it is asymptotically efficient when the rate of contamination tends to zero. The estimator is obtained by an iterative reweighting approach. Each sample point is assigned a weight that is iteratively updated by solving a convex optimization problem. We also establish a dimension-free non-asymptotic risk bound for the expected error of the proposed estimator. It is the first result of this kind in the literature and involves only the effective rank of the covariance matrix. Finally, we show that the obtained results can be extended to sub-Gaussian distributions, as well as to the cases of unknown rate of contamination or unknown covariance matrix.

arXiv comment41 pages, 5 figures; added sub-Gaussian case with unknown Sigma or eps

References in corpus (10)

• A geometric analysis of subspace clustering with outliers
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Tight conditions for consistency of variable selection in the context of high dimensionality
• Boosting in the presence of outliers: adaptive classification with non-convex loss functions
• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
• Fast Mean Estimation with Sub-Gaussian Rates
• Confidence regions and minimax rates in outlier-robust estimation on the probability simplex
• Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
• When does the Tukey median work?

Cited by in corpus (4)

• Information theoretic limits of robust sub-Gaussian mean estimation under star-shaped constraints
• Location and scatter halfspace median under α-symmetric distributions
• Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
• Adversarial robust weighted Huber regression