Mean Estimation with Sub-Gaussian Rates in Polynomial Time

Seminar | February 27 | 4-5 p.m. | 1011 Evans Hall

 Sam Hopkins, UC Berkeley

 Department of Statistics

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. 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-size confidence intervals under such mild assumptions. 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 (as with recent breakthrough work by Lugosi and Mendelson, 2019) are only known to be computable via brute-force search procedures requiring time exponential in the dimension.