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 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 Ω( n d k ). This marks the first runtime improvement for this basic statistical problem in nearly two decades.

Authors

• Ilias Diakonikolas
• Daniel M. Kane
• Daniel Kongsgaard
• Jerry Li 0001
• Kevin Tian

Keywords

• clustering
• list-decodable learning
• mixture models
• robust statistics