@inproceedings{diakonikolas2021list-decodable,
author = {Diakonikolas, Ilias and Kane, Daniel and Kongsgaard, Daniel and Li, Jerry and Tian, Kevin},
title = {List-Decodable Mean Estimation in Nearly-PCA Time},
booktitle = {NeurIPS 2021},
year = {2021},
month = {December},
abstract = {Traditionally, robust statistics has focused on designing estimators tolerant to a minority of contaminated data. Robust list-decodable learning focuses on the more challenging regime where only a minority  fraction of the dataset is drawn from the distribution of interest, and no assumptions are made on the remaining data. We study the fundamental task of list-decodable mean estimation in high dimensions. Our main result is a new list-decodable mean estimation algorithm for bounded covariance distributions with optimal sample complexity and error rate, running in nearly-PCA time. Assuming the ground truth distribution on  has bounded covariance, our algorithm outputs a list of  candidate means, one of which is within distance  from the truth. Our algorithm runs in time  for all , where  is the size of the dataset. We also show that a variant of our algorithm has runtime  for all , at the expense of an  factor in the recovery guarantee. This runtime matches up to logarithmic factors the cost of performing a single -PCA on the data, which is a natural bottleneck of known algorithms for (very) special cases of our problem, such as clustering well-separated mixtures. Prior to our work, the fastest list-decodable mean estimation algorithms had runtimes  and .
Our approach builds on a novel soft downweighting method, SIFT, which is arguably the simplest known polynomial-time mean estimation technique in the list-decodable learning setting. To develop our fast algorithms, we boost the computational cost of SIFT via a careful "win-win-win" analysis of an approximate Ky Fan matrix multiplicative weights procedure we develop, which we believe may be of independent interest.},
url = {http://approjects.co.za/?big=en-us/research/publication/list-decodable-mean-estimation-in-nearly-pca-time/},
}