High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality

Abstract

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 new inferential procedures for testing hypotheses and constructing confidence intervals 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. Our theory is supported by thorough numerical results.

84 pages, 2 figures, 1 table

References in corpus (9)

• Simultaneous analysis of Lasso and Dantzig selector
• Confidence Intervals and Hypothesis Testing for High-Dimensional Regression
• Truncated Power Method for Sparse Eigenvalue Problems
• A Two-round Variant of EM for Gaussian Mixtures
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Exact Post-Selection Inference for Sequential Regression Procedures
• Learning Mixtures of Gaussians using the k-means Algorithm
• Sample Complexity Analysis for Learning Overcomplete Latent Variable Models through Tensor Methods
• Post-Selection Inference for Generalized Linear Models with Many Controls

Cited by in corpus (15)

• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• DSD: Dense-Sparse-Dense Training for Deep Neural Networks
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• A Survey of Optimization Methods from a Machine Learning Perspective
• Complete Dictionary Recovery over the Sphere
• Statistical and Computational Guarantees for the Baum-Welch Algorithm
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Local Minima Structures in Gaussian Mixture Models
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• Provable Sparse Tensor Decomposition
• The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures
• A clustering tool for nucleotide sequences using Laplacian Eigenmaps and Gaussian Mixture Models