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 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 Capp'e and Moulines 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. in a common unifying framework. We also introduce a new version incremental version, inspired by the SAGA algorithm by Defazio et. al. We establish non-asymptotic convergence bounds for global convergence. Numerical applications are presented in this article to illustrate our findings.
Introduction
The Expectation-Maximization (EM) algorithm is a cornerstone of machine learning, widely used for latent variable inference in models ranging from Gaussian Mixture Models (GMM) to Probabilistic Latent Semantic Analysis (pLSA). However, the classic "batch" version of EM requires a full pass over the entire dataset at every iteration, which is computationally prohibitive for large-scale datasets.
While incremental (iEM) and stochastic (sEM) variants have been developed to handle large data, theoretical understanding of these methods has been largely limited to asymptotic behavior or local convergence. This paper provides a rigorous theoretical foundation by establishing the first global, non-asymptotic convergence rates for these methods and introducing a new, faster algorithm, fiEM.
Methods
The authors analyze EM through two complementary lenses: viewing it as a Majorization-Minimization (MM) method in the parameter space, and as a scaled-gradient method in the space of sufficient statistics for curved exponential families.
By applying variance reduction techniques to the sufficient statistics, the authors introduce fiEM (Fast Incremental EM), inspired by the SAGA algorithm. Unlike sEM-VR (inspired by SVRG), which requires periodic full passes to reset variance, fiEM updates a table of stored sufficient statistics incrementally. This unified framework allows for a direct theoretical and empirical comparison of iEM, sEM, sEM-VR, and fiEM.
Results
The theoretical analysis proves that variance-reduced methods (sEM-VR and fiEM) significantly outperform standard incremental approaches. Specifically, the iteration complexity is reduced from $O(n/\epsilon)$ for iEM to $O(n^{2/3}/\epsilon)$ for VR methods.
Empirical validation on GMM and pLSA datasets confirms these findings. As shown in the figures, fiEM and sEM-VR exhibit significantly faster convergence compared to batch or standard incremental EM. Furthermore, experiments varying the problem size $n$ validate the $O(n^{2/3})$ scaling bound for variance-reduced methods, demonstrating its sharpness in practice.
Conclusion
This work establishes the first global, non-asymptotic convergence analysis for incremental and variance-reduced EM algorithms. By demonstrating that variance reduction can be effectively applied to sufficient statistics, the authors provide a path for scaling latent variable inference to massive datasets. Future work includes extending these guarantees beyond the curved exponential family and addressing the memory overhead associated with storing sufficient statistics in fiEM.
Summary updated