# Learning Arbitrary Statistical Mixtures of Discrete Distributions

arXiv: https://arxiv.org/abs/1504.02526 · HTML: https://mlsanity.com/paper/1504.02526/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2015.

## Built on by (most cited first, 4 of 4)

- [Hadamard Extensions and the Identification of Mixtures of Product Distributions](https://mlsanity.com/paper/2101.11688/) (2021)
- [Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity](https://mlsanity.com/paper/2309.13993/) (2023)
- [Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures](https://mlsanity.com/paper/2203.15150/) (2022)
- [Efficient Algorithms for Sparse Moment Problems without Separation](https://mlsanity.com/paper/2207.13008/) (2022)

## Abstract (arXiv)

We study the problem of learning from unlabeled samples very general statistical mixture models on large finite sets. Specifically, the model to be learned, vartheta, is a probability distribution over probability distributions p, where each such p is a probability distribution over [n] = 1,2,dots,n. When we sample from vartheta, we do not observe p directly, but only indirectly and in very noisy fashion, by sampling from [n] repeatedly, independently K times from the distribution p. The problem is to infer vartheta to high accuracy in transportation (earthmover) distance. We give the first efficient algorithms for learning this mixture model without making any restricting assumptions on the structure of the distribution vartheta. We bound the quality of the solution as a function of the size of the samples K and the number of samples used. Our model and results have applications to a variety of unsupervised learning scenarios, including learning topic models and collaborative filtering.