# Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 39 references that are in the map.
- First posted on arXiv 25 Sep 2023.

## Builds on (most cited first, 8 of 8)

- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications](https://mlsanity.com/paper/1803.06521/) (2018)
- [Source Identification for Mixtures of Product Distributions](https://mlsanity.com/paper/2012.14540/) (2020)
- [Causal Inference Despite Limited Global Confounding via Mixture Models](https://mlsanity.com/paper/2112.11602/) (2021)
- [Fourier PCA and Robust Tensor Decomposition](https://mlsanity.com/paper/1306.5825/) (2013)
- [The Sparse Hausdorff Moment Problem, with Application to Topic Models](https://mlsanity.com/paper/2007.08101/) (2020)
- [Learning Arbitrary Statistical Mixtures of Discrete Distributions](https://mlsanity.com/paper/1504.02526/) (2015)
- [Hadamard Extensions and the Identification of Mixtures of Product Distributions](https://mlsanity.com/paper/2101.11688/) (2021)

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

- [Causal Discovery in Mixtures of Populations](https://mlsanity.com/paper/2311.07454/) (2023)
- [Synthetic Potential Outcomes and Causal Mixture Identifiability](https://mlsanity.com/paper/2405.19225/) (2024)
- [Learning Mixtures of Unknown Causal Interventions](https://mlsanity.com/paper/2411.00213/) (2024)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

We consider the problem of identifying, from statistics, a distribution of discrete random variables X1,ldots,Xn that is a mixture of k product distributions. The best previous sample complexity for n ∈ O(k) was (1/zeta)O(k2 log k) (under a mild separation assumption parameterized by zeta). The best known lower bound was exp(Omega(k)). It is known that n≥ 2k-1 is necessary and sufficient for identification. We show, for any n≥ 2k-1, how to achieve sample complexity and run-time complexity (1/zeta)O(k). We also extend the known lower bound of eOmega(k) to match our upper bound across a broad range of zeta. Our results are obtained by combining (a) a classic method for robust tensor decomposition, (b) a novel way of bounding the condition number of key matrices called Hadamard extensions, by studying their action only on flattened rank-1 tensors.