A Stochastic Path-Integrated Differential EstimatoR Expectation Maximization Algorithm
This work provides a more efficient EM algorithm for researchers and practitioners working with large-scale latent variable models, addressing the computational bottleneck of existing methods.
This paper introduces SPIDER-EM, a novel Expectation Maximization algorithm designed for inference in latent variable models with large training sets. The algorithm achieves improved finite-time complexity bounds for smooth non-convex likelihood, specifically showing that the number of M-steps scales as O(ε^-1) and the number of per-sample conditional expectation evaluations scales as n + sqrt(n)O(ε^-1) for convergence to an ε-approximate stationary point.
The Expectation Maximization (EM) algorithm is of key importance for inference in latent variable models including mixture of regressors and experts, missing observations. This paper introduces a novel EM algorithm, called \texttt{SPIDER-EM}, for inference from a training set of size $n$, $n \gg 1$. At the core of our algorithm is an estimator of the full conditional expectation in the {\sf E}-step, adapted from the stochastic path-integrated differential estimator ({\tt SPIDER}) technique. We derive finite-time complexity bounds for smooth non-convex likelihood: we show that for convergence to an $ε$-approximate stationary point, the complexity scales as $K_{\operatorname{Opt}} (n,ε)={\cal O}(ε^{-1})$ and $K_{\operatorname{CE}}( n,ε) = n+ \sqrt{n} {\cal O}(ε^{-1} )$, where $K_{\operatorname{Opt}}( n,ε)$ and $K_{\operatorname{CE}}(n, ε)$ are respectively the number of {\sf M}-steps and the number of per-sample conditional expectations evaluations. This improves over the state-of-the-art algorithms. Numerical results support our findings.