Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation - Diakonikolas, Ilias; Kane, Daniel M.; Kongsgaard, Daniel; Li, Jerry; Tian, Kevin (STOC 2022, 2022)
We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. Specifically, we are given a set of points in and a parameter such that an -fraction of the points in are i.i.d. samples from a well-behaved distribution and the remaining -fraction are arbitrary. The goal is to output a small list of vectors, at least one of which is close to the mean of . We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees, with running time , for any fixed . All prior algorithms for this problem had additional polynomial factors in . We leverage this result, together with additional techniques, to obtain the first almost-linear time algorithms for clustering mixtures of separated well-behaved distributions, nearly-matching the statistical guarantees of spectral methods. Prior clustering algorithms inherently relied on an application of -PCA, thereby incurring runtimes of . This marks the first runtime improvement for this basic statistical problem in nearly two decades. The starting point of our approach is a novel and simpler near-linear time robust mean estimation algorithm in the regime, based on a one-shot matrix multiplicative weights-inspired potential decrease. We crucially leverage this new algorithmic framework in the context of the iterative multi-filtering technique of Diakonikolas et al. '18, '20, providing a method to simultaneously cluster and downsample points using one-dimensional projections – thus, bypassing the -PCA subroutines required by prior algorithms.