Mean estimation with sub-Gaussian rates in polynomial time
The Annals of Statistics · 2020 · Volume 48 · Issue 2
Abstract
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 are only known to be computable via brute-force search procedures requiring time exponential in the dimension.
Keywords
62H12, 68W, confidence intervals, heavy tails, multivariate estimation, semidefinite programming, sub-Gaussian rates, sum of squares method
Enable JavaScript for citation tools and additional paper interactions.