{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:54:12Z","timestamp":1770742452179,"version":"3.49.0"},"reference-count":40,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["678304"],"award-info":[{"award-number":["678304"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["666992"],"award-info":[{"award-number":["666992"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["826421"],"award-info":[{"award-number":["826421"]}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-P3IA-0001"],"award-info":[{"award-number":["ANR-19-P3IA-0001"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-10-IAIHU-06"],"award-info":[{"award-number":["ANR-10-IAIHU-06"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a15030078","type":"journal-article","created":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T10:00:40Z","timestamp":1645783240000},"page":"78","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Deterministic Approximate EM Algorithm; Application to the Riemann Approximation EM and the Tempered EM"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7820-0032","authenticated-orcid":false,"given":"Thomas","family":"Lartigue","sequence":"first","affiliation":[{"name":"Aramis Project-Team, Inria, 75012 Paris, France"},{"name":"CMAP, CNRS, \u00c9cole Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9450-6920","authenticated-orcid":false,"given":"Stanley","family":"Durrleman","sequence":"additional","affiliation":[{"name":"Aramis Project-Team, Inria, 75012 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5692-4945","authenticated-orcid":false,"given":"St\u00e9phanie","family":"Allassonni\u00e8re","sequence":"additional","affiliation":[{"name":"HeKA, Centre de Recherche des Cordeliers, Universit\u00e9 de Paris, INRIA, INSERM, Sorbonne Universit\u00e9, 75012 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the EM algorithm","volume":"39","author":"Dempster","year":"1977","journal-title":"J. R. Stat. Soc. Ser. (Methodol.)"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1214\/aos\/1176346060","article-title":"On the convergence properties of the EM algorithm","volume":"11","author":"Wu","year":"1983","journal-title":"Ann. Stat."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1111\/j.2517-6161.1983.tb01229.x","article-title":"On the convergence of the EM algorithm","volume":"45","author":"Boyles","year":"1983","journal-title":"J. R. Stat. Soc. Ser. (Methodol.)"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1111\/j.2517-6161.1995.tb02037.x","article-title":"A gradient algorithm locally equivalent to the EM algorithm","volume":"57","author":"Lange","year":"1995","journal-title":"J. R. Stat. Soc. Ser. (Methodol.)"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1214\/aos\/1018031103","article-title":"Convergence of a stochastic approximation version of the EM algorithm","volume":"27","author":"Delyon","year":"1999","journal-title":"Ann. Stat."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1080\/01621459.1990.10474930","article-title":"A Monte Carlo implementation of the EM algorithm and the poor man\u2019s data augmentation algorithms","volume":"85","author":"Wei","year":"1990","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1220","DOI":"10.1214\/aos\/1059655912","article-title":"Convergence of the Monte Carlo expectation maximization for curved exponential families","volume":"31","author":"Fort","year":"2003","journal-title":"Ann. Stat."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1020","DOI":"10.1016\/j.csda.2004.07.002","article-title":"Maximum likelihood estimation in nonlinear mixed effects models","volume":"49","author":"Kuhn","year":"2005","journal-title":"Comput. Stat. Data Anal."},{"key":"ref_9","first-page":"641","article-title":"Construction of Bayesian deformable models via a stochastic approximation algorithm: A convergence study","volume":"16","author":"Kuhn","year":"2010","journal-title":"Bernoulli"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"107159","DOI":"10.1016\/j.csda.2020.107159","article-title":"A New Class of EM Algorithms. Escaping Local Maxima and Handling Intractable Sampling","volume":"159","author":"Chevallier","year":"2021","journal-title":"Comput. Stat. Data Anal."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Neal, R.M., and Hinton, G.E. (1998). A view of the EM algorithm that justifies incremental, sparse, and other variants. Learning in Graphical Models, Springer.","DOI":"10.1007\/978-94-011-5014-9_12"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1023\/A:1021987710829","article-title":"On the choice of the number of blocks with the incremental EM algorithm for the fitting of normal mixtures","volume":"13","author":"Ng","year":"2003","journal-title":"Stat. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1111\/j.1467-9868.2009.00698.x","article-title":"On-line expectation\u2013maximization algorithm for latent data models","volume":"71","author":"Moulines","year":"2009","journal-title":"J. R. Stat. Soc. Ser. (Stat. Methodol.)"},{"key":"ref_14","first-page":"7967","article-title":"Stochastic expectation maximization with variance reduction","volume":"31","author":"Chen","year":"2018","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_15","unstructured":"Karimi, B., Wai, H.T., Moulines, E., and Lavielle, M. (2019). On the global convergence of (fast) incremental expectation maximization methods. Advances in Neural Information Processing Systems, Curran Associates, Inc."},{"key":"ref_16","first-page":"16972","article-title":"A Stochastic Path Integral Differential EstimatoR Expectation Maximization Algorithm","volume":"34","author":"Fort","year":"2020","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.1007\/s11222-020-09968-0","article-title":"Properties of the stochastic approximation EM algorithm with mini-batch sampling","volume":"30","author":"Kuhn","year":"2020","journal-title":"Stat. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1214\/16-AOS1435","article-title":"Statistical guarantees for the EM algorithm: From population to sample-based analysis","volume":"45","author":"Balakrishnan","year":"2017","journal-title":"Ann. Stat."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"3161","DOI":"10.1214\/19-AOS1924","article-title":"Singularity, misspecification and the convergence rate of EM","volume":"48","author":"Dwivedi","year":"2020","journal-title":"Ann. Stat."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1111\/1467-9868.00176","article-title":"Maximizing generalized linear mixed model likelihoods with an automated Monte Carlo EM algorithm","volume":"61","author":"Booth","year":"1999","journal-title":"J. R. Stat. Soc. Ser. (Stat. Methodol.)"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1198\/106186001317115045","article-title":"Implementations of the Monte Carlo EM algorithm","volume":"10","author":"Levine","year":"2001","journal-title":"J. Comput. Graph. Stat."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1080\/0094965031000147704","article-title":"An automated (Markov chain) Monte Carlo em algorithm","volume":"74","author":"Levine","year":"2004","journal-title":"J. Stat. Comput. Simul."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Pan, J.X., and Thompson, R. (1998). Quasi-Monte Carlo EM algorithm for MLEs in generalized linear mixed models. COMPSTAT, Physica-Verlag.","DOI":"10.1007\/978-3-662-01131-7_58"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/j.csda.2004.03.019","article-title":"Quasi-Monte Carlo sampling to improve the efficiency of Monte Carlo EM","volume":"48","author":"Jank","year":"2005","journal-title":"Comput. Stat. Data Anal."},{"key":"ref_25","unstructured":"Attias, H. (1999). Inferring Parameters and Structure of Latent Variable Models by Variational Bayes. Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers Inc."},{"key":"ref_26","unstructured":"Bishop, C. (2006). Pattern Recognition and Machine Learning, Springer."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1109\/MSP.2008.929620","article-title":"The variational approximation for Bayesian inference","volume":"25","author":"Tzikas","year":"2008","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2607","DOI":"10.1103\/PhysRevLett.57.2607","article-title":"Replica Monte Carlo simulation of spin-glasses","volume":"57","author":"Swendsen","year":"1986","journal-title":"Phys. Rev. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1080\/01621459.1995.10476590","article-title":"Annealing Markov chain Monte Carlo with applications to ancestral inference","volume":"90","author":"Geyer","year":"1995","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/S0893-6080(97)00133-0","article-title":"Deterministic annealing EM algorithm","volume":"11","author":"Ueda","year":"1998","journal-title":"Neural Netw."},{"key":"ref_32","unstructured":"Naim, I., and Gildea, D. (2012). Convergence of the EM algorithm for Gaussian mixtures with unbalanced mixing coefficients. Proceedings of the 29th International Conference on Machine Learning, Omnipress."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-4149(87)90039-1","article-title":"Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds","volume":"27","author":"Chen","year":"1987","journal-title":"Stoch. Process. Their Appl."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Van Laarhoven, P.J., and Aarts, E.H. (1987). Simulated annealing. Simulated Annealing: Theory and Applications, Springer.","DOI":"10.1007\/978-94-015-7744-1"},{"key":"ref_35","unstructured":"Aarts, E., and Korst, J. (1988). Simulated Annealing and Boltzmann Machines, John Wiley and Sons Inc."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1604","DOI":"10.1143\/JPSJ.65.1604","article-title":"Exchange Monte Carlo method and application to spin glass simulations","volume":"65","author":"Hukushima","year":"1996","journal-title":"J. Phys. Soc. Jpn."},{"key":"ref_37","unstructured":"Titterington, D., Smith, A., and Makov, U. (1985). Statistical Analysis of Finite Mixture Distributions, Wiley."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2726","DOI":"10.1214\/16-AOS1444","article-title":"Convergence rates of parameter estimation for some weakly identifiable finite mixtures","volume":"44","author":"Ho","year":"2016","journal-title":"Ann. Stat."},{"key":"ref_39","unstructured":"Dwivedi, R., Ho, N., Khamaru, K., Wainwright, M., Jordan, M., and Yu, B. (2020, January 26\u201328). Sharp Analysis of Expectation-Maximization for Weakly Identifiable Models. Proceedings of the International Conference on Artificial Intelligence and Statistics, Online."},{"key":"ref_40","unstructured":"Winkelbauer, A. (2012). Moments and absolute moments of the normal distribution. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/78\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:27:47Z","timestamp":1760135267000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":40,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["a15030078"],"URL":"https:\/\/doi.org\/10.3390\/a15030078","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,25]]}}}