# The Sparse Hausdorff Moment Problem, with Application to Topic Models

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

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

- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity](https://mlsanity.com/paper/2309.13993/) (2023)
- [Learning Polynomial Transformations](https://mlsanity.com/paper/2204.04209/) (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)

## Abstract (arXiv)

We consider the problem of identifying, from its first m noisy moments, a probability distribution on [0,1] of support k<∞. This is equivalent to the problem of learning a distribution on m observable binary random variables X1,X2,dots,Xm that are iid conditional on a hidden random variable U taking values in 1,2,dots,k. Our focus is on accomplishing this with m=2k, which is the minimum m for which verifying that the source is a k-mixture is possible (even with exact statistics). This problem, so simply stated, is quite useful: e.g., by a known reduction, any algorithm for it lifts to an algorithm for learning pure topic models. We give an algorithm for identifying a k-mixture using samples of m=2k iid binary random variables using a sample of size left(1/wminright)2 ·left(1/zetaright)O(k) and post-sampling runtime of only O(k2+o(1)) arithmetic operations. Here wmin is the minimum probability of an outcome of U, and zeta is the minimum separation between the distinct success probabilities of the Xis. Stated in terms of the moment problem, it suffices to know the moments to additive accuracy wmin·zetaO(k). It is known that the sample complexity of any solution to the identification problem must be at least exponential in k. Previous results demonstrated either worse sample complexity and worse O(kc) runtime for some c substantially larger than 2, or similar sample complexity and much worse kO(k2) runtime.