Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation

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 T of n points in ℝd and a parameter 0< α <frac 1 2 such that an α-fraction of the points in T are i.i.d. samples from a well-behaved distribution D and the remaining (1-α)-fraction are arbitrary. The goal is to output a small list of vectors, at least one of which is close to the mean of D. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees, with running time O(n1 + ε0 d), for any fixed ε0 > 0. All prior algorithms for this problem had additional polynomial factors in frac 1 α. We leverage this result, together with additional techniques, to obtain the first almost-linear time algorithms for clustering mixtures of k separated well-behaved distributions, nearly-matching the statistical guarantees of spectral methods. Prior clustering algorithms inherently relied on an application of k-PCA, thereby incurring runtimes of Omega(n d k). 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 α → 1 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 k-PCA subroutines required by prior algorithms.