Near-optimal sample complexity bounds for learning Latent k-polytopes and applications to Ad-Mixtures

Deriving Optimal bounds on Sample Complexity of Latent Variable models is an active area of research. Recently such bounds were obtained for Mixture of Gaussians (Ashtiani et al., 2018), no such results are known for Ad-mixtures, a generalization of Mixture distributions. In this paper we show that O * (dk/m) samples are sufficient to learn each of ktopic vectors of LDA, a popular Ad-mixture model, with vocabulary size d and m ∈ Ω(1) words per document, to any constant error in L 1 norm. The result is a corollary of the major contribution of this paper: the first sample complexity upper bound for the problem (introduced in (Bhattacharyya & Kannan, 2020)) of learning the vertices of a Latent k-Polytope in R d , given perturbed points from it. The bound, O * (dk/β), is optimal and linear in number of parameters. It applies to many stochastic models including a broad class Ad-mixtures. To demonstrate the generality of the approach we specialize the setting to Mixed Membership Stochastic Block Models(MMSB) and show for the first time that if an MMSB has k blocks, the sample complexity is O * (k 2 ) under usual assumptions. Introduction Recently, in a seminal paper, building on long line of research, (Ashtiani et al., 2018) showed that a mixture of k gaussians in R d can be recovered using O(number of parameters) iid samples drawn from the mixture.