List-Decodable Mean Estimation via Iterative Multi-Filtering
  We study the problem of {\em list-decodable mean estimation} for bounded
covariance distributions. Specifically, we are given a set $T$ of points in
$\mathbb{R}^d$ with the promise that an unknown $\alpha$-fraction of points in
$T$, where $0< \alpha < 1/2$, are drawn from an unknown mean and bounded
covariance distribution $D$, and no assumptions are made on the remaining
points. The goal is to output a small list of hypothesis vectors such that at
least one of them is close to the mean of $D$. We give the first practically
viable estimator for this problem. In more detail, our algorithm is sample and
computationally efficient, and achieves information-theoretically near-optimal
error. While the only prior algorithm for this setting inherently relied on the
ellipsoid method, our algorithm is iterative and only uses spectral techniques.
Our main technical innovation is the design of a soft outlier removal procedure
for high-dimensional heavy-tailed datasets with a majority of outliers.
