Uniform-weight parallel-pancake Gaussian mixtures cannot be efficiently distinguished from a standard Gaussian by statistical query algorithms unless quasi-polynomial accuracy is allowed, and a testing algorithm with similar quasi-polynomial cost exists when most mixture weights are equal.
Robustly Learning Mixtures of $k$ Arbitrary Gaussians
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
cs.LG 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On Learning Parallel Pancakes with Mostly Uniform Weights
Uniform-weight parallel-pancake Gaussian mixtures cannot be efficiently distinguished from a standard Gaussian by statistical query algorithms unless quasi-polynomial accuracy is allowed, and a testing algorithm with similar quasi-polynomial cost exists when most mixture weights are equal.