Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation

We study the clustering problem for mixtures of bounded covariance distributions, under a fine-grained separation assumption. Specifically, given samples from a k-component mixture distribution D = sumi =1k wi Pi, where each wi ≥ α for some known parameter α, and each Pi has unknown covariance Sigmai preceq σ2i · Id for some unknown σi, the goal is to cluster the samples assuming a pairwise mean separation in the order of (σi+σj)/√α between every pair of components Pi and Pj. Our contributions are as follows: For the special case of nearly uniform mixtures, we give the first poly-time algorithm for this clustering task. Prior work either required separation scaling with the maximum cluster standard deviation (i.e. maxi σi) [DKK+22b] or required both additional structural assumptions and mean separation scaling as a large degree polynomial in 1/α [BKK22]. For general-weight mixtures, we point out that accurate clustering is information-theoretically impossible under our fine-grained mean separation assumptions. We introduce the notion of a clustering refinement -- a list of not-too-small subsets satisfying a similar separation, and which can be merged into a clustering approximating the ground truth -- and show that it is possible to efficiently compute an accurate clustering refinement of the samples. Furthermore, under a variant of the "no large sub-cluster'' condition from in prior work [BKK22], we show that our algorithm outputs an accurate clustering, not just a refinement, even for general-weight mixtures. As a corollary, we obtain efficient clustering algorithms for mixtures of well-conditioned high-dimensional log-concave distributions. Moreover, our algorithm is robust to Omega(α)-fraction of adversarial outliers.