heavy-tailed scalar concentration

Unlike light-tailed settings, the sample mean is not well-behaved in heavy-tailed settings. Since heavy-tailed distributions may not have finite MGFs, the Chernoff method is not applicable. Catoni gives an example demonstrating the bound achieved via Markov’s inequality (basic inequalities), i.e.,

$$\mathbb{P}\left(|{\overline{X}}_n-\mu |)\ge \frac{\sigma }{\sqrt{n\delta }}\right)\le \delta ,$$

is essentially tight (where we receive observations $X_1,\dots ,X_n$ and ${\overline{X}}_n$ is the sample mean). The issue is that outliers can have devastating effects on the sample mean, and heavy-tailed distributions can have many extreme observations. See this discussion by Lugosi and Mendelson for more details.

Ideally we want estimators with sub-Gaussian like behavior, i.e.,

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

This is an exponential improvement in the dependence on $1/\delta$. These are called sub-Gaussian estimators.

Median-of-means (MoM)

The idea is simple: Split the data into $k$ buckets, and compute the sample mean ${\hat{\mu }}_i$ of each bucket. 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.

Trimmed mean estimator

Since the empirical mean is ruined by outliers, a natural idea is to remove some fraction of the points and then compute the empirical mean on the remaining points. These are known as trimmed mean estimators.

Oliveira and Orenstein prove that if you remove $\gamma n$ of the largest and smallest points for $\gamma =\Theta (\log (1/\delta )/n)$, then the trimmed mean is sub-Gaussian. See here for a discussion.

A related idea is proposed by Lee and Valiant who don’t remove entire points but instead weighted fractions of each observations:

At the highest level: in order to return a $\delta$-robust estimate of the mean, our estimator “throws out the $\frac{1}{1}\log (1/\delta )$ most extreme points in the samples”, and returns the mean of what remains. More specifically, outliers are thrown out in a weighted manner, where we throw out a fraction of each data point, with the fraction proportional to the square of its distance from a median-of-means initial guess for the mean, where the fraction is capped at 1, and the proportionality constant is chosen so that the total weight thrown out equals exactly $\frac{1}{3}\log (1/\delta )$.

Their estimator achieves a bound of $\sigma (1+o(1))\sqrt{2\log (1/\delta )/n}$.

Catoni-Giulini M-estimator