# Source Identification for Mixtures of Product Distributions

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2020.

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

- [Causal Inference Despite Limited Global Confounding via Mixture Models](https://mlsanity.com/paper/2112.11602/) (2021)
- [Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimation](https://mlsanity.com/paper/2204.00930/) (2022)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [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)
- [Causal Discovery in Mixtures of Populations](https://mlsanity.com/paper/2311.07454/) (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)
- [Identifiability of Product of Experts Models](https://mlsanity.com/paper/2310.09397/) (2023)
- [Synthetic Potential Outcomes and Causal Mixture Identifiability](https://mlsanity.com/paper/2405.19225/) (2024)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

We give an algorithm for source identification of a mixture of k product distributions on n bits. This is a fundamental problem in machine learning with many applications. Our algorithm identifies the source parameters of an identifiable mixture, given, as input, approximate values of multilinear moments (derived, for instance, from a sufficiently large sample), using 2O(k2) nO(k) arithmetic operations. Our result is the first explicit bound on the computational complexity of source identification of such mixtures. The running time improves previous results by Feldman, O'Donnell, and Servedio (FOCS 2005) and Chen and Moitra (STOC 2019) that guaranteed only learning the mixture (without parametric identification of the source). Our analysis gives a quantitative version of a qualitative characterization of identifiable sources that is due to Tahmasebi, Motahari, and Maddah-Ali (ISIT 2018).