Fast Mean Estimation with Sub-Gaussian Rates

Abstract

We propose an estimator for the mean of a random vector in ${\mathbb{R}}^d$ that can be computed in time $O(n^4+n^{2}d)$ for $n$ i.i.d.~samples and that has error bounds matching the sub-Gaussian case. The only assumptions we make about the data distribution are that it has finite mean and covariance; in particular, we make no assumptions about higher-order moments. Like the polynomial time estimator introduced by Hopkins, 2018, which is based on the sum-of-squares hierarchy, our estimator achieves optimal statistical efficiency in this challenging setting, but it has a significantly faster runtime and a simpler analysis.

References in corpus (4)

• Geometric median and robust estimation in Banach spaces
• Robust empirical mean Estimators
• Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
• Dimension-free PAC-Bayesian bounds for the estimation of the mean of a random vector

Cited by in corpus (8)

• Concentration study of M-estimators using the influence function
• A Unified Approach to Robust Mean Estimation
• MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means
• All-In-One Robust Estimator of the Gaussian Mean
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• A spectral algorithm for robust regression with subgaussian rates
• Exponential Concentration for Geometric-Median-of-Means in Non-Positive Curvature Spaces
• Designing Differentially Private Estimators in High Dimensions