Robustly learning mixtures of k arbitrary Gaussians

Ainesh Bakshi; Ilias Diakonikolas; He Jia; Daniel M. Kane; Pravesh K. Kothari; Santosh S. Vempala

doi:10.1145/3519935.3519953

Robustly learning mixtures of k arbitrary Gaussians

Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

24 Scopus citations

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.

Original language	English (US)
Title of host publication	STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Stefano Leonardi, Anupam Gupta
Publisher	Association for Computing Machinery
Pages	1234-1247
Number of pages	14
ISBN (Electronic)	9781450392648
DOIs	https://doi.org/10.1145/3519935.3519953
State	Published - Sep 6 2022
Externally published	Yes
Event	54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy Duration: Jun 20 2022 → Jun 24 2022

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Country/Territory	Italy
City	Rome
Period	6/20/22 → 6/24/22

All Science Journal Classification (ASJC) codes

Software

Keywords

Gaussian Mixture Model
Robust Statistics
Sum-of-Squares
Tensor Decomposition

Access to Document

10.1145/3519935.3519953

Cite this

Bakshi, A., Diakonikolas, I., Jia, H., Kane, D. M., Kothari, P. K., & Vempala, S. S. (2022). Robustly learning mixtures of k arbitrary Gaussians. In S. Leonardi, & A. Gupta (Eds.), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1234-1247). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3519935.3519953

@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",

}

Bakshi, A, Diakonikolas, I, Jia, H, Kane, DM, Kothari, PK & Vempala, SS 2022, Robustly learning mixtures of k arbitrary Gaussians. in S Leonardi & A Gupta (eds), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 1234-1247, 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, Rome, Italy, 6/20/22. https://doi.org/10.1145/3519935.3519953

Robustly learning mixtures of k arbitrary Gaussians. / Bakshi, Ainesh; Diakonikolas, Ilias; Jia, He et al.
STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Stefano Leonardi; Anupam Gupta. Association for Computing Machinery, 2022. p. 1234-1247 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Robustly learning mixtures of k arbitrary Gaussians

AU - Bakshi, Ainesh

AU - Diakonikolas, Ilias

AU - Jia, He

AU - Kane, Daniel M.

AU - Kothari, Pravesh K.

AU - Vempala, Santosh S.

PY - 2022/9/6

Y1 - 2022/9/6

N2 - 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.

AB - 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.

KW - Gaussian Mixture Model

KW - Robust Statistics

KW - Sum-of-Squares

KW - Tensor Decomposition

UR - http://www.scopus.com/inward/record.url?scp=85132763106&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132763106&partnerID=8YFLogxK

U2 - 10.1145/3519935.3519953

DO - 10.1145/3519935.3519953

M3 - Conference contribution

AN - SCOPUS:85132763106

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1234

EP - 1247

BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Leonardi, Stefano

A2 - Gupta, Anupam

PB - Association for Computing Machinery

T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022

Y2 - 20 June 2022 through 24 June 2022

ER -

Bakshi A, Diakonikolas I, Jia H, Kane DM, Kothari PK, Vempala SS. Robustly learning mixtures of k arbitrary Gaussians. In Leonardi S, Gupta A, editors, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2022. p. 1234-1247. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3519935.3519953

Robustly learning mixtures of k arbitrary Gaussians

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this