2012/12/07 by Yuval Rabani, Rabani, Yuval, Leonard J. Schulman +4 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #F.2.2 #FOS: Computer and information sciences #G.2 #G.3 #Machine Learning (cs.LG) #Machine Learning and Algorithms #Text and Document Classification Technologies #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.1212.1527
Update of previous version with improved aperture and sample-size lower bounds
openalex publication_date 2012/12/07 · arxiv created 2013/09/18 · arxiv updated 2013/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give an algorithm for learning a mixture of \em unstructured distributions. This problem arises in various unsupervised learning scenarios, for example in learning \em topic models from a corpus of documents spanning several topics. We show how to learn the constituents of a mixture of k arbitrary distributions over a large discrete domain [n]=\1,2,…,n\ and the mixture weights, using O(n\polylog n) samples. (In the topic-model learning setting, the mixture constituents correspond to the topic distributions.) This task is information-theoretically impossible for k>1 under the usual sampling process from a mixture distribution. However, there are situations (such as the above-mentioned topic model case) in which each sample point consists of several observations from the same mixture constituent. This number of observations, which we call the \em "sampling aperture", is a crucial parameter of the problem. We obtain the \em first bounds for this mixture-learning problem \em without imposing any assumptions on the mixture constituents. We show that efficient learning is possible exactly at the information-theoretically least-possible aperture of 2k-1. Thus, we achieve near-optimal dependence on n and optimal aperture. While the sample-size required by our algorithm depends exponentially on k, we prove that such a dependence is \em unavoidable when one considers general mixtures. A sequence of tools contribute to the algorithm, such as concentration results for random matrices, dimension reduction, moment estimations, and sensitivity analysis.