Provable Tensor Methods for Learning Mixtures of Generalized Linear Models
Hanie Sedghi, Majid Janzamin, Anima Anandkumar
Abstract
We consider the problem of learning mixtures of generalized linear models (GLM) which arise in classification and regression problems. Typical learning approaches such as expectation maximization (EM) or variational Bayes can get stuck in spurious local optima. In contrast, we present a tensor decomposition method which is guaranteed to correctly recover the parameters. The key insight is to employ certain feature transformations of the input, which depend on the input generative model. Specifically, we employ score function tensors of the input and compute their cross-correlation with the response variable. We establish that the decomposition of this tensor consistently recovers the parameters, under mild non-degeneracy conditions. We demonstrate that the computational and sample complexity of our method is a low order polynomial of the input and the latent dimensions.
BibTeX
@InProceedings{pmlr-v51-sedghi16,
title = {Provable Tensor Methods for Learning Mixtures of Generalized Linear Models},
author = {Sedghi, Hanie and Janzamin, Majid and Anandkumar, Anima},
booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics},
pages = {1223--1231},
year = {2016},
editor = {Gretton, Arthur and Robert, Christian C.},
volume = {51},
series = {Proceedings of Machine Learning Research},
address = {Cadiz, Spain},
month = {09--11 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v51/sedghi16.pdf},
url = {https://proceedings.mlr.press/v51/sedghi16.html},
abstract = {We consider the problem of learning mixtures of generalized linear models (GLM) which arise in classification and regression problems. Typical learning approaches such as expectation maximization (EM) or variational Bayes can get stuck in spurious local optima. In contrast, we present a tensor decomposition method which is guaranteed to correctly recover the parameters. The key insight is to employ certain feature transformations of the input, which depend on the input generative model. Specifically, we employ score function tensors of the input and compute their cross-correlation with the response variable. We establish that the decomposition of this tensor consistently recovers the parameters, under mild non-degeneracy conditions. We demonstrate that the computational and sample complexity of our method is a low order polynomial of the input and the latent dimensions.}
}