Beyond the low-degree algorithm: mixtures of subcubes and their applications
Sitan Chen, Ankur Moitra · 2019
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 nO(logk)-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.