Sam Hopkins: How to Estimate the Mean of a Heavy-Tailed Vector in Polynomial Time

Tuesday, April 9, 2019 - 4:00pm to 5:00pm
Refreshments: 
Light Refreshments at 3:45pm
Location: 
Patil/Kiva G449
Speaker: 
Sam Hopkins, UC Berkeley

Abstract: 
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