MEAN ESTIMATION WITH SUB-GAUSSIAN RATES IN POLYNOMIAL TIME

• 成果类型: Article
• 署名作者: Hopkins, Samuel B.
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/19-AOS1843
• 发表日期: 2020
• 页码: 1193-1213
• 关键词: robust estimation; sparse pca; semidefinite; relaxation; POWER; cut

摘要

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.