Efficient Algorithms for Heavy-Tailed Mean EstimationSpeaker: Prayaag
Title: Efficient Algorithms for Heavy-Tailed Mean Estimation
Date: 07 Dec 2020 17:30-18:45 EST (talk starts at 17:45)
Abstract: In this talk, I will discuss the problem of estimating the mean of a heavy-tailed, high-dimensional distribution. Given iid samples, the goal is produce an estimate which has as small a confidence interval as possible. Standard estimators, such as the empirical mean, do not attain the optimal confidence interval size in the heavy-tailed setting. I will explain how the median-of-means estimator can be used to solve this problem. While statistically optimal, computing this estimator takes exponential time. I will then present a computationally efficient variant of this estimator which achieves the same statistical performance. This talk will focus on past work due to Lugosi and Mendelson, Hopkins, and Cherapanamjeri et al.. I will also briefly mention work on designing faster algorithms for this problem as well as other recent developments.