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 = k i=1 w i P i , where each w i ≥ α for some known parameter α, and each P i has unknown covariance Σ i ⪯ σ 2 i • I d 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 P i and P j . Our main contributions are as follows: