ARC and Indo-US Virtual Center Seminar: Pravesh Kothari (CMU)

Algorithms & Randomness Center (ARC) and Indo-US Virtual Center Seminar

Pravesh Kothari (CMU)

Monday, June 8, 2020

Virtual via Bluejeans - 11:30 am


Title:  Outlier-robust Clustering of Gaussian Mixtures

Abstract:  We give efficient algorithms for robustly clustering of mixtures of "reasonable" distributions, including the well-known open problem of robustly clustering a mixture of arbitrary Gaussians. Specifically, we give an outlier-robust efficient algorithm for clustering a mixture of k Gaussians with pairwise TV distance 1-exp(k^k/\eta). The running time of our algorithm is d^{(k/\eta)^{O(k)}}. More generally, our algorithm succeeds for mixtures of distributions that satisfy two well-studied analytic assumptions - certifiable hypercontractivity and anti-concentration. Thus, it extends 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 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.

It remains open to improve the running time of the algorithms and to give a robust parameter estimation algorithm for Gaussian mixtures with no separation assumptions. 

Based on joint work with Ainesh Bakshi (CMU). 


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Event Details


  • Monday, June 8, 2020
    12:30 pm - 1:30 pm