On the Global Convergence of (Fast) Incremental Expectation Maximization Methods

Belhal Karimi, Hoi-To Wai, Eric Moulines, Marc Lavielle

The Expectation-Maximization (EM) algorithm is a cornerstone of machine learning, used everywhere from clustering with Gaussian Mixture Models to topic modeling. However, the classic "batch" EM algorithm has a major flaw: it requires a full pass over the entire dataset at every single step. In the era of Big Data, this is a significant bottleneck.

In their NeurIPS 2019 paper, Karimi et al. provide a rigorous theoretical foundation for modern, "stochastic" versions of EM that process data in small chunks. They go beyond analyzing existing methods by introducing a new algorithm (fiEM) and proving that these modern variants are fundamentally faster than the incremental methods used for decades.

TL;DR

This paper establishes the first non-asymptotic global convergence rates for several stochastic EM variants (iEM, sEM-VR) and introduces a new, faster version called fiEM. The authors prove that variance-reduced versions reduce iteration complexity from $O(n/\epsilon)$ to $O(n^{2/3}/\epsilon)$, a massive efficiency gain for large datasets.

What Problem Does This Paper Address?

The standard EM algorithm is an iterative process: an E-step (estimating missing data) followed by an M-step (maximizing the likelihood). When dealing with millions of data points, performing the E-step for every point before updating the model is incredibly slow.

Researchers previously proposed "Incremental" EM (iEM) and "Stochastic" EM (sEM) to alleviate this. While these worked well in practice, the field lacked a clear understanding of their global non-asymptotic convergence. In other words: how many iterations does it take to get "close enough" to a solution, starting from anywhere? Furthermore, can we accelerate this process using modern optimization tricks like variance reduction?

Methods

The authors tackle this by viewing EM through two distinct analytical lenses:

  1. Majorization-Minimization (MM): Viewing EM as creating a surrogate function that upper-bounds the objective and minimizing it.
  2. Scaled Gradient Descent: A surprising perspective where the EM update is seen as a gradient step in the space of "sufficient statistics," scaled by a specific matrix.

Using these perspectives, they analyze:

  • iEM (Incremental EM): Updates only a mini-batch of observations per iteration.
  • sEM-VR (Variance Reduced sEM): Uses a technique similar to SVRG to reduce the "noise" introduced by sampling mini-batches.
  • fiEM (Fast Incremental EM): A newly introduced algorithm inspired by the SAGA optimization method. It uses a clever update rule for sufficient statistics to achieve variance reduction without the periodic full-batch passes required by sEM-VR.

Datasets

The authors validated their theoretical findings using two primary benchmarks:

  • Synthetic Gaussian Mixture Models (GMM): Used to verify the relationship between sample size ($n$) and the number of iterations required.
  • FAO Datasets: Real-world document collections from the UN Food and Agriculture Organization (ranging from 1,000 to 10,500 documents) used for Probabilistic Latent Semantic Analysis (pLSA).

Key Insights and Ideas

  • EM is a Scaled Gradient Method: By proving that EM updates are essentially gradient steps in the space of sufficient statistics, the authors successfully ported over powerful convergence proofs from the world of stochastic optimization (like SVRG and SAGA).
  • The Monotonicity Trap: Standard iEM is "monotone," meaning it guarantees the objective function improves at every step. However, the authors show that this "safety" comes at a theoretical cost: it is slower ($O(n/\epsilon)$) than non-monotone variance-reduced methods.
  • Variance Reduction is King: By reducing the "noise" in the stochastic E-step, sEM-VR and fiEM achieve a much better dependency on the dataset size ($n^{2/3}$ vs $n$).

Key Results

  • Theoretical Speedup: The paper proves that to reach an $\epsilon$-stationary point, iEM requires $O(n/\epsilon)$ iterations, while the variance-reduced versions (sEM-VR and fiEM) only require $O(n^{2/3}/\epsilon)$.
Iteration complexity vs. problem size
  • Empirical Confirmation: In tests on pLSA and GMMs, fiEM and sEM-VR reached high-precision solutions significantly faster than both the standard batch EM and the incremental EM.
Convergence over epochs
  • Efficiency: The new fiEM algorithm provides a practical trade-off, offering the fast convergence of variance reduction without needing the occasional expensive full-dataset passes that sEM-VR requires.

Limitations and Future Work

  • Exponential Family Constraint: The current analysis is tailored to models where the complete data likelihood belongs to the "curved exponential family." While this covers many common models (GMM, pLSA, Hidden Markov Models), it isn't universal.
  • Memory Overhead: Algorithms like fiEM and iEM require storing sufficient statistics for every data point (or mini-batch). For truly massive datasets with complex statistics, this memory requirement could become a bottleneck.
  • Stationary Points: Like most non-convex optimization proofs, the "global convergence" here refers to reaching a stationary point (where the gradient is zero), which could technically be a local minimum or a saddle point rather than the global optimum.

Summary updated

Abstract

The EM algorithm is one of the most popular algorithm for inference in latent data models. The original formulation of the EM algorithm does not scale to large data set, because the whole data set is required at each iteration of the algorithm. To alleviate this problem, Neal and Hinton [1998] have proposed an incremental version of the EM (iEM) in which at each iteration the conditional expectation of the latent data (E-step) is updated only for a mini-batch of observations. Another approach has been proposed by Cappe and Moulines [2009] in which the E-step is replaced by a stochastic approximation step, closely related to stochastic gradient. In this paper, we analyze incremental and stochastic version of the EM algorithm as well as the variance reduced-version of [Chen et al., 2018] in a common unifying framework. We also introduce a new version incremental version, inspired by the SAGA algorithm by Defazio et al. [2014]. We establish non-asymptotic convergence bounds for global convergence. Numerical applications are presented in this article to illustrate our findings.
BibTeX
@inproceedings{karimi2019global,
  author = {Belhal Karimi and Hoi-To Wai and Eric Moulines and Marc Lavielle},
  title = {{On the Global Convergence of (Fast) Incremental Expectation Maximization Methods}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=2K1aOXr1Pc},
}
Figure