Robustly learning mixtures of k arbitrary Gaussians

DOI10.1145/3519935.3519953MaRDI QIDQ6083576zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

Gaussian mixture modelrobust statisticssum-of-squarestensor decomposition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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.

Cited in

(9)

• Learning mixtures of separated nonspherical Gaussians
• Efficient Greedy Learning of Gaussian Mixture Models
• Robust Classification Under \ell₀ Attack for the Gaussian Mixture Model
• Gaussian mixtures closest to a given measure via optimal transport
• Solving unique games over globally hypercontractive graphs
• Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers
• Learning arithmetic formulas in the presence of noise: a general framework and applications to unsupervised learning
• Clustering a mixture of Gaussians with unknown covariance
• Mixtures of Gaussians are privately learnable with a polynomial number of samples

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)