Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications

Understand

We introduce the problem of learning mixtures of $k$ subcubes over $\{0,1\}^n$, which contains many classic learning theory problems as a special case (and is itself a special case of others).

• We give a surprising $n^{O(\log k)}$-time learning algorithm based on higher-order multilinear moments.
• It is not possible to learn the parameters because the same distribution can be represented by quite different models.
• Instead, we develop a framework for reasoning about how multilinear moments can pinpoint essential features of the mixture, like the number of components.