# Regularized EM Algorithms: A Unified Framework and Statistical Guarantees

arXiv: https://arxiv.org/abs/1511.08551 · HTML: https://mlsanity.com/paper/1511.08551/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2015.

## Built on by (most cited first, 20 of 20)

- [Selective inference for k-means clustering](https://mlsanity.com/paper/2203.15267/) (2022)
- [Provable Hierarchical Imitation Learning via EM](https://mlsanity.com/paper/2010.03133/) (2020)
- [Prediction Sets for High-Dimensional Mixture of Experts Models](https://mlsanity.com/paper/2210.16710/) (2022)
- [The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures](https://mlsanity.com/paper/2103.15653/) (2021)
- [Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent](https://mlsanity.com/paper/2110.07810/) (2021)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees](https://mlsanity.com/paper/2104.00245/) (2021)
- [Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures](https://mlsanity.com/paper/2205.11078/) (2022)
- [Block Sparse Bayesian Learning: A Diversified Scheme](https://mlsanity.com/paper/2402.04646/) (2024)
- [Jointly Modeling and Clustering Tensors in High Dimensions](https://mlsanity.com/paper/2104.07773/) (2021)
- [An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models](https://mlsanity.com/paper/2205.07999/) (2022)
- [EM for Mixture of Linear Regression with Clustered Data](https://mlsanity.com/paper/2308.11518/) (2023)
- [In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamics](https://mlsanity.com/paper/2410.14183/) (2024)
- [Improving Computational Complexity in Statistical Models with Second-Order Information](https://mlsanity.com/paper/2202.04219/) (2022)
- [Hierarchical mixtures of Gaussians for combined dimensionality reduction and clustering](https://mlsanity.com/paper/2206.04841/) (2022)
- [Estimation of High-Dimensional Markov-Switching VAR Models with an Approximate EM Algorithm](https://mlsanity.com/paper/2210.07456/) (2022)
- [Regularized EM algorithm](https://mlsanity.com/paper/2303.14989/) (2023)
- [Inferring Diffusion Structures of Heterogeneous Network Cascade](https://mlsanity.com/paper/2506.19142/) (2025)
- [Graph-Regularized Learning of Gaussian Mixture Models](https://mlsanity.com/paper/2509.13855/) (2025)
- [Selective Inference for Clustering Under Unknown Covariance](https://mlsanity.com/paper/2610.17458/) (2026)

## Abstract (arXiv)

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.