Settling the Robust Learnability of Mixtures of Gaussians
It solves a foundational problem in machine learning for robust statistics, enabling reliable learning of Gaussian mixtures in noisy or adversarial settings.
The paper tackles the problem of provably robust learning of mixtures of Gaussians, achieving the first algorithm that works for any constant number of components under mild assumptions, with dimension-independent polynomial identifiability.
This work represents a natural coalescence of two important lines of work: learning mixtures of Gaussians and algorithmic robust statistics. In particular we give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. We require only mild assumptions on the mixing weights (bounded fractionality) and that the total variation distance between components is bounded away from zero. At the heart of our algorithm is a new method for proving dimension-independent polynomial identifiability through applying a carefully chosen sequence of differential operations to certain generating functions that not only encode the parameters we would like to learn but also the system of polynomial equations we would like to solve. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.