We give the first outlier-robust efficient algorithm for clustering a mixture of k statistically separated d-dimensional Gaussians (k-GMMs). Concretely, our algorithm takes input an \epsilon-corrupted sample from a k-GMM and (k/\eta)} time, } outputs an approximate clustering that misclassifies at most O(k\epsilon)(\epsilon} +\eta  fraction of the points whenever every pair of components is separated by 1-\exp(- poly (k/\eta)  ) in total variation distance. This is the statistically weakest possible notion of separation and allows, for e.g., clusteringof mixtures with components with the same mean with covariances differing in a single unknown direction or separated in Frobenius distance. The running time of our algorithm is d^{O(\log(\kappa)) \textrm{poly(k/\eta)} where \kappa is a measure of spread of the mixture in any direction. For k=2, our algorithms run in time and samples }poly (d) with no dependence on the spread \kappa. Such a results were not known prior to our work, even for k=2. More generally, our algorithm succeeds for mixtures of any distribution that satisfies two well-studied analytic assumptions - certifiable hypercontractivity and anti-concentration . Thus, they extend to clustering mixtures of arbitrary affine transforms of the uniform distribution on the d-dimensional unit sphere. Even the information theoretic clusterability of distributions satisfying our analytic assumptions was not known  and is likely to be of independent interest. Our algorithms build on the recent flurry of work relying on certifiable anti-concentration , first introduced in [KKK'19,RY'20]. Our techniques expand the sum-of-squares toolkit to show robust certifiability of TV-separated Gaussian clusters in data. This involves  a low-degree sum-of-squares proof of statements that relate parameter  distance to total variation distance simply relying on hypercontractivity and anti-concentration.
We give the first outlier-robust efficient algorithm for clustering a mixture of k statistically separated d-dimensional Gaussians (k-GMMs). Concretely, our algorithm takes input an \epsilon-corrupted sample from a k-GMM and whp in d^{\text{poly(k/\eta)} time, } outputs an approximate clustering that misclassifies at most k^{O(k)(\epsilon} +\eta ) fraction of the points whenever every pair of mixture components are separated by 1-\exp(- \text{poly (k/\eta) ^k ) in total variation (TV) distance. Such a result was not previously known even for k=2. TV separation is the statistically weakest possible notion of separation and (k/\eta)} where \kappa is a measure of spread of the mixture in any direction. For k=2, our algorithms run in time and samples } captures important special cases such as mixed linear regression and subspace clustering. Our main conceptual contribution is to distill two simple analytic properties - (certifiable) hypercontractivity and anti-concentration - that are necessary and sufficient for mixture models to be (efficiently) clusterable. As a consequence, our results extend to clustering mixtures of arbitrary affine transforms of the uniform distribution on the d-dimensional unit sphere. Even the information theoretic clusterability of separated distributions satisfying these two analytic assumptions was not known prior to our work and is likely to be of independent interest. Our algorithms build on the recent sequence of works relying on certifiable anti-concentration first introduced in [KKK'19,RY'20]. Our techniques expand the sum-of-squares toolkit to show robust certifiability of TV-separated Gaussian clusters in data. This involves giving a low-degree sum-of-squares proof of statements that relate parameter (i.e. mean and covariances) distance to total variation distance by relying only on hypercontractivity and anti-concentration.
A
whp in d^{\text{poly
R
O(k\epsilon)
k^{O(k)
A
)
R
components is
mixture components are
R
poly
\text{poly
A
^k
R
distance. This
(TV) distance. Such a result was not previously known even for k=2. TV separation
D
allows, for e.g., clusteringof mixtures with components with the same mean with covariances differing in a single unknown direction or separated in Frobenius distance. The running time of our algorithm is d^{O(\log(\kappa)) \textrm{poly
D
poly
R
(d) with no dependence on the spread \kappa. Such a results were not known prior to our work, even for k=2. More generally, our algorithm succeeds for mixtures of any distribution that satisfies two well-studied analytic assumptions
captures important special cases such as mixed linear regression and subspace clustering. Our main conceptual contribution is to distill two simple analytic properties
R
certifiable
(certifiable)
R
. Thus, they
- that are necessary and sufficient for mixture models to be (efficiently) clusterable. As a consequence, our results
R
distributions satisfying our
separated distributions satisfying these two
A
prior to our work
R
flurry of work
sequence of works
D
,
A
giving
A
(i.e. mean and covariances)
R
simply relying
by relying only