Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(n) iterations

DOI10.4171/MSL/29MaRDI QIDQ2113265zbMATH OpenFDO

Authors Yanyan Li

Publication date 11 March 2022

Published in Mathematical Statistics and Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.10935

zbMATH Keywords

convergence rateEM algorithmGaussian mixtureminimax ratesrandom initialization

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) Hypothesis testing in multivariate analysis (62H15)

Abstract: We analyze the classical EM algorithm for parameter estimation in the symmetric two-component Gaussian mixtures in $d$ dimensions. We show that, even in the absence of any separation between components, provided that the sample size satisfies $n=Omega(dlo{g}^{3}d)$, the randomly initialized EM algorithm converges to an estimate in at most $O(sqrtn)$ iterations with high probability, which is at most $O((fracdlo{g}^{3}nn{)}^{1/4})$ in Euclidean distance from the true parameter and within logarithmic factors of the minimax rate of $(fracdn{)}^{1/4}$. Both the nonparametric statistical rate and the sublinear convergence rate are direct consequences of the zero Fisher information in the worst case. Refined pointwise guarantees beyond worst-case analysis and convergence to the MLE are also shown under mild conditions. This improves the previous result of Balakrishnan et al cite{BWY17} which requires strong conditions on both the separation of the components and the quality of the initialization, and that of Daskalakis et al cite{DTZ17} which requires sample splitting and restarting the EM iteration.

Review text

Summary: We analyze the classical EM algorithm for parameter estimation in the symmetric two-component Gaussian mixtures in \(d\) dimensions. We show that, even in the absence of any separation between components, provided that the sample size satisfies \(n=\Omega (d \log^4 d)\), the randomly initialized EM algorithm converges to an estimate in at most \(O(\sqrt{n})\) iterations with high probability, which is at most \(O((d/n)^{1/4} \log n)\) in Euclidean distance from the true parameter and within logarithmic factors of the minimax rate of \((d/n)^{1/4}\). Both the nonparametric statistical rate and the sublinear convergence rate are direct consequences of the zero Fisher information in the worst case. Refined pointwise guarantees beyond worst-case analysis and convergence to the MLE are also shown under mild conditions. This improves the previous result of \textit{S. Balakrishnan} et al. [Ann. Stat. 45, No. 1, 77--120 (2017; Zbl 1367.62052)], which requires strong conditions on both the separation of the components and the quality of the initialization, and that of \textit{C. Daskalakis}, \textit{C. Tzamos} and \textit{M. Zampetakis} [``Ten steps of EM suffice for mixtures of two Gaussians, Proc. Mach. Learn. Res. (PMLR) 65, 704--710 (2017)], which requires sample splitting and restarting the EM iteration.

Recommendations

• Initializing the EM algorithm in Gaussian mixture models with an unknown number of components
• A greedy EM algorithm for Gaussian mixture learning
• scientific article; zbMATH DE number 5009269
• A Gaussian mixture model based k-means to initialize the EM algorithm
• Initializing the EM algorithm for univariate Gaussian, multi-component, heteroscedastic mixture models by dynamic programming partitions

Cites work

• Adaptive estimation of a quadratic functional by model selection.
• Asymptotic Statistics
• Choosing initial values for the EM algorithm for finite mixtures
• Choosing starting values for the EM algorithm for getting the highest likelihood in multivariate Gaussian mixture models
• Convergence rates of parameter estimation for some weakly identifiable finite mixtures
• Dissipation of Information in Channels With Input Constraints
• Entropies and rates of convergence for maximum likelihood and Bayes estimation for mixtures of normal densities.
• Functional Properties of Minimum Mean-Square Error and Mutual Information
• Generalized maximum likelihood estimation of normal mixture densities
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• scientific article; zbMATH DE number 3834852 (Why is no real title available?)
• scientific article; zbMATH DE number 5654889 (Why is no real title available?)
• scientific article; zbMATH DE number 3567782 (Why is no real title available?)
• Information-theoretic determination of minimax rates of convergence
• Mixture Densities, Maximum Likelihood and the EM Algorithm
• On the nonparametric maximum likelihood estimator for Gaussian location mixture densities with application to Gaussian denoising
• On the rate of convergence in Wasserstein distance of the empirical measure
• Optimal estimation of Gaussian mixtures via denoised method of moments
• Rates of convergence for the Gaussian mixture sieve.
• Singularity, misspecification and the convergence rate of EM
• Sparse PCA: optimal rates and adaptive estimation
• Statistical guarantees for the EM algorithm: from population to sample-based analysis
• The landscape of empirical risk for nonconvex losses
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• Trust Region Methods

Cited in

(15)

• Singularity, misspecification and the convergence rate of EM
• Sharp optimal recovery in the two component Gaussian mixture model
• Iterative algorithm for discrete structure recovery
• Improved convergence guarantees for learning Gaussian mixture models by EM and gradient EM
• Statistical convergence of the EM algorithm on Gaussian mixture models
• CHIME: clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality
• Statistical guarantees for the EM algorithm: from population to sample-based analysis
• Optimal estimation of high-dimensional Gaussian location mixtures
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Optimal estimation and computational limit of low-rank Gaussian mixtures
• Optimal clustering by Lloyd's algorithm for low-rank mixture model
• On the convergence of coordinate ascent variational inference
• Clustering a mixture of Gaussians with unknown covariance
• Sharp-SSL: Selective High-Dimensional Axis-Aligned Random Projections for Semi-Supervised Learning
• Convergence and optimality of the EM algorithm under multi-component Gaussian mixture models

This page was built for publication: Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \(O(\sqrt{n})\) iterations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113265)