Robustly learning mixtures of k arbitrary Gaussians

DOI10.1145/3519935.3519953arXiv2012.02119OpenAlexW3110212018MaRDI QIDQ6083576FDOQ6083576

Authors: Ainesh Bakshi, Ilias Diakonikolas, Daniel M. Kane, Pravesh Kothari, Santosh S. Vempala 

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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 emph{tensor decomposition} algorithm that allows errors in both Frobenius norm and low-rank terms.

Full work available at URL: https://arxiv.org/abs/2012.02119

zbMATH Keywords

robust statisticsGaussian mixture modelsum-of-squarestensor decomposition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (4)

• Efficient Greedy Learning of Gaussian Mixture Models
• Gaussian mixtures closest to a given measure via optimal transport
• Learning mixtures of separated nonspherical Gaussians
• Robust Classification Under $\ell_0$ Attack for the Gaussian Mixture Model

This page was built for publication: Robustly learning mixtures of k arbitrary Gaussians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083576)