9
$\begingroup$

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:

enter image description here

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.

$\endgroup$
5
  • $\begingroup$ For what K and N do you want an answer, or with what limiting properties? And can we replace “sharper” by “of lower variance”? $\endgroup$
    – Matt F.
    Commented May 24, 2023 at 3:26
  • $\begingroup$ @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? $\endgroup$
    – glS
    Commented May 24, 2023 at 8:49
  • $\begingroup$ 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 ?$$ $\endgroup$
    – Matt F.
    Commented May 25, 2023 at 3:21
  • $\begingroup$ @MattF. what do you mean with $\Delta estimators$? $\endgroup$
    – glS
    Commented May 25, 2023 at 8:30
  • $\begingroup$ That’s $\Delta$ for difference, so the difference between the mean as an estimator and the median of means as an estimator. $\endgroup$
    – Matt F.
    Commented May 25, 2023 at 9:18

1 Answer 1

4
$\begingroup$

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.

For well-behaved distributions (e.g. Gaussians and Uniform[-1,1]), this corresponds to larger-variance error distribution you are observing compared with the sample mean.

The recent Lee and Valiant estimator (https://arxiv.org/abs/2011.08384) has optimal proven guarantees in the multiplicative constants, and it works well numerically, both on well-behaved distributions and for heavy-tailed distributions.

Note however that once you have a very large number of samples, the central limit theorem is already "optimal" and so the sample mean is the best you can do. The issue for heavy-tailed distributions is that the "large" threshold for the number of samples depends arbitrarily badly on the tail, whereas better estimators make the "large" threshold independent of the tail, and so these estimators work better than the sample mean in the smaller-sample regime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.