Robustly Learning Mixtures of $k$ Arbitrary Gaussians

Authors:
  • ABAinesh Bakshi
    Ainesh Bakshi
  • IDIlias Diakonikolas
    Ilias Diakonikolas
  • HJHe Jia
    He Jia
  • DKDaniel M. Kane
    Daniel M. Kane
  • PKPravesh K. Kothari
    Pravesh K. Kothari
  • SVSantosh S. Vempala
    Santosh S. Vempala

Abstract
We give a polynomial-time algorithm for the problem of robustly estimating a mixture of $k$ arbitrary Gaussians in $\mathbb{R}^d$, for any fixed $k$, in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem 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. Our main tools are an efficient \emph{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.