Mean Estimation with Sub-Gaussian Rates in Polynomial Time

2018/09/19 by Hopkins, Samuel B. · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1809.07425

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.

Cited by

• Improved Concentration for Mean Estimators via Shrinkage
• Shadow Tomography Against Adversaries
• Empirical Orlicz norms
• Adversarially robust quantum state learning and testing

Related

• Fast Mean Estimation with Sub-Gaussian Rates
• A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates
• Sub-Gaussian estimators of the mean of a random vector
• Algorithms for Heavy-Tailed Statistics: Regression, Covariance\n Estimation, and Beyond
• Robust subgaussian estimation of a mean vector in nearly linear time