Robustly Learning Mixtures of $k$ Arbitrary Gaussians
Preprint
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.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Robust estimation via generalized quasi-gradientsInformation and Inference: A Journal of the IMA, 2021
- Robust Learning of Mixtures of Gaussians2021
- Learning sums of powers of low-degree polynomials in the non-degenerate case2020
- Robust Estimation via Robust Gradient EstimationJournal of the Royal Statistical Society Series B: Statistical Methodology, 2020
- Average Sensitivity and Noise Sensitivity of Polynomial Threshold FunctionsSIAM Journal on Computing, 2014
- Polynomial Learning of Distribution Families2010
- Settling the Polynomial Learnability of Mixtures of Gaussians2010
- Learning linear transformations2002
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- III. Contributions to the mathematical theory of evolutionProceedings of the Royal Society of London, 1894