{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T15:55:09Z","timestamp":1791474909917,"version":"4.3.4"},"reference-count":33,"publisher":"Institute of Mathematical Statistics","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2020,12,1]]},"abstract":"<jats:p>A line of recent work has analyzed the behavior of the Expectation-Maximization (EM) algorithm in the well-specified setting, in which the population likelihood is locally strongly concave around its maximizing argument. Examples include suitably separated Gaussian mixture models and mixtures of linear regressions. We consider over-specified settings in which the number of fitted components is larger than the number of components in the true distribution. Such mis-specified settings can lead to singularity in the Fisher information matrix, and moreover, the maximum likelihood estimator based on $n$ i.i.d. samples in $d$ dimensions can have a nonstandard $\\mathcal{O}((d\/n)^{\\frac{1}{4}})$ rate of convergence. Focusing on the simple setting of two-component mixtures fit to a $d$-dimensional Gaussian distribution, we study the behavior of the EM algorithm both when the mixture weights are different (unbalanced case), and are equal (balanced case). Our analysis reveals a sharp distinction between these two cases: in the former, the EM algorithm converges geometrically to a point at Euclidean distance of $\\mathcal{O}((d\/n)^{\\frac{1}{2}})$ from the true parameter, whereas in the latter case, the convergence rate is exponentially slower, and the fixed point has a much lower $\\mathcal{O}((d\/n)^{\\frac{1}{4}})$ accuracy. Analysis of this singular case requires the introduction of some novel techniques: in particular, we make use of a careful form of localization in the associated empirical process, and develop a recursive argument to progressively sharpen the statistical rate.<\/jats:p>","DOI":"10.1214\/19-aos1924","type":"journal-article","created":{"date-parts":[[2020,12,11]],"date-time":"2020-12-11T04:02:41Z","timestamp":1607659361000},"page":"3161-3182","source":"Crossref","is-referenced-by-count":31,"title":["Singularity, misspecification and the convergence rate of EM"],"prefix":"10.1214","volume":"48","author":[{"given":"Raaz","family":"Dwivedi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nhat","family":"Ho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Koulik","family":"Khamaru","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin J.","family":"Wainwright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael I.","family":"Jordan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Yu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] Bartlett, P. L., Bousquet, O. and Mendelson, S. (2005). Local rademacher complexities. <i>Ann. Statist.<\/i> <b>33<\/b> 1497\u20131537.","DOI":"10.1214\/009053605000000282"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] Koltchinskii, V. (2006). Local Rademacher complexities and oracle inequalities in risk minimization. <i>Ann. Statist.<\/i> <b>34<\/b> 2593\u20132656.","DOI":"10.1214\/009053606000001019"},{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] Balakrishnan, S., Wainwright, M. J. and Yu, B. (2017). Statistical guarantees for the EM algorithm: From population to sample-based analysis. <i>Ann. Statist.<\/i> <b>45<\/b> 77\u2013120.","DOI":"10.1214\/16-AOS1435"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] Cai, T. T., Ma, J. and Zhang, L. (2019). CHIME: Clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality. <i>Ann. Statist.<\/i> <b>47<\/b> 1234\u20131267.","DOI":"10.1214\/18-AOS1711"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] Chen, J. and Li, P. (2009). Hypothesis test for normal mixture models: The EM approach. <i>Ann. Statist.<\/i> <b>37<\/b> 2523\u20132542.","DOI":"10.1214\/08-AOS651"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] Chen, J. H. (1995). Optimal rate of convergence for finite mixture models. <i>Ann. Statist.<\/i> <b>23<\/b> 221\u2013233.","DOI":"10.1214\/aos\/1176324464"},{"key":"6","unstructured":"[6] Chen, Y. C. (2018). Statistical inference with local optima. Preprint. Available at <a href=\"arXiv:1807.04431\">arXiv:1807.04431<\/a>."},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] Dempster, A. P., Laird, N. M. and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. <i>J. Roy. Statist. Soc. Ser. B<\/i> <b>39<\/b> 1\u201338.","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] Dwivedi, R., Ho, N., Khamaru, K., Wainwright, M. J., Jordan, M. I. and Yu, B. (2020). Supplement to \u201cSingularity, misspecification and the convergence rate of EM.\u201d <a href=\"https:\/\/doi.org\/10.1214\/19-AOS1924SUPP\">https:\/\/doi.org\/10.1214\/19-AOS1924SUPP<\/a>","DOI":"10.1214\/19-AOS1924SUPP"},{"key":"11","unstructured":"[11] Dwivedi, R., Ho, N., Khamaru, K., Wainwright, M. J., Jordan, M. I. and Yu, B. (2019). Challenges with EM in application to weakly identifiable mixture models. Preprint. Available at <a href=\"arXiv:1902.00194\">arXiv:1902.00194<\/a>."},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] Ghosal, S. and van der Vaart, A. W. (2001). Entropies and rates of convergence for maximum likelihood and Bayes estimation for mixtures of normal densities. <i>Ann. Statist.<\/i> <b>29<\/b> 1233\u20131263.","DOI":"10.1214\/aos\/1013203453"},{"key":"13","unstructured":"[13] Hao, B., Sun, W. W., Liu, Y. and Cheng, G. (2018). Simultaneous clustering and estimation of heterogeneous graphical models. <i>J. Mach. Learn. Res.<\/i> <b>18<\/b> Art. ID 217."},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] Heinrich, P. and Kahn, J. (2018). Strong identifiability and optimal minimax rates for finite mixture estimation. <i>Ann. Statist.<\/i> <b>46<\/b> 2844\u20132870.","DOI":"10.1214\/17-AOS1641"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] Ishwaran, H., James, L. F. and Sun, J. (2001). Bayesian model selection in finite mixtures by marginal density decompositions. <i>J. Amer. Statist. Assoc.<\/i> <b>96<\/b> 1316\u20131332.","DOI":"10.1198\/016214501753382255"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] Klusowski, J. M., Yang, D. and Brinda, W. D. (2019). Estimating the coefficients of a mixture of two linear regressions by expectation maximization. <i>IEEE Trans. Inform. Theory<\/i> <b>65<\/b> 3515\u20133524.","DOI":"10.1109\/TIT.2019.2891628"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] Li, P., Chen, J. and Marriott, P. (2009). Non-finite Fisher information and homogeneity: An EM approach. <i>Biometrika<\/i> <b>96<\/b> 411\u2013426.","DOI":"10.1093\/biomet\/asp011"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] Ma, J., Xu, L. and Jordan, M. I. (2000). Asymptotic convergence rate of the EM algorithm for Gaussian mixtures. <i>Neural Comput.<\/i> <b>12<\/b> 2881\u20132907.","DOI":"10.1162\/089976600300014764"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] Nguyen, X. (2013). Convergence of latent mixing measures in finite and infinite mixture models. <i>Ann. Statist.<\/i> <b>41<\/b> 370\u2013400.","DOI":"10.1214\/12-AOS1065"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] 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":"23","doi-asserted-by":"publisher","unstructured":"[23] Richardson, S. and Green, P. J. (1997). On Bayesian analysis of mixtures with an unknown number of components. <i>J. Roy. Statist. Soc. Ser. B<\/i> <b>59<\/b> 731\u2013792.","DOI":"10.1111\/1467-9868.00095"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] Rousseau, J. and Mengersen, K. (2011). Asymptotic behaviour of the posterior distribution in overfitted mixture models. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>73<\/b> 689\u2013710.","DOI":"10.1111\/j.1467-9868.2011.00781.x"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] Stephens, M. (2000). Dealing with label switching in mixture models. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>62<\/b> 795\u2013809.","DOI":"10.1111\/1467-9868.00265"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] Wainwright, M. J. (2019). <i>High-Dimensional Statistics: A Non-Asymptotic Viewpoint<\/i>. <i>Cambridge Series in Statistical and Probabilistic Mathematics<\/i> <b>48<\/b>. Cambridge Univ. Press, Cambridge.","DOI":"10.1017\/9781108627771"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[29] 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":"31","doi-asserted-by":"publisher","unstructured":"[31] 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_a_00154"},{"key":"7","unstructured":"[7] Daskalakis, C., Tzamos, C. and Zampetakis, M. (2017). Ten steps of EM suffice for mixtures of two Gaussians. In <i>Proceedings of the 2017 Conference on Learning Theory<\/i>."},{"key":"9","unstructured":"[9] Dwivedi, R., Ho, N., Khamaru, K., Wainwright, M. J. and Jordan, M. I. (2018). Theoretical guarantees for EM under misspecified Gaussian mixture models. In <i>NeurIPS 31<\/i>."},{"key":"18","unstructured":"[18] Kumar, R. and Schmidt, M. (2017). Convergence rate of expectation-maximization. In <i>10th NIPS Workshop on Optimization for Machine Learning<\/i>."},{"key":"26","unstructured":"[26] van de Geer, S. (2000). <i>Empirical Processes in M-Estimation<\/i>. Cambridge Univ. Press, Cambridge."},{"key":"28","unstructured":"[28] Wang, Z., Gu, Q., Ning, Y. and Liu, H. (2015). High-dimensional expectation-maximization algorithm: Statistical optimization and asymptotic normality. In <i>Advances in Neural Information Processing Systems 28<\/i>."},{"key":"30","unstructured":"[30] Xu, J., Hsu, D. and Maleki, A. (2016). Global analysis of expectation maximization for mixtures of two Gaussians. In <i>Advances in Neural Information Processing Systems 29<\/i>."},{"key":"32","unstructured":"[32] Yan, B., Yin, M. and Sarkar, P. (2017). Convergence of gradient EM on multi-component mixture of Gaussians. In <i>Advances in Neural Information Processing Systems 30<\/i>."},{"key":"33","unstructured":"[33] Yi, X. and Caramanis, C. (2015). Regularized EM algorithms: A unified framework and statistical guarantees. In <i>Advances in Neural Information Processing Systems 28<\/i>."}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1607677231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T15:21:20Z","timestamp":1791472880000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-48\/issue-6\/Singularity-misspecification-and-the-convergence-rate-of-EM\/10.1214\/19-AOS1924.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,1]]},"references-count":33,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2020,12,1]]}},"URL":"https:\/\/doi.org\/10.1214\/19-aos1924","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,1]]}}}