Itcanbeshown (see [18] andthesupplementary material) thatKsEM-VROpt(n, )= KFIEMOpt(n, )= n2/3O( 1) and KsEM-VRCE (n, )= KFIEMCE (n, )= n+n2/3O( 1). SPIDER estimator employed, Proof Sketch.Whilewe

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 {\tt 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 integral differential estimator ({\tt SPIDER}) technique. We derive finite-time complexity bounds for smooth non-convex likelihood: we show that for convergence to an $\epsilon$-approximate stationary point, the complexity scales as $K_{Opt} (n,\epsilon)={\cal O}(\epsilon^{-1})$ and $K_{CE}( n,\epsilon) = n+ \sqrt{n} {\cal O}( \epsilon^{-1})$, where $K_{Opt}( n,\epsilon)$ and $K_{CE}(n, \epsilon)$ 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.

By convention, vectors are column vectors. We first compare the complexities of the incremental EM based methods using the following table which summarizes the state-of-the-art results. The last column is the optimal complexity to reach an -approximate stationary point. Next, we provide the psuedo-codes of several existing incremental EM-based algorithms, following the notations defined in the main paper. Using Lemma 3 below this page, we deduce that SPIDER-EM can be equivalently described by the following algorithm 7 .

Summary and Contributions: This paper proposes SPIDER-EM algorithm, which is the combination of recently developed SPIDER estimator with Expectation Maximization (EM) algorithm. The paper also provides a unified framework of stochastic approximation (SA) within EM. The results of SPIDER-EM match the typical results of SPIDER in nonconvex optimization, i.e., O(\sqrt(n)) and improves the previous result on EM with SVRG O(n {2/3}). Since it matches the typical results of SPIDER in nonconvex optimization, the obtained results should be correct. It is interesting that the SPIDER estimator can be applied to EM algorithms. On the other hand, since other variance reduction techniques (such as SVRG) have already been applied in the EM setting in the literature, the idea of SPIDER-EM is a combination of recent popular variance reduction algorithm SPIDER and the previous variance reduction EM algorithms, which is incremental.

The four expert reviewers agree that this paper makes a solid, if highly technical contribution to large-scale EM inference. Following the rebuttal, the most critical reviewer increased their score as the authors' comments alleviated their worry about novelty. I still want to encourage the authors to consider the suggestions made by this (and all the other) reviewers.

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 {\tt 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 integral differential estimator ({\tt SPIDER}) technique. We derive finite-time complexity bounds for smooth non-convex likelihood: we show that for convergence to an \epsilon -approximate stationary point, the complexity scales as K_{Opt} (n,\epsilon) {\cal O}(\epsilon {-1}) and K_{CE}( n,\epsilon) n \sqrt{n} {\cal O}( \epsilon {-1}), where K_{Opt}( n,\epsilon) and K_{CE}(n, \epsilon) 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.