English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Expectation-Maximization (EM) algorithm is a widely used method formaximum likelihood estimation in models with latent variables. For estimatingmixtures of Gaussians, its iteration can be viewed as a soft version of thek-means clustering algorithm. Despite its wide use and applications, there areessentially no known convergence guarantees for this method. We provide globalconvergence guarantees for mixtures of two Gaussians with known covariancematrices. We show that the population version of EM, where the algorithm isgiven access to infinitely many samples from the mixture, convergesgeometrically to the correct mean vectors, and provide simple, closed-formexpressions for the convergence rate. As a simple illustration, we show that,in one dimension, ten steps of the EM algorithm initialized at infinity resultin less than 1\% error estimation of the means. In the finite sample regime, weshow that, under a random initialization, $\tilde{O}(d/\epsilon^2)$ samplessuffice to compute the unknown vectors to within $\epsilon$ in Mahalanobisdistance, where $d$ is the dimension. In particular, the error rate of the EMbased estimator is $\tilde{O}\left(\sqrt{d \over n}\right)$ where $n$ is thenumber of samples, which is optimal up to logarithmic factors.

Ten Steps of EM Suffice for Mixtures of Two Gaussians