Mean estimation with sub-Gaussian rates in polynomial time (Q2196216)

The author studies polynomial time algorithms for estimating the mean of a heavy-tailed multivariate random vector. The only assumption is 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. A polynomial time algorithm is proposed to estimate the mean with sub-Gaussian-size confidence intervals under these assumptions. The 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. The algorithm runs in polynomial time, but it is not close to practical for any substantially high-dimensional data set.