Sam Hopkins: How to Estimate the Mean of a Heavy-Tailed Vector in Polynomial Time
Sam Hopkins, UC Berkeley
Date: Tuesday, April 09, 2019
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Event Type: Seminar
Host: Ankur Moitra
Contact: Deborah Goodwin, 617.324.7303, firstname.lastname@example.org
Speaker URL: None
TALK: Sam Hopkins: How to Estimate the Mean of a Heavy-Tailed Vector in Polynomial Time
We study polynomial time algorithms for estimating the mean of a multivariate random vector under very mild assumptions: we assume only that the random vector X has finite mean and covariance. This allows for X to be heavy-tailed. In this setting, the radius of confidence intervals achieved by the empirical mean are exponentially larger in the case that X is Gaussian or sub-Gaussian. That is, the empirical mean is poorly concentrated.
We offer the first polynomial time algorithm to estimate the mean of X with sub-Gaussian-size confidence intervals under such mild assumptions. That is, our estimators are exponentially better-concentrated than the empirical mean. Our algorithm is based on a new semidefinite programming relaxation of a high-dimensional median. Previous estimators which assumed only existence of finitely-many moments of X either sacrifice sub-Gaussian performance or are only known to be computable via brute-force search procedures requiring time exponential in the dimension.
Based on https://arxiv.org/abs/1809.07425 to appear in Annals of Statistics
Created by Deborah Goodwin at Friday, April 05, 2019 at 2:15 PM.