High Dimensional EM Algorithm: Statistical Optimization and Asymptotic Normality
We provide a general theory of the expectation-maximization (EM) algorithm for inferring high dimensional latent variable models. In particular, we make two contributions: (i) For parameter estimation, we propose a novel high dimensional EM algorithm which naturally incorporates sparsity structure into parameter estimation. With an appropriate initialization, this algorithm converges at a geometric rate and attains an estimator with the (near-)optimal statistical rate of convergence. (ii) Based on the obtained estimator, we propose a new inferential procedure for testing hypotheses for low dimensional components of high dimensional parameters. For a broad family of statistical models, our framework establishes the first computationally feasible approach for optimal estimation and asymptotic inference in high dimensions.
A sparse EM procedure is proposed which modifies classical EM by truncating the parameter vector at each step to a desired sparsity level. Also proposed is an asymptotically normal statistic based on a decorrelated score for testing whether a specific entry of the parameter vector is non-zero. The guarantee provided for the sparse EM states that the estimate converges geometrically to the true value (in the number of iterations), up to a statistical error term which is like the square root of the sparsity level and the infinity norm of the statistical error in the M-step, which is typically only logarithmic in the ambient dimension.This follows on the heels of recent similar results for EM in the low-dimensional setting. As in the previous work, it is assumed that the Q function is sufficiently smooth and nearly quadratic in a certain basin of attraction, and that the algorithm is initialized in the same basin. The new condition is the infinity norm control on the error in estimating M. This condition is required only for sparse vectors, but for many models estimating M at all possible vectors is just as easy as at sparse vectors (this holds for the Gaussian mixture example considered, and for the non-gradient version of the mixture of regression model). This raises a question -- is the truncated EM algorithm necessary? Could a similar guarantee be obtained, for instance, by performing ordinary EM under the same conditions, followed by a single truncation step? EDIT: the authors' observation that linear regression is a special case here seems to be a convincing argument against a single truncation step.There may be some related work in sparse optimization that perhaps should be discussed (like "Sparse online learning via truncated gradient" Langford et al 2009, just as an example).The experimental section should state what initialization was used.