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

DOI10.4171/MSL/29zbMATH Open1493.62350arXiv1908.10935MaRDI QIDQ2113265FDOQ2113265

Authors: Yanyan Li 

Publication date: 11 March 2022

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

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.

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

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

zbMATH Keywords

EM algorithmconvergence rateminimax ratesGaussian mixturerandom initialization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Optimal estimation and computational limit of low-rank Gaussian mixtures
• Optimal estimation of high-dimensional Gaussian location mixtures
• Sharp optimal recovery in the two component Gaussian mixture model
• Iterative algorithm for discrete structure recovery

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)