###### Abstract  
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. Expectation Maximisation; exponential family; approximate EM; Riemann sums; tempering; annealing  
3  
T: 1  
them rely on Monte Carlo (MC) methods and Stochastic Approximations (SA) to estimate this expectation. Notable examples include the Stochastic Approximation EM (SAEM, [5]), the Monte Carlo EM (MC-EM, [6]), the Markov Chain Monte Carlo EM (MCMC-EM, [7]), the MCMC-SAEM [8; 9] and the Approximate SAEM [10]. Random approximation of the E step have also been used in the case where the data are too voluminous to allow a full E step computation. A non-exhaustive list includes the Incremental EM [11; 12], the Online EM [13] and, more recently, the stochastic EM with variance reduction (sEM-vr) [14], the fast Incremental EM (FIEM) [15], the Stochastic Path-Integrated Differential EstimatoR EM (SPIDER-EM) [16], and the mini-batch MCMC-SAEM [17]. Most of these variants come with their own theoretical convergence guarantees for the models of the exponential family. Recent works have also provided theoretical analysis of the EM algorithm outside of the exponential family, with locally strongly-concave log-likelihood function around the global maxima by [PERSON] et al. [18], or without such strong-concavity assumption by [PERSON] et al. [19]. The stochastically approximated EM algorithms constitute an extensive catalogue of methods. Indeed, there are many possible variants of MCMC samplers that can be considered, as well as the additional parameters, such as the burn-in period length and the gain decrease sequence, that have to be set. All these choices have an impact on the convergence of these \"EM-like\" algorithms and making the appropriate ones for each problem can be overwhelming, see [20; 21; 22], among others, for discussions on tuning the MC-EM alone. On several cases, one might desire to dispose of a simpler method, possibly non-stochastic, and non-parametric to run an EM-like algorithm for models with no closed forms. However the literature is lacking in that regards. The Quasi-Monte Carlo EM, introduced by [PERSON] and [PERSON] [23], is a deterministic version of Monte Carlo EM, however theoretical guarantees are not provided. In that vein, [PERSON] [24] introduces the randomised Quasi-Monte Carlo EM, which is not deterministic, and does not have theoretical guarantees either. Another example of deterministic approximation can be found in the Variational EM [25; 26; 27], where the conditional distribution is approximated within a certain distribution family, and optimised over before each E step.