EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Robustly Learning Mixtures of k Arbitrary Gaussians

Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel Kane, Pravesh Kothari, Santosh Vempala

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →