Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
Latent models are a fundamental modeling tool in machine learning applications, but they present significant computational and analytical challenges. The popular EM algorithm and its variants, is a much used algorithmic tool; yet our rigorous understanding of its performance is highly incomplete. Recently, work in [1] has demonstrated that for an important class of problems, EM exhibits linear local convergence. In the high-dimensional setting, however, the M -step may not be well defined. We address precisely this setting through a unified treatment using regularization. While regularization for high-dimensional problems is by now well understood, the iterative EM algorithm requires a careful balancing of making progress towards the solution while identifying the right structure (e.g., sparsity or low-rank). In particular, regularizing the M -step using the state-of-the-art highdimensional prescriptions (e.g.,à la [19]) is not guaranteed to provide this balance. Our algorithm and analysis are linked in a way that reveals the balance between optimization and statistical errors. We specialize our general framework to sparse gaussian mixture models, high-dimensional mixed regression, and regression with missing variables, obtaining statistical guarantees for each of these examples.
In the EM algorithm for high dimensional setting, the M step is problematic, which needs to be addressed by exploiting the structure of the high-dim paramters. The paper considers to use decompposable regularizers. The main contribution is a way to set the regularizer in the iterative process of EM. It is shown that this leads to local linear convergence, under conditions about the population and empirical estimation of log likelihood using current estimation of the parameters (the basic quantity in EM). The EM algorithm is used widely in machine learning and it is thus an important topic to identify conditions under which it leads to provable guarantees. The paper gives a priciple way to regularize the EM which is particularly interesting for the high dimensional setting. It further demonstrates the application of the theory to three well known models. The result is interesting and important.--In the abstract: the authors claim that regularzing the M-step using the state of the art prescriptions ([19]) is not guaranteed to provide the desired bound, but this needs more illustration.--Condition 5: as noted by the authors, this replaces the term that appears in previous work. It seems to me that this condition is the key to make the algorithm work in the high-dim region, while the analysis follows the previous work. minor: --line 80: Y Z should be bold face --Eqn (2.2): "f" is missing --line 122: | |_R* is not yet defined here and thus the sentence is a bit confusing.