Robustly Learning Mixtures of k Arbitrary Gaussians
Journal of the ACM · 30.06.2026 · 73 (3) · 1-100
DOI: 10.1145/3804445 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 17.06.2026. Verfasst von Ainesh Bakshi und 5 weiteren Autor:innen. Die Arbeit nennt 73 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Office of Naval Research, National Science Foundation, DARPA Learning with Less Labels.
Abstract (Originalsprache)
We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in ℝ 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.
Förderung
- Office of Naval Research
- National Science Foundation
- DARPA Learning with Less Labels
- NSF
Zitieren
APA
Bakshi, A., Diakonikolas, I., Jia, H., Kane, D., Kothari, P., & Vempala, S. (2026). Robustly Learning Mixtures of k Arbitrary Gaussians. Journal of the ACM, 73(3), 1-100. https://doi.org/10.1145/3804445
Vancouver
Bakshi A, Diakonikolas I, Jia H, Kane D, Kothari P, Vempala S. Robustly Learning Mixtures of k Arbitrary Gaussians. Journal of the ACM. 2026;73(3):1-100. doi:10.1145/3804445
BibTeX
@article{Bakshi2026,
author = {Bakshi, Ainesh and Diakonikolas, Ilias and Jia, He and Kane, Daniel and Kothari, Pravesh and Vempala, Santosh},
title = {Robustly Learning Mixtures of k Arbitrary Gaussians},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {3},
pages = {1--100},
doi = {10.1145/3804445}
}
EUVIMED