Statistical guarantees for the EM algorithm: from population to sample-based analysis
From MaRDI portal
Publication:524451
DOI10.1214/16-AOS1435zbMATH Open1367.62052arXiv1408.2156OpenAlexW2962737134MaRDI QIDQ524451FDOQ524451
Authors: Sivaraman Balakrishnan, Martin J. Wainwright, Bin Yu 
Publication date: 2 May 2017
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: We develop a general framework for proving rigorous guarantees on the performance of the EM algorithm and a variant known as gradient EM. Our analysis is divided into two parts: a treatment of these algorithms at the population level (in the limit of infinite data), followed by results that apply to updates based on a finite set of samples. First, we characterize the domain of attraction of any global maximizer of the population likelihood. This characterization is based on a novel view of the EM updates as a perturbed form of likelihood ascent, or in parallel, of the gradient EM updates as a perturbed form of standard gradient ascent. Leveraging this characterization, we then provide non-asymptotic guarantees on the EM and gradient EM algorithms when applied to a finite set of samples. We develop consequences of our general theory for three canonical examples of incomplete-data problems: mixture of Gaussians, mixture of regressions, and linear regression with covariates missing completely at random. In each case, our theory guarantees that with a suitable initialization, a relatively small number of EM (or gradient EM) steps will yield (with high probability) an estimate that is within statistical error of the MLE. We provide simulations to confirm this theoretically predicted behavior.
Full work available at URL: https://arxiv.org/abs/1408.2156
Recommendations
- Statistical convergence of the EM algorithm on Gaussian mixture models
- Convergence theorems for generalized alternating minimization procedures
- Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \(O(\sqrt{n})\) iterations
- scientific article; zbMATH DE number 4032799
- On the global and componentwise rates of convergence of the EM algorithm
Cited In (67)
- Supermix: sparse regularization for mixtures
- Sketched learning for image denoising
- Robust high dimensional expectation maximization algorithm via trimmed hard thresholding
- Analysis of a generalised expectation-maximisation algorithm for Gaussian mixture models: a control systems perspective
- A new class of stochastic EM algorithms. Escaping local maxima and handling intractable sampling
- Optimal estimation of Gaussian mixtures via denoised method of moments
- Oscillating neural circuits: Phase, amplitude, and the complex normal distribution
- Uniform consistency in nonparametric mixture models
- Title not available (Why is that?)
- Statistical Inference with Local Optima
- Title not available (Why is that?)
- Covariate regularized community detection in sparse graphs
- Rate optimal estimation and confidence intervals for high-dimensional regression with missing covariates
- Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
- Improved convergence guarantees for learning Gaussian mixture models by EM and gradient EM
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- Computing Robust Statistics via an EM Algorithm
- Singularity, misspecification and the convergence rate of EM
- Universal inference
- Parameter recovery in two-component contamination mixtures: the \(L^2\) strategy
- A general frame for uncertainty propagation under multimodally distributed random variables
- Sharp global convergence guarantees for iterative nonconvex optimization with random data
- Subgroup-effects models for the analysis of personal treatment effects
- Solution manifold and its statistical applications
- Exponential-Family Embedding With Application to Cell Developmental Trajectories for Single-Cell RNA-Seq Data
- On the nonparametric maximum likelihood estimator for Gaussian location mixture densities with application to Gaussian denoising
- Statistical convergence of the EM algorithm on Gaussian mixture models
- STORE: sparse tensor response regression and neuroimaging analysis
- Network inference from temporally dependent grouped observations
- Estimating finite mixtures of ordinal graphical models
- Statistical analysis of Markov switching vector autoregression models with endogenous explanatory variables
- From inexact optimization to learning via gradient concentration
- Improving the accuracy and internal consistency of regression-based clustering of high-dimensional datasets
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Simultaneous Clustering and Estimation of Heterogeneous Graphical Models
- Community detection with dependent connectivity
- The computational asymptotics of Gaussian variational inference and the Laplace approximation
- Reliable clustering of Bernoulli mixture models
- A flexible probabilistic framework for large-margin mixture of experts
- Statistical and computational guarantees for the Baum-Welch algorithm
- An alternative to EM for Gaussian mixture models: batch and stochastic Riemannian optimization
- Likelihood Maximization and Moment Matching in Low <scp>SNR</scp> Gaussian Mixture Models
- Large-sample properties of unsupervised estimation of the linear discriminant using projection pursuit
- On the curved exponential family in the stochastic approximation expectation maximization algorithm
- Statistical Inference for High-Dimensional Vector Autoregression with Measurement Error
- Title not available (Why is that?)
- Semiparametric mixture regression with unspecified error distributions
- Homomorphic sensing of subspace arrangements
- Estimating a network from multiple noisy realizations
- Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \(O(\sqrt{n})\) iterations
- Iterative algorithm for discrete structure recovery
- GAT–GMM: Generative Adversarial Training for Gaussian Mixture Models
- Geometry of EM and related iterative algorithms
- Sequential estimation for mixture of regression models for heterogeneous population
- A new algorithm for inference in HMM's with lower span complexity
- Loss modeling with the size-biased lognormal mixture and the entropy regularized EM algorithm
- Moment Estimation for Nonparametric Mixture Models through Implicit Tensor Decomposition
- A diffusion process perspective on posterior contraction rates for parameters
- Tuning-free sparse clustering via alternating hard-thresholding
- A Doubly Enhanced EM Algorithm for Model-Based Tensor Clustering
- Optimal estimation and computational limit of low-rank Gaussian mixtures
- Mixture conditional regression with ultrahigh dimensional text data for estimating extralegal factor effects
- Deep parameterizations of pairwise and triplet Markov models for unsupervised classification of sequential data
- Likelihood-based analysis in mixture global vars
- Fundamental limits of low-rank matrix estimation with diverging aspect ratios
- Nonparametric Finite Mixture of Gaussian Graphical Models
- A tensor-EM method for large-scale latent class analysis with binary responses
This page was built for publication: Statistical guarantees for the EM algorithm: from population to sample-based analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q524451)
