IDEAL Workshop: Ainesh Bakshi, Robustly Learning a Mixture of k Arbitrary Gaussians

In this talk, we will describe a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in R^d, for any fixed k, in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem identified in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. We will provide a high-level overview of the main tools we establish in this work: an efficient “partial-clustering” algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.