Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent

Expectation maximization (EM) is the default algorithm for fitting\nprobabilistic models with missing or latent variables, yet we lack a full\nunderstanding of its non-asymptotic convergence properties. Previous works show\nresults along the lines of "EM converges at least as fast as gradient descent"\nby assuming the conditions for the convergence of gradient descent apply to EM.\nThis approach is not only loose, in that it does not capture that EM can make\nmore progress than a gradient step, but the assumptions fail to hold for\ntextbook examples of EM like Gaussian mixtures. In this work we first show that\nfor the common setting of exponential family distributions, viewing EM as a\nmirror descent algorithm leads to convergence rates in Kullback-Leibler (KL)\ndivergence. Then, we show how the KL divergence is related to first-order\nstationarity via Bregman divergences. In contrast to previous works, the\nanalysis is invariant to the choice of parametrization and holds with minimal\nassumptions. We also show applications of these ideas to local linear (and\nsuperlinear) convergence rates, generalized EM, and non-exponential family\ndistributions.\n