{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T02:01:12Z","timestamp":1792548072197,"version":"4.5.0"},"reference-count":53,"publisher":"Institute of Mathematical Statistics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2017,2,1]]},"abstract":"<jats:p>The EM algorithm is a widely used tool in maximum-likelihood estimation in incomplete data problems. Existing theoretical work has focused on conditions under which the iterates or likelihood values converge, and the associated rates of convergence. Such guarantees do not distinguish whether the ultimate fixed point is a near global optimum or a bad local optimum of the sample likelihood, nor do they relate the obtained fixed point to the global optima of the idealized population likelihood (obtained in the limit of infinite data). This paper develops a theoretical framework for quantifying when and how quickly EM-type iterates converge to a small neighborhood of a given global optimum of the population likelihood. For correctly specified models, such a characterization yields rigorous guarantees on the performance of certain two-stage estimators in which a suitable initial pilot estimator is refined with iterations of the EM algorithm. Our analysis is divided into two parts: a treatment of the EM and first-order EM algorithms at the population level, followed by results that apply to these algorithms on a finite set of samples. Our conditions allow for a characterization of the region of convergence of EM-type iterates to a given population fixed point, that is, the region of the parameter space over which convergence is guaranteed to a point within a small neighborhood of the specified population fixed point. We verify our conditions and give tight characterizations of the region of convergence for three canonical problems of interest: symmetric mixture of two Gaussians, symmetric mixture of two regressions and linear regression with covariates missing completely at random.<\/jats:p>","DOI":"10.1214\/16-aos1435","type":"journal-article","created":{"date-parts":[[2017,2,21]],"date-time":"2017-02-21T04:01:04Z","timestamp":1487649664000},"page":"77-120","source":"Crossref","is-referenced-by-count":214,"title":["Statistical guarantees for the EM algorithm: From population to sample-based analysis"],"prefix":"10.1214","volume":"45","author":[{"given":"Sivaraman","family":"Balakrishnan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin J.","family":"Wainwright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Yu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M. and Telgarsky, M. (2012). Tensor decompositions for learning latent variable models. Preprint. Available at <a href=\"arXiv:1210.7559\">arXiv:1210.7559<\/a>.","DOI":"10.21236\/ADA604494"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] Balakrishnan, S., Wainwright, M. J. and Yu, B. (2014). Supplement to \u201cStatistical guarantees for the EM algorithm: From population to sample-based analysis.\u201d <a href=\"DOI:10.1214\/16-AOS1435SUPP\">DOI:10.1214\/16-AOS1435SUPP<\/a>.","DOI":"10.1214\/16-AOS1435SUPP"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] Balan, R., Casazza, P. and Edidin, D. (2006). On signal reconstruction without phase. <i>Appl. Comput. Harmon. Anal.<\/i> <b>20<\/b> 345\u2013356.","DOI":"10.1016\/j.acha.2005.07.001"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] Baum, L. E., Petrie, T., Soules, G. and Weiss, N. (1970). A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. <i>Ann. Math. Stat.<\/i> <b>41<\/b> 164\u2013171.","DOI":"10.1214\/aoms\/1177697196"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] Beale, E. M. L. and Little, R. J. A. (1975). Missing values in multivariate analysis. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>37<\/b> 129\u2013145.","DOI":"10.1111\/j.2517-6161.1975.tb01037.x"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] Buldygin, V. V. and Kozachenko, Yu. V. (2000). <i>Metric Characterization of Random Variables and Random Processes. Translations of Mathematical Monographs<\/i> <b>188<\/b>. Amer. Math. Soc., Providence, RI. Translated from the 1998 Russian original by V. Zaiats.","DOI":"10.1090\/mmono\/188"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] Cand\u00e8s, E. J., Strohmer, T. and Voroninski, V. (2013). PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming. <i>Comm. Pure Appl. Math.<\/i> <b>66<\/b> 1241\u20131274.","DOI":"10.1002\/cpa.21432"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] Celeux, G. and Govaert, G. (1992). A classification EM algorithm for clustering and two stochastic versions. <i>Comput. Statist. Data Anal.<\/i> <b>14<\/b> 315\u2013332.","DOI":"10.1016\/0167-9473(92)90042-E"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Chr\u00e9tien, S. and Hero, A. O. (2008). On EM algorithms and their proximal generalizations. <i>ESAIM Probab. Stat.<\/i> <b>12<\/b> 308\u2013326.","DOI":"10.1051\/ps:2007041"},{"key":"16","unstructured":"[16] Dasgupta, S. and Schulman, L. (2007). A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. <i>J. Mach. Learn. Res.<\/i> <b>8<\/b> 203\u2013226."},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] Dempster, A. P., Laird, N. M. and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>39<\/b> 1\u201338.","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] Hartley, H. O. (1958). Maximum likelihood estimation from incomplete data. <i>Biometrics<\/i> <b>14<\/b> 174\u2013194.","DOI":"10.2307\/2527783"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] Healy, M. and Westmacott, M. (1956). Missing values in experiments analysed on automatic computers. <i>J. R. Stat. Soc. Ser. C. Appl. Stat.<\/i> <b>5<\/b> 203\u2013206.","DOI":"10.2307\/2985421"},{"key":"20","unstructured":"[20] Hero, A. O. and Fessler, J. A. (1995). Convergence in norm for alternating expectation-maximization (EM) type algorithms. <i>Statist. Sinica<\/i> <b>5<\/b> 41\u201354."},{"key":"21","unstructured":"[21] Hsu, D. and Kakade, S. M. (2012). Learning Gaussian mixture models: Moment methods and spectral decompositions. Preprint. Available at <a href=\"arXiv:1206.5766\">arXiv:1206.5766<\/a>."},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] Iturria, S. J., Carroll, R. J. and Firth, D. (1999). Polynomial regression and estimating functions in the presence of multiplicative measurement error. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>61<\/b> 547\u2013561.","DOI":"10.1111\/1467-9868.00192"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] Koltchinskii, V. (2011). <i>Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems. Lecture Notes in Math.<\/i> <b>2033<\/b>. Springer, Heidelberg.","DOI":"10.1007\/978-3-642-22147-7"},{"key":"25","doi-asserted-by":"crossref","unstructured":"[25] Liu, C. and Rubin, D. B. (1994). The ECME algorithm: A simple extension of EM and ECM with faster monotone convergence. <i>Biometrika<\/i> <b>81<\/b> 633\u2013648.","DOI":"10.1093\/biomet\/81.4.633"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] Louis, T. A. (1982). Finding the observed information matrix when using the EM algorithm. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>44<\/b> 226\u2013233.","DOI":"10.1111\/j.2517-6161.1982.tb01203.x"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] Ma, J. and Xu, L. (2005). Asymptotic convergence properties of the EM algorithm with respect to the overlap in the mixture. <i>Neurocomputing<\/i> <b>68<\/b> 105\u2013129.","DOI":"10.1016\/j.neucom.2004.12.009"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] Meilijson, I. (1989). A fast improvement to the EM algorithm on its own terms. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>51<\/b> 127\u2013138.","DOI":"10.1111\/j.2517-6161.1989.tb01754.x"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] Meng, X. (1994). On the rate of convergence of the ECM algorithm. <i>Ann. Statist.<\/i> <b>22<\/b> 326\u2013339.","DOI":"10.1214\/aos\/1176325371"},{"key":"32","doi-asserted-by":"crossref","unstructured":"[32] Meng, X. and Rubin, D. B. (1993). Maximum likelihood estimation via the ECM algorithm: A general framework. <i>Biometrika<\/i> <b>80<\/b> 267\u2013278.","DOI":"10.1093\/biomet\/80.2.267"},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] Meng, X. and Rubin, D. B. (1994). On the global and componentwise rates of convergence of the EM algorithm. <i>Linear Algebra Appl.<\/i> <b>199<\/b> 413\u2013425.","DOI":"10.1016\/0024-3795(94)90363-8"},{"key":"35","doi-asserted-by":"crossref","unstructured":"[35] Nesterov, Y. (2004). <i>Introductory Lectures on Convex Optimization<\/i>: <i>A Basic Course. Applied Optimization<\/i> <b>87<\/b>. Kluwer Academic, Boston, MA.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] Orchard, T. and Woodbury, M. A. (1972). A missing information principle: Theory and applications. In <i>Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability<\/i> (<i>Univ. California<\/i>, <i>Berkeley<\/i>, <i>Calif.<\/i>, 1970<i>\/<\/i>1971), <i>Theory of Statistics<\/i> <b>1<\/b> 697\u2013715. Univ. California Press, Berkeley, CA.","DOI":"10.1525\/9780520325883-036"},{"key":"39","doi-asserted-by":"crossref","unstructured":"[39] Redner, R. A. and Walker, H. F. (1984). Mixture densities, maximum likelihood and the EM algorithm. <i>SIAM Rev.<\/i> <b>26<\/b> 195\u2013239.","DOI":"10.1137\/1026034"},{"key":"40","doi-asserted-by":"crossref","unstructured":"[40] Rubin, D. B. (1974). Characterizing the estimation of parameters in incomplete-data problems. <i>J. Amer. Statist. Assoc.<\/i> <b>69<\/b> 467\u2013474.","DOI":"10.1080\/01621459.1974.10482976"},{"key":"41","unstructured":"[41] Sundberg, R. (1974). Maximum likelihood theory for incomplete data from an exponential family. <i>Scand. J. Stat.<\/i> <b>1<\/b> 49\u201358."},{"key":"42","doi-asserted-by":"crossref","unstructured":"[42] Tanner, M. A. and Wong, W. H. (1987). The calculation of posterior distributions by data augmentation. <i>J. Amer. Statist. Assoc.<\/i> <b>82<\/b> 528\u2013550.","DOI":"10.1080\/01621459.1987.10478458"},{"key":"43","doi-asserted-by":"crossref","unstructured":"[43] Tseng, P. (2004). An analysis of the EM algorithm and entropy-like proximal point methods. <i>Math. Oper. Res.<\/i> <b>29<\/b> 27\u201344.","DOI":"10.1287\/moor.1030.0073"},{"key":"49","doi-asserted-by":"crossref","unstructured":"[49] Wei, G. and Tanner, M. A. (1990). A Monte Carlo implementation of the EM algorithm and the poor man\u2019s data augmentation algorithm. <i>J. Amer. Statist. Assoc.<\/i> <b>85<\/b> 699\u2013704.","DOI":"10.1080\/01621459.1990.10474930"},{"key":"50","doi-asserted-by":"crossref","unstructured":"[50] Wu, C.-F. J. (1983). On the convergence properties of the EM algorithm. <i>Ann. Statist.<\/i> <b>11<\/b> 95\u2013103.","DOI":"10.1214\/aos\/1176346060"},{"key":"51","doi-asserted-by":"crossref","unstructured":"[51] Xu, L. and Jordan, M. I. (1996). On convergence properties of the EM algorithm for Gaussian mixtures. <i>Neural Comput.<\/i> <b>8<\/b> 129\u2013151.","DOI":"10.1162\/neco.1996.8.1.129"},{"key":"52","doi-asserted-by":"crossref","unstructured":"[52] Xu, Q. and You, J. (2007). Covariate selection for linear errors-in-variables regression models. <i>Comm. Statist. Theory Methods<\/i> <b>36<\/b> 375\u2013386.","DOI":"10.1080\/03610920600974765"},{"key":"46","doi-asserted-by":"crossref","unstructured":"[46] van der Vaart, A. W. and Wellner, J. A. (1996). <i>Weak Convergence and Empirical Processes<\/i>. Springer, New York.","DOI":"10.1007\/978-1-4757-2545-2"},{"key":"2","unstructured":"[2] Anandkumar, A., Jain, P., Netrapalli, P. and Tandon, R. (2013). Learning sparsely used overcomplete dictionaries via alternating minimization. Technical report, Microsoft Research, Redmond, OR."},{"key":"7","unstructured":"[7] Bertsekas, D. P. (1995). <i>Nonlinear Programming<\/i>. Athena Scientific, Belmont, CA."},{"key":"8","unstructured":"[8] Bubeck, S. (2014). Theory of convex optimization for machine learning. Unpublished manuscript."},{"key":"11","unstructured":"[11] Celeux, G., Chauveau, D. and Diebolt, J. (1995). On stochastic versions of the EM algorithm. Technical Report, No. 2514, INRIA."},{"key":"13","unstructured":"[13] Chaganty, A. T. and Liang, P. (2013). Spectral experts for estimating mixtures of linear regressions. Unpublished manuscript."},{"key":"14","unstructured":"[14] Chen, Y., Yi, X. and Caramanis, C. (2013). A convex formulation for mixed regression: Near optimal rates in the face of noise. Unpublished manuscript."},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] Ledoux, M. and Talagrand, M. (1991). <i>Probability in Banach Spaces<\/i>: <i>Isoperimetry and Processes<\/i>. Springer, Berlin.","DOI":"10.1007\/978-3-642-20212-4"},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] Loh, P. and Wainwright, M. J. (2012). Corrupted and missing predictors: Minimax bounds for high-dimensional linear regression. In <i>ISIT<\/i> 2601\u20132605. IEEE, Piscataway Township, NJ.","DOI":"10.1109\/ISIT.2012.6283989"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] McLachlan, G. and Krishnan, T. (2007). <i>The EM Algorithm and Extensions<\/i>. Wiley, New York.","DOI":"10.1002\/9780470191613"},{"key":"34","doi-asserted-by":"crossref","unstructured":"[34] Neal, R. M. and Hinton, G. E. (1999). A view of the EM algorithm that justifies incremental, sparse, and other variants. In <i>Learning in Graphical Models<\/i> (M. I. Jordan, ed.) 355\u2013368. MIT Press, Cambridge, MA.","DOI":"10.1007\/978-94-011-5014-9_12"},{"key":"36","unstructured":"[36] Netrapalli, P., Jain, P. and Sanghavi, S. (2013). Phase retrieval using alternating minimization. In <i>Neural Information Processing Systems<\/i> Curran Associates, Inc., Red Hook, New York 2796\u20132804."},{"key":"38","doi-asserted-by":"crossref","unstructured":"[38] Pearson, K. (1894). <i>Contributions to the Mathematical Theory of Evolution<\/i>. Harrison and Sons, London.","DOI":"10.1098\/rsta.1894.0003"},{"key":"44","unstructured":"[44] van Dyk, D. A. and Meng, X. L. (2000). Algorithms based on data augmentation: A graphical representation and comparison. In <i>Computing Science and Statistics<\/i>: <i>Proceedings of the<\/i> 31<i>st Symposium on the Interface<\/i> 230\u2013239. Interface Foundation of North America, Fairfax Station, VA."},{"key":"45","unstructured":"[45] van de Geer, S. (2000). <i>Empirical Processes in M-Estimation<\/i>. Cambridge Univ. Press, Cambridge."},{"key":"47","doi-asserted-by":"crossref","unstructured":"[47] Vershynin, R. (2012). Introduction to the non-asymptotic analysis of random matrices. In <i>Compressed Sensing<\/i> 210\u2013268. Cambridge Univ. Press, Cambridge.","DOI":"10.1017\/CBO9780511794308.006"},{"key":"48","unstructured":"[48] Wang, Z., Gu, Q., Ning, Y. and Liu, H. (2014). High dimensional expectation-maximization algorithm: Statistical optimization and asymptotic normality. Unpublished manuscript."},{"key":"53","unstructured":"[53] Yi, X., Caramanis, C. and Sanghavi, S. (2013). Alternating minimization for mixed linear regression. Unpublished manuscript."}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"http:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1487667618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T18:46:43Z","timestamp":1791485203000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-45\/issue-1\/Statistical-guarantees-for-the-EM-algorithm--From-population-to\/10.1214\/16-AOS1435.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,1]]},"references-count":53,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,2,1]]}},"URL":"https:\/\/doi.org\/10.1214\/16-aos1435","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,1]]}}}