FAST INCREMENTAL EXPECTATION-MAXIMIZATION ALGORITHM: √ N ITERATIONS FOR AN $\\epsilon$-STATIONARY POINT ?
Pierre Gach, Gersende Fort, Éric Moulines · HAL (Le Centre pour la Communication Scientifique Directe) · 2020
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 ?