Near Optimal Sample Complexity Bounds for Learning Latent k-polytopes and applications to Ad-Mixtures
Jul 12, 2020
Speakers
Chiranjib Bhattacharyya
Speaker · 0 followers
Ravindran Kannan
Speaker · 0 followers
About
Recently near-optimal bounds on sample complexity of Mixture of Gaussians was shown in the seminal paper <cit.>. 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∈Ω(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 <cit.>) of learning the vertices of a Latent k- Polytope in R^d, given perturbed points from it. The bound, O^*(dk/β), 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, β 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 Ω^*(dk/β) by a combinatorial construction based on a code-design. Our upper bound proof combines two novel methods. The first is 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 subset averaging which uses β to prove that the set of averages of all large subsets of data is a good candidate set.Recently near-optimal bounds on sample complexity of Mixture of Gaussians was shown in the seminal paper <cit.>. 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∈Ω(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 pr…
Categories
AI & Data Science
Category · 10.8k presentations
Mathematics
Category · 2.4k presentations
About ICML 2020
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Laguerre-Gauss Preprocessing: Line Profiles as Image Features
Watch later
Sharp Composition Bounds for Gaussian Differential Privacy via Edgeworth Expansion
Watch later
Feature Noise Induces Loss Discrepancy Across Groups
Watch later
Class Weighted Classification: Trade-offs and Robust Approaches
Watch later
Ziyu Xu, …
Implicit Class-Conditioned Domain Alignment for Unsupervised Domain Adaptation
Watch later
Xiang Jiang, …