[AIRG] Fast concentration for mean estimation, 04/03, CS3310

[Ankit Pensia <ankitp@xxxxxxxxxxx>]

Hi AIRG,

I will talk about mean estimation for heavy-tailed distributions. For a nice (light-tailed) distribution, sample mean has exponential concentration by Hoeffding's inequality. But what if the distribution is heavy-tailed? One might wonder if exponential-concentration is even possible because empirical mean can shown to be pretty wild. Turns out it is indeed possible!

I will talk about variety of estimators which achieve exponential concentration even for heavy-tailed distributions, starting from single dimension, then extending it to multiple dimensions, and finally high dimensions (infinite dimensions).

These estimators are very simple to state and follow the philosophy of "median of means". I will present estimators from multiple papers without going into a lot of proofs.

Couple of papers on this topic:
Â1. Bandits with heavy tails: https://arxiv.org/abs/1209.1727

Â2. Geometric median and robust estimation in Banach spaces: https://arxiv.org/abs/1308.1334

Time and place: 04/03, 4pm, CS 3310

Thanks,

Ankit Pensia