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:
- Majorization-Minimization (MM): Viewing EM as creating a surrogate function that upper-bounds the objective and minimizing it.
- 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)$.
- 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.
- 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