Learning Mixtures of Discrete Product Distributions using Spectral Decompositions

Abstract

We study the problem of learning a distribution from samples, when the underlying distribution is a mixture of product distributions over discrete domains. This problem is motivated by several practical applications such as crowd-sourcing, recommendation systems, and learning Boolean functions. The existing solutions either heavily rely on the fact that the number of components in the mixtures is finite or have sample/time complexity that is exponential in the number of components. In this paper, we introduce a polynomial time/sample complexity method for learning a mixture of $r$ discrete product distributions over $\{1,2,\dots ,\ell {\}}^n$, for general $\ell$ and $r$. We show that our approach is statistically consistent and further provide finite sample guarantees. We use techniques from the recent work on tensor decompositions for higher-order moment matching. A crucial step in these moment matching methods is to construct a certain matrix and a certain tensor with low-rank spectral decompositions. These tensors are typically estimated directly from the samples. The main challenge in learning mixtures of discrete product distributions is that these low-rank tensors cannot be obtained directly from the sample moments. Instead, we reduce the tensor estimation problem to: $a$) estimating a low-rank matrix using only off-diagonal block elements; and $b$) estimating a tensor using a small number of linear measurements. Leveraging on recent developments in matrix completion, we give an alternating minimization based method to estimate the low-rank matrix, and formulate the tensor completion problem as a least-squares problem.

30 pages no figures

Cited by in corpus (9)

• Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing
• Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
• A Deep Learning Approach to Unsupervised Ensemble Learning
• Learning Mixtures of Gaussians in High Dimensions
• Learning Mixed Multinomial Logit Model from Ordinal Data
• Unsupervised Ensemble Learning with Dependent Classifiers
• Adversarial Top-$K$ Ranking
• Reinforcement Learning in Reward-Mixing MDPs
• Feature Selection Facilitates Learning Mixtures of Discrete Product Distributions