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

[Aubrey Barnard <barnard@xxxxxxxxxxx>]

AIRG,

This afternoon Ankit Pensia will be introducing us to estimation for 
heavy-tailed distributions, which are important because there are plenty 
of things in the world that are not Gaussian. For example, the Cauchy 
distribution describes the incidence on a line of rays emitted from a 
fixed point, and is so heavy tailed as to not have a mean. The issue of 
heavy tails has also been addressed in the popular press, in books such 
as "The Black Swan: The Impact of the Highly Improbable", where the 
author espouses the ubiquity of power laws and their distributions 
(which have heavier tails than Gaussians).

4pm, CS 3310

Power law: https://en.wikipedia.org/wiki/Power_law
Paper 2: http://dx.doi.org/10.3150/14-BEJ645
Paper 1: https://doi.org/10.1109/TIT.2013.2277869 / 
https://ieeexplore-ieee-org.ezproxy.library.wisc.edu/document/6576820 / 
https://www.microsoft.com/en-us/research/wp-content/uploads/2017/01/BCL13.pdf

Aubrey

P.S. If you need access to subscription publications (e.g. IEEE) from 
off campus, you can append ".ezproxy.library.wisc.edu" to the domain 
name in the URL and log in with your NetID. This will give you access to 
publications the University subscribes to.
https://www.library.wisc.edu/help/off-campus-access/
https://www.library.wisc.edu/help/off-campus-access/remote-access-bookmarklet/


On 4/1/19 10:39 AM, Ankit Pensia wrote:
> 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
> 
> _______________________________________________
> AIRG mailing list
> AIRG@xxxxxxxxxxx
> https://lists.cs.wisc.edu/mailman/listinfo/airg
>