CMSA Probability Seminar: Outlier-Robust Algorithms for Clustering Non-Spherical Mixtures

In this talk, we describe the first polynomial time algorithm for robustly clustering a mixture of statistically-separated, high-dimensional Gaussians. Prior to our work this question was open even in the special case of 2 components in the mixture. Our main conceptual contribution is distilling analytic properties of distributions, namely hyper-contractivity of degree-two polynomials and anti-concentration of linear projections, which are necessary and sufficient for clustering.

Based on joint work with Pravesh Kothari.