2018

Singularity, Misspecification, and the Convergence Rate of EM

Dwivedi, Raaz, Ho, Nhat, Khamaru, Koulik et al.

Understand

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 misspecified settings can lead to singularity in the Fisher information matrix, and moreover, the maximum likelihood estimator based on $n$ i.i.d.

Built on

[author] Dwivedi, RaazR., Ho, NhatN., Khamaru, KoulikK., Wainwright, Martin JM. J., Jordan, Michael IM. I. and Yu, BinB. (2019). Challenges with EM in application to weakly identifiable mixture models. arXiv preprint arXiv:1902.00194
Original
1902
Earlier work this paper cites.
[author] Wu, C. F. JeffC. F. J. (1983). On the convergence properties of the EM algorithm. The Annals of Statistics 11 95-103
1983
Earlier work this paper cites.
[author] Redner, Richard AR. A. and Walker, Homer FH. F. (1984). Mixture densities, maximum likelihood and the EM algorithm. SIAM review 26 195–239
1984
Earlier work this paper cites.
[author] Ledoux, M.M. and Talagrand, M.M. (1991). Probability in Banach Spaces: Isoperimetry and Processes. Springer-Verlag, New York, NY
1991
Earlier work this paper cites.
[author] Chen, J.J. (1995). Optimal rate of convergence for finite mixture models. The Annals of Statistics 23 221-233
1995
Earlier work this paper cites.
[author] Xu, L.L. and Jordan, M. I.M. I. (1996). On convergence properties of the EM Algorithm for Gaussian mixtures. Neural Computation 8 129-151
1996
Earlier work this paper cites.
[author] Dempster, A. P.A. P., Laird, N. M.N. M. and Rubin, D. B.D. B. (1997). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 39 1-38
1997
Earlier work this paper cites.
[author] Janson, S.S. (1997). Gaussian Hilbert Spaces 129. Cambridge University Press
1997
Earlier work this paper cites.
[author] Richardson, S.S. and Green, P. J.P. J. (1997). On Bayesian analysis of mixtures with an unknown number of components. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 59 731-792
1997
Earlier work this paper cites.
[author] van der Vaart, A. W.A. W. (1998). Asymptotic Statistics. Cambridge University Press
1998
Earlier work this paper cites.
[author] Ma, J.J., Xu, L.L. and Jordan, M. I.M. I. (2000). Asymptotic convergence rate of the EM algorithm for Gaussian mixtures. Neural Computation 12 2881-2907
2000
Earlier work this paper cites.
[author] van de Geer, S.S. (2000). Empirical Processes in M-estimation. Cambridge University Press
2000
Earlier work this paper cites.

Similar

[author] van der Vaart, A. W.A. W. and Wellner, J. A.J. A. (2000). Weak Convergence and Empirical Processes: With Applications to Statistics. Springer-Verlag, New York, NY
2000
Cited alongside, same era.
[author] Ghosal, S.S. and van der Vaart, A.A. (2001). Entropies and rates of convergence for maximum likelihood and Bayes estimation for mixtures of normal densities. The Annals of Statistics 29 1233-1263
2001
Cited alongside, same era.
[author] Ishwaran, H.H., James, L. F.L. F. and Sun, J.J. (2001). Bayesian model selection in finite mixtures by marginal density decompositions. Journal of the American Statistical Association 96 1316-1332
2001
Cited alongside, same era.
[author] Stephens, M.M. (2002). Dealing with label switching in mixture models. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 62 795-809
2002
Cited alongside, same era.
[author] Bartlett, P. L.P. L., Bousquet, O.O. and Mendelson, S.S. (2005). Local Rademacher complexities. The Annals of Statistics 33 1497–1537
2005
Cited alongside, same era.
[author] Koltchinskii, V.V. (2006). Local Rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics 34 2593–2656
2006
Cited alongside, same era.
[author] Chen, J.J. and Li, P.P. (2009). Hypothesis test for normal mixture models: the EM approach. The Annals of Statistics 37 2523-2542
2009
Cited alongside, same era.
[author] Li, P.P., Chen, J.J. and Marriott, P.P. (2009). Non-finite Fisher information and homogeneity: an EM approach. Biometrika 96 411-426
2009
Cited alongside, same era.
[author] Inglot, T.T. (2010). Inequalities for quantiles of the chi-square distribution. Probability and Mathematical Statistics 30 339–351
2010
Cited alongside, same era.
[author] Rousseau, J.J. and Mengersen, K.K. (2011). Asymptotic behaviour of the posterior distribution in overfitted mixture models. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 73 689-710
2011
Cited alongside, same era.
[author] Vershynin, R.R. (2011). Introduction to the non-asymptotic analysis of random matrices. arXiv:1011.3027v7
Original
2011
Cited alongside, same era.

Then

[author] Nguyen, X.X. (2013). Convergence of latent mixing measures in finite and infinite mixture models. The Annals of Statistics 4 370-400
2013
Later among the works it cites.
[author] Balakrishnan, S.S., Wainwright, M. J.M. J. and Yu, B.B. (2017). Statistical guarantees for the EM algorithm: From population to sample-based analysis. The Annals of Statistics 45 77-120
2017
Later among the works it cites.
Daskalakis, C
2017
Later among the works it cites.
[author] Kumar, R.R. and Schmidt, M.M. (2017). Convergence rate of expectation-maximization. 10th NIPS Workshop on Optimization for Machine Learning
2017
Later among the works it cites.
[author] Chen, Y. C.Y. C. (2018). Statistical inference with local optima. arXiv preprint arXiv:1807.04431
Original
2018
Closest in time.
Dwivedi, R
2018
Closest in time.
[author] Hao, B.B., Sun, W.W., Liu, Y.Y. and Cheng, G.G. (2018). Simultaneous clustering and estimation of heterogeneous graphical models. Journal of Machine Learning Research 18 1 - 58
2018
Closest in time.
[author] Heinrich, P.P. and Kahn, J.J. (2018). Strong identifiability and optimal minimax rates for finite mixture estimation. The Annals of Statistics 46 2844-2870
2018
Closest in time.
[author] Cai, T TonyT. T., Ma, JingJ., Zhang, LinjunL. et al. (2019). CHIME: Clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality. The Annals of Statistics 47 1234–1267
2019
Closest in time.
[author] Klusowski, Jason MJ. M., Yang, DanaD. and Brinda, WDW. (2019). Estimating the coefficients of a mixture of two linear regressions by expectation maximization. IEEE Transactions on Information Theory 65 3515–3524
2019
Closest in time.
[author] Wainwright, M. J.M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, Cambridge, UK
2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…