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

Event Details
  • Date/Time:
    • Monday June 8, 2020
      11:30 am - 12:30 pm
  • Location: Virtual via Bluejeans
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Outlier-robust Clustering of Gaussian Mixtures - Virtual via Bluejeans at 11:30am

Full Summary: No summary paragraph submitted.

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:

Additional Information

In Campus Calendar


Invited Audience
Faculty/Staff, Postdoc, Graduate students, Undergraduate students
No keywords were submitted.
  • Created By: Francella Tonge
  • Workflow Status: Published
  • Created On: Jun 1, 2020 - 12:07pm
  • Last Updated: Jun 1, 2020 - 12:09pm