Fast Incremental Expectation Maximization for finite-sum optimization:
  nonasymptotic convergence
  Fast Incremental Expectation Maximization (FIEM) is a version of the EM
framework for large datasets. In this paper, we first recast FIEM and other
incremental EM type algorithms in the {\em Stochastic Approximation within EM}
framework. Then, we provide nonasymptotic bounds for the convergence in
expectation as a function of the number of examples $n$ and of the maximal
number of iterations $\kmax$. We propose two strategies for achieving an
$\epsilon$-approximate stationary point, respectively with $\kmax =
O(n^{2/3}/\epsilon)$ and $\kmax = O(\sqrt{n}/\epsilon^{3/2})$, both strategies
relying on a random termination rule before $\kmax$ and on a constant step size
in the Stochastic Approximation step. Our bounds provide some improvements on
the literature. First, they allow $\kmax$ to scale as $\sqrt{n}$ which is
better than $n^{2/3}$ which was the best rate obtained so far; it is at the
cost of a larger dependence upon the tolerance $\epsilon$, thus making this
control relevant for small to medium accuracy with respect to the number of
examples $n$. Second, for the $n^{2/3}$-rate, the numerical illustrations show
that thanks to an optimized choice of the step size and of the bounds in terms
of quantities characterizing the optimization problem at hand, our results
desig a less conservative choice of the step size and provide a better control
of the convergence in expectation.
