*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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).
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
