A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates

Understand

We study the algorithmic problem of estimating the mean of heavy-tailed random vector in $\mathbb{R}^d$, given $n$ i.i.d.

• samples.
• The goal is to design an efficient estimator that attains the optimal sub-gaussian error bound, only assuming that the random vector has bounded mean and covariance.
• Polynomial-time solutions to this problem are known but have high runtime due to their use of semi-definite programming (SDP).