{"635860":{"#nid":"635860","#data":{"type":"event","title":"ARC and Indo-US Virtual Center Seminar: Pravesh Kothari (CMU)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) and Indo-US Virtual Center Seminar\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EPravesh Kothari (CMU)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, June 8, 2020\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EVirtual via Bluejeans - 11:30 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp; \u003C\/strong\u003EOutlier-robust Clustering of Gaussian Mixtures\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EWe give efficient algorithms for robustly clustering of mixtures of \u0026quot;reasonable\u0026quot; distributions, including the well-known open problem of robustly clustering a mixture of arbitrary Gaussians. Specifically, we\u0026nbsp;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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIt 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.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBased on joint work with Ainesh Bakshi (CMU).\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.cs.princeton.edu\/~kothari\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Outlier-robust Clustering of Gaussian Mixtures - Virtual via Bluejeans at 11:30am"}],"uid":"27544","created_gmt":"2020-06-01 16:07:20","changed_gmt":"2020-06-01 16:09:23","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2020-06-08T12:30:00-04:00","event_time_end":"2020-06-08T13:30:00-04:00","event_time_end_last":"2020-06-08T13:30:00-04:00","gmt_time_start":"2020-06-08 16:30:00","gmt_time_end":"2020-06-08 17:30:00","gmt_time_end_last":"2020-06-08 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}