Learning Overcomplete Latent Variable Models through Tensor Methods

Animashree Anandkumar, Rong Ge, Majid Janzamin
Proceedings of The 28th Conference on Learning Theory, PMLR 40:36-112, 2015.

Abstract

We provide guarantees for learning latent variable models emphasizing on the overcomplete regime, where the dimensionality of the latent space exceeds the observed dimensionality. In particular, we consider multiview mixtures, ICA, and sparse coding models. Our main tool is a new algorithm for tensor decomposition that works in the overcomplete regime. In the semi-supervised setting, we exploit label information to get a rough estimate of the model parameters, and then refine it using the tensor method on unlabeled samples. We establish learning guarantees when the number of components scales as k=o(d^p/2), where d is the observed dimension, and p is the order of the observed moment employed in the tensor method (usually p=3,4). In the unsupervised setting, a simple initialization algorithm based on SVD of the tensor slices is proposed, and the guarantees are provided under the stricter condition that k ≤βd (where constant βcan be larger than 1). For the learning applications, we provide tight sample complexity bounds through novel covering arguments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Anandkumar15, title = {Learning Overcomplete Latent Variable Models through Tensor Methods}, author = {Anandkumar, Animashree and Ge, Rong and Janzamin, Majid}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {36--112}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Anandkumar15.pdf}, url = {https://proceedings.mlr.press/v40/Anandkumar15.html}, abstract = {We provide guarantees for learning latent variable models emphasizing on the overcomplete regime, where the dimensionality of the latent space exceeds the observed dimensionality. In particular, we consider multiview mixtures, ICA, and sparse coding models. Our main tool is a new algorithm for tensor decomposition that works in the overcomplete regime. In the semi-supervised setting, we exploit label information to get a rough estimate of the model parameters, and then refine it using the tensor method on unlabeled samples. We establish learning guarantees when the number of components scales as k=o(d^p/2), where d is the observed dimension, and p is the order of the observed moment employed in the tensor method (usually p=3,4). In the unsupervised setting, a simple initialization algorithm based on SVD of the tensor slices is proposed, and the guarantees are provided under the stricter condition that k ≤βd (where constant βcan be larger than 1). For the learning applications, we provide tight sample complexity bounds through novel covering arguments. } }
Endnote
%0 Conference Paper %T Learning Overcomplete Latent Variable Models through Tensor Methods %A Animashree Anandkumar %A Rong Ge %A Majid Janzamin %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Anandkumar15 %I PMLR %P 36--112 %U https://proceedings.mlr.press/v40/Anandkumar15.html %V 40 %X We provide guarantees for learning latent variable models emphasizing on the overcomplete regime, where the dimensionality of the latent space exceeds the observed dimensionality. In particular, we consider multiview mixtures, ICA, and sparse coding models. Our main tool is a new algorithm for tensor decomposition that works in the overcomplete regime. In the semi-supervised setting, we exploit label information to get a rough estimate of the model parameters, and then refine it using the tensor method on unlabeled samples. We establish learning guarantees when the number of components scales as k=o(d^p/2), where d is the observed dimension, and p is the order of the observed moment employed in the tensor method (usually p=3,4). In the unsupervised setting, a simple initialization algorithm based on SVD of the tensor slices is proposed, and the guarantees are provided under the stricter condition that k ≤βd (where constant βcan be larger than 1). For the learning applications, we provide tight sample complexity bounds through novel covering arguments.
RIS
TY - CPAPER TI - Learning Overcomplete Latent Variable Models through Tensor Methods AU - Animashree Anandkumar AU - Rong Ge AU - Majid Janzamin BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Anandkumar15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 36 EP - 112 L1 - http://proceedings.mlr.press/v40/Anandkumar15.pdf UR - https://proceedings.mlr.press/v40/Anandkumar15.html AB - We provide guarantees for learning latent variable models emphasizing on the overcomplete regime, where the dimensionality of the latent space exceeds the observed dimensionality. In particular, we consider multiview mixtures, ICA, and sparse coding models. Our main tool is a new algorithm for tensor decomposition that works in the overcomplete regime. In the semi-supervised setting, we exploit label information to get a rough estimate of the model parameters, and then refine it using the tensor method on unlabeled samples. We establish learning guarantees when the number of components scales as k=o(d^p/2), where d is the observed dimension, and p is the order of the observed moment employed in the tensor method (usually p=3,4). In the unsupervised setting, a simple initialization algorithm based on SVD of the tensor slices is proposed, and the guarantees are provided under the stricter condition that k ≤βd (where constant βcan be larger than 1). For the learning applications, we provide tight sample complexity bounds through novel covering arguments. ER -
APA
Anandkumar, A., Ge, R. & Janzamin, M.. (2015). Learning Overcomplete Latent Variable Models through Tensor Methods. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:36-112 Available from https://proceedings.mlr.press/v40/Anandkumar15.html.

Related Material