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.

This paper has provided global convergence analyses, with convergence rates, of stochastic EM-algorithms which include incremental (iEM) and variance reduced (sEM-VR) versions of EM-algorithms. Especially, the paper has given a convergence rate of O(n/\epsilon) for iEM by applying the theory developed by Miral(2015) and a convergence rate of O(n {2/3}/\epsilon) for sEM-VR by showing sEM-VR is a special case of stochastic scaled-gradient methods. In addition, a new variance reduced EM-algorithm named fiEM based on SAGA has been proposed with its convergence analysis as well as sEM-VR. Finally, the superiority of variance reduced variants (sEM-VR and fiEM) has been shown via numerical experiments. Clarity: The paper is clear and well written.

This paper studies the convergence of incremental and stochastic Expectation-Maximization (EM). This paper is on the borderline and was carefully discussed. The main concern of the reviewers is that Theorem 1 in this submission is a special case of Theorem 1 in submission 1613 (from the same authors). After some discussions, reviewers recognized that Theorem 2 is more important than Theorem 1, and is the main contribution of this work. Therefore, I recommend reject 1613 and accept this one.

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.

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.