北航数学论坛

题目:  Statistical and Computational Guarantees of EM with Random Initialization

报告人：Prof. Harrison Zhou （耶鲁大学）

时间： 6月10号 16:00-17:00

地点：主321

摘要: This talk considers parameter estimation in the two-component symmetric Gaussian mixtures in $d$ dimensions with $n$ independent samples. We show that, even in the absence of any separation between components, with high probability, the EM algorithm converges to an estimate in at most $O(\sqrt{n} \log n)$ iterations, which is within $O((d/n)^{1/4} (\log n)^{3/4})$ in Euclidean distance to the true parameter, provided that $n=\Omega(d \log^2 d)$. This is within a logarithmic factor to the minimax optimal rate of $(d/n)^{1/4}$. The proof relies on establishing (a) a non-linear contraction behavior of the population EM mapping (b) concentration of the EM trajectory near the population version, to prove that random initialization works. This is in contrast to previous analysis in Daskalakis, Tzamos, and Zampetakis (2017) that requires sample splitting and restart the EM iteration after normalization, and Balakrishnan, Wainwright, and Yu (2017) that requires strong conditions on both the separation of the components and the quality of the initialization. Furthermore, we obtain the asymptotic efficient estimation when the signal is stronger than the minimax rate.

报告人简介:  Prof. Harrison Zhou is a Henry Ford II Professor and Chair of the Department of Statistics and Data Science at Yale. His main research interests include asymptotic  decision theory, large covariance matrices estimation, graphical models, Bayesian nonparametrics, statistical network analysis, sparse canonical correlation analysis and principal component analysis, and analysis of iterative algorithms. His research has been acknowledged with awards including the National Science foundation Career Award, the Noether Young Scholar Award from the American Statistical Association, the Tweedie Award, the IMS Medallion lecture and IMS Fellow from the Institute of mathematical Statistics.

邀请人：陈迪荣