Asymptotic convergence properties of the EM algorithm with respect to the overlap in the mixture

The EM algorithm is generally considered as a linearly convergent algorithm. However, many empirical results show that it can converge significantly faster than those gradient based first-order iterative algorithms, especially when the overlap of densities in a mixture is small. This paper explores this issue theoretically on mixtures of densities from a class of exponential families. We have proved that as an average overlap measure of densities in the mixture tends to zero, the asymptotic convergence rate of the EM algorithm locally around the true solution is a higher order infinitesimal than a positive order power of this overlap measure. Thus, the large sample local convergence rate for the EM algorithm tends to be asymptotically superlinear when the overlap of densities in the mixture tends to zero. Moreover, this result has been detailed on Gaussian mixtures. (c) 2005 Elsevier B.V. All rights reserved.Computer Science, Artificial IntelligenceSCI(E)EI0ARTICLE1-4105-1296