Fast incremental expectation-maximization algorithm: √N iterations for an epsilon-stationary point ?

Fast Incremental Expectation Maximization (FIEM) is an iterative algorithm, based on the Expectation Maximization (EM) algorithm, which was introduced to design EM for the large scale learning framework by avoiding the full data set to be processed at each iteration. In this paper, we first recast this algorithm in the Stochastic Approximation (SA) within EM framework. Then, we provide non asymptotic convergence rates as a function of the batch size n and of the maximal number of iterations Kmax fixed by the user. This allows a complexity analysis: in order to reach an-approximate solution, how does Kmax depend upon n and