median-of-means

An approach to heavy-tailed scalar concentration and multivariate heavy-tailed concentration.

The overall idea is straightforward: Split the data into $k$ buckets and compute the sample mean ${\hat{\mu }}_i$ of each bucket. Then the overall estimator is

$$\hat{\mu }=\text{Median}({\hat{\mu }}_1,\dots ,{\hat{\mu }}_k).$$

There are several questions to answer to implement this in practice. First, how to choose $k$? Second (especially relevant in multivariate settings), how do we define the median?

Scalar case

With probability at least $3/4$ by Chebyshev, ${\hat{\mu }}_i$ is not too far from the true mean. So for the median to be far from the mean, many (at least half) independent Bernoulli events with probability 3/4 must fail to occur.

If we choose $k=\lceil 8\log (1/\delta )\rceil$ then the median-of-means estimator $\hat{\mu }$ satisfies

$$\mathbb{P}\left(|\hat{\mu }-\mu |\ge \sigma \sqrt{\frac{32\log (1/\delta )}{n}}\right)\le \delta .$$

The MoM estimator can also be extended to situations where the distribution has no variance. If $\mathbb{E}|X-\mu {|}^{1+ϵ}\le v$, then

$$\mathbb{P}\left(|\hat{\mu }-\mu |\ge (12v{)}^{\frac{1}{1+ϵ}}{\left(\frac{8\log (1/\delta )}{n}\right)}^{\frac{ϵ}{1+ϵ}}\right)\le \delta .$$

This was originally proved by Bubeck, Cesa-Bianchi, and Lugosi in the content of heavy-tailed bandits. I have a post with the proofs here.

You can sequentialize the MoM estimator using the Dubins-Savage inequality. I have a post about that here.

Finite-dimensional vector case

Defining the median in ${\mathbb{R}}^d$ is slightly trickier.

One option is the geometric median, which is studied by Minsker (see below). This achieves rate $\sqrt{\text{Tr}(\Sigma )\log (1/\delta )/n}$, which is not quite sub-Gaussian.

Lugosi and Mendelson define a specialized version of the median and get sub-Gaussian rates. Blog post here. Hopkins made this computationally tractable in 2020.

Unlike the scalar setting, MoM in ${\mathbb{R}}^d$ has not been extended to settings where the variance doesn’t exist.

Infinite-dimensional case

MoM with the geometric median was studied in Banach spaces by Minsker and in Polish spaces by Yun and Park:

Heavy-tailed concentration

In 2015, Minsker proposed the geometric median-of-means for Banach spaces. This is a general method for boosting weak (polynomial rate) estimators into an estimator with exponential rate. The idea is similar to the Lugosi-Mendelson median-of-means (see multivariate heavy-tailed concentration), but the weak estimators are aggregated using the geometric median. This can be computed in polynomial time (in ${\mathbb{R}}^d$) using Weisfeld’s algorithm, since the objective is convex. This estimator was proposed simultaneously by Hsu and Sabato.

In 2022, Yun and Park extended geometric median-of-means to Polish spaces, which include separable Banach spaces. They seem to get the same rates as Minsker, which are not quite sub-Gaussian in ${\mathbb{R}}^d$.

Link to original