# When is the median-of-means estimator better than the standard mean?

The median-of-means estimator is often given as an alternative way to, given a sequence of IID random variables $$X_1,...,X_N$$, estimate the expectation value $$\mathbb{E}[X]$$ (see e.g. these pdf notes by Yen-Chi Chen, or these slides by Gabor Lugosi).

The basic idea is that, instead of computing $$\frac1 N\sum_{i=1}^N X_i$$, we divide the observations into $$K$$ subsamples, compute the mean within each subsample, and then compute the median of the means. As discussed in the above notes, or also in (math.ST:1509.05845), the median-of-means estimator gives finite-sample exponential concentrations guarantees.

It is also my understanding (though I'm less certain about this) that median-of-means only provides advantages for distributions with heavy tails. In particular, whenever the distribution is sub-Gaussian (and thus, in particular, whenever it's bounded), we have the same guarantees with just the standard mean.

Assuming the above is correct, what are explicit examples that demonstrate the possible advantages of median-of-means? These, I believe, would be examples of distributions which give a distribution for the median-of-means that is "sharper" than the one for the standard mean.

For reference, if I try to apply it, as a toy example, to a uniform distribution in $$[-1,1]$$, and compare the distribution of mean vs median-of-means for different $$K$$s, I get the following:

which shows the mean clearly always outperforming median-of-means. This is done using $$N=20$$ and $$10^4$$ realizations to obtain smoother (smoothed) histograms. Mathematica snippet used to generate it is:

With[{numSamples = 20, realizations = 10000, ks = {2, 4, 5}},
Table[
With[{data = RandomVariate[UniformDistribution[{-1, 1}], numSamples]},
{
Mean @ data,
Sequence @@ Table[Mean /@ Partition[data, k] // Median, {k, ks}]
}
],
realizations
] // SmoothHistogram[Evaluate @ Transpose @ #,
PlotLegends -> {"mean", Sequence @@ Table["median-of-means, K=" <> ToString @ k,{k, ks}]},
PlotRange -> All, GridLines -> Automatic
]&
]

I figured that trying this with uniform distributions over a wider interval $$[-M,M]$$ one might start to see the difference, as these would be "closer" to having a "heavy tail" (I'm not entirely sure it makes sense, but it at least seemed sensible), but I always get the mean more concentrated around the average than median-of-means.

• For what K and N do you want an answer, or with what limiting properties? And can we replace “sharper” by “of lower variance”? May 24, 2023 at 3:26
• @MattF. well, I'm looking for any example that shows the advantage of using median-of-mean. This would naturally mean it having lower variance for me, but I don't know if there's possibly some other more suitable metric. Same for $K$ and $N$. The references generally use $K\simeq \log(1/\delta)$ to ensure the error probability being bounded by $\delta$, so it seems like different choices of $K$ can be used to different degrees of closeness around the expected value. As for $N$, don't we just get Gaussians for large $N$, and thus the difference between the estimators would disappear?
– glS
May 24, 2023 at 8:49
• 1) Have you tried exponential or Poisson or lognormal distributions (with high $\sigma$)? They might show more interesting results than symmetric distributions. 2) Perhaps $$\lim_{N\to\infty}\Delta estimators =0$$ but that needn’t end the discussion; e.g. one might ask: for what function $f(N)$ do you get a finite non-zero number from $$\lim_{N\to\infty}f(N)\Delta estimators ?$$ May 25, 2023 at 3:21
• @MattF. what do you mean with $\Delta estimators$?
– glS
May 25, 2023 at 8:30
• That’s $\Delta$ for difference, so the difference between the mean as an estimator and the median of means as an estimator. May 25, 2023 at 9:18

Median of means performs badly in practice because of the bad multiplicative constant hidden inside the big O (which in reasonable asymptotic regimes is $$\pi/2$$ or $$\sqrt{\pi/2}$$ depending on whether you're measuring the variance or the absolute estimation error). You can find this in Equation (2) in https://arxiv.org/pdf/2202.11842.pdf.