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

Mean estimation is the following simple task: given samples from a probability distribution D on R, estimate the mean mu of D. Although mean estimation has been studied since the dawn of time, various elementary and fundamental questions about mean estimation are still being tackled.

A natural goal is to obtain optimal nonasymptotic errors. That is, for a given number of samples n and error rate delta, design an estimator hat(mu) which satisfies an inequality of the form Pr( |hat(mu) - mu| < error ) \geq 1-delta, for as small a function error(n,delta) as possible. If D is Gaussian, the empirical mean gives the best possible estimator, but since the real world isn't really Gaussian, we would like to obtain estimators with such guarantees, ideally with the function error(n,delta) matching the one we would get for Gaussian D, under much weaker assumptions on D.

Lee and Valiant in 2022 constructed a mean estimator which obtains the optimal error(n,delta) under only the assumption that D has bounded variance. Their estimator even adapts to the variance of D.

While the Lee-Valiant estimator is highly robust in the sense of tolerating a broad class of underlying distributions D, the question this paper addresses is whether it is robust in other senses, in particular:

-- adversarial contamination/data poisoning -- what if a small fraction of the sample are chosen adversarially? -- nonexistent variance -- what if even the variance of D does not exist?

The authors prove that the Lee-Valiant estimator satisfies strong robustness guarantees in both these senses. First, they show that it is resilient to an $\eta$-fraction of adversarially corrupted samples in the strong contamination model, achieving the optimal error bound $O(\sigma \sqrt{\eta})$. Second, they establish that when $D$ has only a finite $z$-th moment for $z \in (1,2)$, the estimator attains the minimax-optimal error rate, matching known lower bounds. Third, they show that it satisfies neighborhood optimality, meaning that it adapts to the structure of the underlying distribution and achieves the best possible error beyond worst-case guarantees. Finally, they prove that the estimator is asymptotically normal, converging efficiently to the true mean as the sample size grows.

These results show that the Lee-Valiant estimator is not just optimal in the standard setting but also robust across a range of challenging conditions, making it a strong candidate for practical use over alternatives like median-of-means or trimmed means.

This paper concerns the problem of estimating the mean of i.i.d. real-valued samples. The authors studies an estimator due to Lee & Valiant 2022 and show that this estimator enjoys several properties not known before. These include

• optimal robustness against adversarial outliers
• optimal accuracy for heavy-tailed distributions
• optimal adaptation to unknown distributions

This paper considers the problem of designing "all-purpose"mean estimation algorithms that can be applied to a variety of scenarios. To be specific, the authors consider the estimator by Lee & Valiant (2022). This algorithm, is previously shown to be optimal in the standard finite variance and i.i.d. setting. This paper, further give the result that Lee & Valiant (2022)'s algorithm is optimal in other settings. To be specific, they proved that the algorithm is robust to data corruption, and also optimal for distributions that have infinite variance.

This paper can be seen as a follow up for the seminal work of Lee & Valiant (2022), which proposed an optimal mean estimator for distributions over the set of real values, i.e. $\mathbb{R}$. Based on that, this paper further shows that the mean estimator of Lee & Valiant (2022) is ``all-purpose'', that is, it is robust to an $\eta$-fraction of corruptions under the strong contamination model; meanwhile, for heavy-tailed distribution with bounded $z$-th moment ($z\in(1,2)$), it has optimal estimation error comparing to a lower bound in Devroye et al. (2016). Futhermore, it also shows that all estimators with similar error guarantees imply the neighborhood optimal, hence solving an open question raised in Dang et al. (2023). Finally, the paper also proves that the estimator is asymptotically normal and efficient, further supporting its performance in many learning scenarios.

Summary.

The topic of this paper is 1D robust mean estimation. Lee and Valiant (2022) proposed an estimator for the mean which is optimal and tight down to the leading constant for the class of distributions with finite variance (algorithm reported in Estimator 1 and guarantee reported in Fact 1.1.).

In this paper, the authors demonstrate through careful analysis that the estimator (without any modification to it):

• Achieves optimal guarantees in the adversarial contamination model.

• Achieves optimal guarantees for the class of distributions with finite $z$th moment for $z \in (1,2)$ (specifically, it achieves the lower bound in Devroye et al., 2016 up to constants).

• Achieves so-called “neighborhood optimality” (Dang et al., 2023).

• Is asymptotic normal and efficient (in the finite variance, uncontaminated setting).

Following the above, the authors deduce that the Lee and Valiant’s estimator is “all purpose”, that is, it should be the one used in practice, in lieu of more classical algorithms such as median-of-means or trimmed mean.

Strengths.

• The problem is of strong interest to the ICML community (and the more general ML community).

• No soundness concerns were raised, and the writing is clear.

• Novelty: this is the first time an estimator was found to satisfy optimality to the leading constant in the finite variance setting, and is at the same time robust to adversarial contamination and optimal for distributions with infinite variance.

• The main claim that the estimator is “all purpose” is convincing; this is particularly important for practioners, as it removes the need to make additional assumptions on their data.

Weaknesses.

The presented analysis may not extend to higher dimensions (aQTr , eHht, UmEB); however, devising optimal estimator in dimensions higher than one is known to be a hard problem in the field.

Discussion and reviewer consensus.

There is strong consensus among the reviewer that the paper should be accepted.

Additional remarks.

Some minor points were raised by eHht, I recommend the authors to include more details on neighborhood optimality in their final version if the paper gets accepted.

Overall evaluation.

This is a serious contribution to the ICML program; I recommend acceptance.