@inproceedings{0ea8d48662d44dd9b39d7d5cb8825918,

title = "Robustly learning mixtures of k arbitrary Gaussians",

abstract = "We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in g.,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 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.",

keywords = "Gaussian Mixture Model, Robust Statistics, Sum-of-Squares, Tensor Decomposition",

author = "Ainesh Bakshi and Ilias Diakonikolas and He Jia and Kane, {Daniel M.} and Kothari, {Pravesh K.} and Vempala, {Santosh S.}",

note = "Publisher Copyright: {\textcopyright} 2022 Owner/Author.; 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 ; Conference date: 20-06-2022 Through 24-06-2022",

year = "2022",

month = sep,

day = "6",

doi = "10.1145/3519935.3519953",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "1234--1247",

editor = "Stefano Leonardi and Anupam Gupta",

booktitle = "STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing",

}