The Sparse Hausdorff Moment Problem, with Application to Topic Models

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.