Mean Estimation with Sub-Gaussian Rates in Polynomial Time

Samuel B. Hopkins

We study polynomial time algorithms for estimating the mean of a heavy-tailed multivariate random vector. We assume only that the random vector $X$ has finite mean and covariance.…