Learning Mixtures of Product Distributions via Higher Multilinear Moments

Abstract: Learning mixtures of k binary product distributions is a central problem in computational learning theory, but one where there are wide gaps between the best known algorithms and lower bounds (even for restricted families of algorithms). We narrow many of these gaps by developing novel insights about how to reason about higher order multilinear moments. Our results include: 1) an n^{O(k^2)} time algorithm for learning mixtures of binary product distributions, giving the first improvement on the n^{O(k^3)} time algorithm of Feldman, O'Donnell and Servedio (FOCS '05), 2) an n^{\Omega(\sqrt{k})} statistical query lower bound, improving on the quasipolynomial lower bound that is based on connections to sparse parity with noise, and 3) a quasipolynomial time algorithm for learning mixtures of $k$ subcubes. This special case can still simulate many other hard learning problems, but is much richer than any of them alone. As a corollary, we obtain more flexible algorithms for learning decision trees under the uniform distribution, that work with stochastic transitions, when we are only given positive examples and with a polylogarithmic number of samples for any fixed k.

Joint work with Ankur Moitra.