Abstract
We study polynomial time algorithms for estimating the mean of a d-dimensional random vector X from n independent samples X1,?,Xn when X may be heavy-tailed. In particular, we assume only that X has finite mean and covariance. In this setting, the radius of confidence intervals achieved by the empirical mean are large compared to the case that X is Gaussian or sub-Gaussian. We offer the first polynomial time algorithm to estimate the mean with sub-Gaussian-style confidence intervals even when X has only finite second moments. Our algorithm is based on a new semidefinite programming relaxation of a high-dimensional median. Previous estimators which assumed only existence of O(1) moments of X either sacrifice sub-Gaussian performance or are only known to be computable via brute-force search procedures requiring exp(d) time.