Seminars

View all Seminars  |  Download ICal for this event

Robustly Learning Mixtures of Arbitrary Gaussians in Polynomial Time

Series: Bangalore Theory Seminars

Speaker: Santosh VempalaGeorgia Tech

Date/Time: Dec 02 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
The Gaussian Mixture Model (Pearson 1894) is widely used for high-dimensional data. While classical results establish its unique identifiability, it was shown in 2010 (Kalai-Moitra-Valiant, Belkin-Sinha) that for any fixed number of component Gaussians, the underlying mixture parameters can be estimated to arbitrary accuracy in polynomial time. Robust Statistics (Huber 1964) asks for estimation of underlying models robustly, i.e., even if a bounded fraction of data is noisy, possibly chosen adversarially. This goal seemed to be computationally intractable, even for estimating the mean of nice distributions, till 2016 (Diakonikolas-Kamath-Kane-Li-Moitra-Stewart, Lai-Rao-Vempala). These methods were extended to many problems, but the robust estimation of GMMs remained a central open problem. In this talk, we will present the first polytime algorithm for any fixed number of components with no assumptions on the underlying mixture. The techniques developed, clustering using convex relaxations and approximate tensor decomposition allowing for error in both Frobenius norm and low-rank terms, might be useful more generally.


Speaker Website Link


Microsoft teams link:

<a href="Link

Hosts: Aditya Abhay Lonkar, Rahul Madhavan and Rameesh Paul