Near Optimal Sample Complexity Bounds for Learning Latent k-polytopes and applications to Ad-Mixtures
12. července 2020
Řečníci
Chiranjib Bhattacharyya
Řečník · 0 sledujících
Ravindran Kannan
Řečník · 0 sledujících
O prezentaci
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…
Kategorie
Umělá inteligence a data science
Kategorie · 10,8k prezentací
Matematika
Kategorie · 2,4k prezentací
O organizátorovi (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.
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Active Learning on Graphs via Meta Learning
Zhlédnout později
Topological Autoencoders
Zhlédnout později
Michael Moor, …
Training Linear Neural Networks: Non-Local Convergence and Complexity Results
Zhlédnout později
AdaScale SGD: A User-Friendly Algorithm for Distributed Training
Zhlédnout později
Efficient Domain Generalization via Common-Specific Low-Rank Decomposition
Zhlédnout později
Leveraging Frequency Analysis for Deep Fake Image Recognition
Zhlédnout později
Joel Frank, …