{"success":1,"msg":"","color":"rgb(28, 35, 49)","title":"Robustly Learning Mixtures of (Clusterable) Gaussians via the SoS Proofs to Algorithms Method<\/b>","description":"webinar","title2":"","start":"2021-04-15 17:00","end":"2021-04-15 18:00","responsable":"Giacomo Zanella <\/i><\/a>","speaker":"Sam Hopkins (UC Berkeley)","id":"36","type":"webinar","timezone":"Europe\/Rome","activity":"zoom link and passcode will be available a few hours before the seminar at\r\nhttps:\/\/www.bidsa.unibocconi.eu\/wps\/wcm\/connect\/Site\/Bidsa\/Home\/News_Events\/BIDSA+Webinar+Spring+Series+2021+Hopkins","abstract":"Gaussian Mixture Models (GMMs) are the canonical generative models for non-homogeneous data: they have been studied in statistics and (later) computer science for more than 100 years. A seminal algorithm of Moitra and Vailiant shows that for every fixed k, mixtures of k Gaussians in d dimensions can be learned in time polynomial in d. However, this algorithm is highly non-robust: if the underlying distribution of samples is merely close to being a GMM (or if any samples are corrupted), their algorithm fails to learn the distribution. \r\nWe design and analyze a new, robust algorithm to learn high-dimensional GMMs, under the assumption that the mixture is clusterable ? that is, all pairs of Gaussians in the mixture have total variation distance close to 1. Prior robust algorithms for learning GMMs work only for spherical Gaussians ? that is, with covariance (upper bounded by) identity. \r\nIn this talk I will attempt to emphasize the SoS Proofs to Algorithms method which we use to design and analyze our algorithm. This method, which offers a mechanical way to turn a sufficiently simple proof of identifiability of parameters of a distribution into an efficient algorithm to learn those parameters, has proven to be exceptionally powerful in a wide range of high-dimensional statistics settings."}