Estimators – References for the Median of Means Estimator Method

analysis-of-meansestimatorsmedianreferences

I can't find the term in Wikipedia, and by searching online, I seem to know the original material raised up the idea Median of Means Estimator is this book, while I can only find the scanned edition of this book, so I can't directly search the keywords, and the content seems doesn't offer more useful information where Median of Means Estimator might be raised.

I mainly want to know one theorem which is related to the Median of means estimator, which I read in this paper(Theorem S1 near Eq. (S13) ) is different from the little things I found online. I stated the theorem below for convenient reference:

Let $X$ be a random variable with variance $\sigma^2$. Then, $K$ independent sample means of size $N=34\sigma^2/\epsilon^2$ suffice to construct a median of means estimator $\hat{\mu}(N,K)$ that obeys $Pr[|\hat{\mu}-\mathbb{E}[X]|\ge\epsilon]\le2e^{-K/2}$ for all $\epsilon > 0$.

So is there some formal statement and proof of this kind of theorem of Median of Means Estimator?

Best Answer

The first paper cited below includes a review and proof of the median-of-means estimator. The second paper (whose main goal is to show an optimal sample size for mean estimation) also mentions this estimator (near end of section 2.1).

REFERENCES:

  • Devroye, L., Lerasle, M., et al. "Sub-Gaussian mean estimators", https://arxiv.org/pdf/1509.05845.pdf
  • Kunsch, R.J., Novak, E. And Rudolf, D., 2019. Solvable integration problems and optimal sample size selection. Journal of Complexity, 53, pp.40-67.
Related Question