= Median-of-means estimator
A <median-of-means estimator> divides a sample into $k$ disjoint groups, computes the <sample mean> in each group, and returns a <sample median> of those group means. A single extreme observation changes only one group <mean>, so it need not dominate the final answer.
Here is a finite-<variance> guarantee. Let the observations be <independent and identically distributed random variables> with <mean> $\mu$ and <variance> $v>0$. Take odd $k$, groups of equal size $m=\lfloor n/k\rfloor$, and discard any unused observations. By <Chebyshev inequality>, each group <mean> differs from $\mu$ by more than $2\sqrt{v/m}$ with <probability> at most $1/4$.
The groups are <independent>. If their <sample median> exceeds this error, at least half of the groups must be bad. Applying <Hoeffding inequality> to their bad-group indicators gives
$$
\mathbb P\left(|\widehat\mu-\mu|>2\sqrt{v/m}\right)\leq e^{-k/8}.
$$
Thus an odd $k\geq8\log(1/\delta)$ gives confidence at least $1-\delta$, provided there are enough observations. If $n\geq2k$, then $m\geq n/(2k)$, giving error at most $2\sqrt{2vk/n}$. This is a <sub-Gaussian deviation bound> under finite <variance>; it does not assert that the observations are <sub-Gaussian random variables>. The block argument above derives the bound from the two stated inequalities. Choosing too many groups makes the individual means noisy.
Back to article page
