  The Expectation Maximisation (EM) algorithm is widely used to optimise
non-convex likelihood functions with latent variables. Many authors modified
its simple design to fit more specific situations. For instance, the
Expectation (E) step has been replaced by Monte Carlo (MC), Markov Chain Monte
Carlo or tempered approximations, etc. Most of the well-studied approximations
belong to the stochastic class. By comparison, the literature is lacking when
it comes to deterministic approximations. In this paper, we introduce a
theoretical framework, with state-of-the-art convergence guarantees, for any
deterministic approximation of the E step. We analyse theoretically and
empirically several approximations that fit into this framework. First, for
intractable E-steps, we introduce a deterministic version of MC-EM using
Riemann sums. A straightforward method, not requiring any hyper-parameter
fine-tuning, useful when the low dimensionality does not warrant a MC-EM. Then,
we consider the tempered approximation, borrowed from the Simulated Annealing
literature and used to escape local extrema. We prove that the tempered EM
verifies the convergence guarantees for a wider range of temperature profiles
than previously considered. We showcase empirically how new non-trivial
profiles can more successfully escape adversarial initialisations. Finally, we
combine the Riemann and tempered approximations into a method that accomplishes
both their purposes.
