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: