Regularized EM Algorithms: A Unified Framework and Statistical Guarantees

Abstract

Latent variable 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 Balakrishnan et al. (2014) 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 high-dimensional prescriptions (e.g., Wainwright (2014)) 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.

53 pages, 3 figures. A shorter version appears in NIPS 2015

Cited by in corpus (21)

• Parameter Estimation of Heavy-Tailed AR Model with Missing Data via Stochastic EM
• Anomaly Detection in Partially Observed Traffic Networks
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Statistical and Computational Guarantees for the Baum-Welch Algorithm
• Singularity, Misspecification, and the Convergence Rate of EM
• Instability, Computational Efficiency and Statistical Accuracy
• Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression
• Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
• Differentially Private (Gradient) Expectation Maximization Algorithm with Statistical Guarantees
• Jointly Modeling and Clustering Tensors in High Dimensions
• Sharp Analysis of Expectation-Maximization for Weakly Identifiable Models
• Provable Hierarchical Imitation Learning via EM
• Convergence of Parameter Estimates for Regularized Mixed Linear Regression Models
• Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
• The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures
• Sparse Tensor Additive Regression
• Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent
• A Simple Correction Procedure for High-Dimensional Generalized Linear Models with Measurement Error
• Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent
• Learning Mixtures of Low-Rank Models
• Learning Graph Neural Networks with Approximate Gradient Descent