Near-optimal sample complexity bounds for learning Latent $k-$polytopes and applications to Ad-Mixtures
Recently near-optimal bounds on sample complexity of Mixture of Gaussians was shown in the seminal paper \cite{HSNCAY18}. No such results are known for Ad-mixtures. In this paper we show that $O^*(dk/m)$ samples are sufficient to learn each of $k-$ topic vectors of LDA, a popular Ad-mixture model, with vocabulary size $d$ and $m\in \Omega(1)$ words per document, to any constant error in $L_1$ norm. This is a corollary of the major contribution of the current paper: the first sample complexity upper bound for the problem (introduced in \cite{BK20}) of learning the vertices of a Latent $k-$ Polytope in ${\bf R}^d$, given perturbed points from it. The bound, $O^*(dk/\beta)$, is optimal and applies to many stochastic models including LDA, Mixed Membership block Models(MMBM),Dirichlet Simplex Nest, and large class of Ad-mixtures. The parameter, $\beta$ depends on the probability laws governing individual models and in many cases can be expressed very succintly, e.g. it is equal to the average degree of each node for MMBM, and equal to $m$ in LDA. The tightness is proved by a nearly matching lower of $\Omega^*(dk/\beta)$ by a combinatorial construction based on a code-design. Our upper bound proof combines two novel methods. The first is {\it vertex set certification} which, for any $k-$polytope $K$ gives convex geometry based sufficient conditions for a set of $k$ points from a larger candidate set to be close in Hausdorff distance to the set of $k$ vertices of the polytope. The second is {\it subset averaging} which uses $\beta$ to prove that the set of averages of all large subsets of data is a good candidate set.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
PAC Reinforcement Learning for Predictive State Representations
In this paper we study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-kn…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Finite-Sample Analysis of Nonlinear Independent Component Analysis:Sample Complexity and Identifiability Bounds
Independent Component Analysis (ICA) is a fundamental unsupervised learning technique foruncovering latent structure in data by separating mixed signals into their independent sources. While substantial progress has been…
Sample-Adaptivity Tradeoff in On-Demand Sampling
We study the tradeoff between sample complexity and round complexity in on-demand sampling, where the learning algorithm adaptively samples from $k$ distributions over a limited number of rounds. In the realizable settin…
Near-Optimal Sample Complexity Bounds for Constrained MDPs
In contrast to the advances in characterizing the sample complexity for solving Markov decision processes (MDPs), the optimal statistical complexity for solving constrained MDPs (CMDPs) remains unknown. We resolve this q…
Bilinear Classes: A Structural Framework for Provable Generalization in RL
This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function approximation. The framework incorporates…