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


View Calendar
November 16, 2022 3:30 pm - 4:30 pm
CMSA, 20 Garden St, G10
Address: 20 Garden Street, Cambridge, MA 02138

Ainesh Bakshi - MIT

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.