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 R d and a parameter 0 < α < 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 listdecodable mean estimation, achieving nearly-optimal statistical guarantees, with running time O(n 1+ǫ0 d), for any fixed ǫ 0 > 0. All prior algorithms for this problem had additional polynomial factors in 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 Ω(ndk). 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 weightsinspired potential decrease. We crucially leverage this new algorithmic framework in the context of the iterative multi-filtering technique of [DKS18, DKK20a], providing a method to simultaneously cluster and downsample points using one-dimensional projections -thus, bypassing the k-PCA subroutines required by prior algorithms.