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

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.

To appear in the proceedings of the Conference on Learning Theory (COLT), 2019. This paper results from a merger of work from two groups who work on the problem at the same time

References in corpus (5)

• Global analysis of Expectation Maximization for mixtures of two Gaussians
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
• On the Convergence of the EM Algorithm: A Data-Adaptive Analysis