All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance

We consider the basic statistical challenge of designing an "all-purpose" mean estimation algorithm that is recommendable across a variety of settings and models. Recent work by Lee & Valiant (2022) introduced the first 1-d mean estimator whose error in the standard finite-variance+i.i.d. setting is optimal even in its constant factors; experimental demonstration of its good performance was shown by Gobet et al. (2022). Yet, unlike for classic (but not necessarily practical) estimators such as median-of-means and trimmed mean, this new algorithm lacked proven robustness guarantees in other settings, including the settings of adversarial data corruption and heavy-tailed distributions with infinite variance. Such robustness is important for practical use cases. This raises a research question: is it possible to have a mean estimator that is robust, without sacrificing provably optimal performance in the standard i.i.d. setting? In this work, we show that Lee and Valiant's estimator is in fact an "all-purpose" mean estimator by proving:

(A) It is robust to an η-fraction of data corruption, even in the strong contamination model; it has optimal estimation error O(σ √ η) for distributions with variance σ 2 . (B) For distributions with finite z th moment, for z ∈ (1, 2), it has optimal estimation error, matching the lower bounds of Devroye et al. (2016) up to constants.

We further show (C) that outlier robustness for 1-d mean estimators in fact implies neighborhood optimality, a notion of beyond worst-case and distribution-dependent optimality recently introduced by Dang et al. (2023). Previously, such an