Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression

Jeongyeol Kwon, Wei Qian, Constantine Caramanis, Yudong Chen, Damek Davis
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:2055-2110, 2019.

Abstract

The Expectation-Maximization algorithm is perhaps the most broadly used algorithm for inference of latent variable problems. A theoretical understanding of its performance, however, largely remains lacking. Recent results established that EM enjoys global convergence for Gaussian Mixture Models. For Mixed Linear Regression, however, only local convergence results have been established, and those only for the high SNR regime. We show here that EM converges for mixed linear regression with two components (it is known that it may fail to converge for three or more), and moreover that this convergence holds for random initialization. Our analysis reveals that EM exhibits very different behavior in Mixed Linear Regression from its behavior in Gaussian Mixture Models, and hence our proofs require the development of several new ideas.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-kwon19a, title = {Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression}, author = {Kwon, Jeongyeol and Qian, Wei and Caramanis, Constantine and Chen, Yudong and Davis, Damek}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {2055--2110}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/kwon19a/kwon19a.pdf}, url = {https://proceedings.mlr.press/v99/kwon19a.html}, abstract = {The Expectation-Maximization algorithm is perhaps the most broadly used algorithm for inference of latent variable problems. A theoretical understanding of its performance, however, largely remains lacking. Recent results established that EM enjoys global convergence for Gaussian Mixture Models. For Mixed Linear Regression, however, only local convergence results have been established, and those only for the high SNR regime. We show here that EM converges for mixed linear regression with two components (it is known that it may fail to converge for three or more), and moreover that this convergence holds for random initialization. Our analysis reveals that EM exhibits very different behavior in Mixed Linear Regression from its behavior in Gaussian Mixture Models, and hence our proofs require the development of several new ideas.} }
Endnote
%0 Conference Paper %T Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression %A Jeongyeol Kwon %A Wei Qian %A Constantine Caramanis %A Yudong Chen %A Damek Davis %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-kwon19a %I PMLR %P 2055--2110 %U https://proceedings.mlr.press/v99/kwon19a.html %V 99 %X The Expectation-Maximization algorithm is perhaps the most broadly used algorithm for inference of latent variable problems. A theoretical understanding of its performance, however, largely remains lacking. Recent results established that EM enjoys global convergence for Gaussian Mixture Models. For Mixed Linear Regression, however, only local convergence results have been established, and those only for the high SNR regime. We show here that EM converges for mixed linear regression with two components (it is known that it may fail to converge for three or more), and moreover that this convergence holds for random initialization. Our analysis reveals that EM exhibits very different behavior in Mixed Linear Regression from its behavior in Gaussian Mixture Models, and hence our proofs require the development of several new ideas.
APA
Kwon, J., Qian, W., Caramanis, C., Chen, Y. & Davis, D.. (2019). Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:2055-2110 Available from https://proceedings.mlr.press/v99/kwon19a.html.

Related Material