Source-linked AI summary
Ten Steps of EM Suffice for Mixtures of Two Gaussians
Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis
TL;DR
Computing the likelihood requires summing over all latent-variable values, commonly making the log-likelihood non-convex in λ and hard to optimize. The paper analyzes population and finite-sample EM for balanced mixtures of two Gaussians with equal, known covariance matrices. Except for equidistant starts, population EM converges geometrically to either mean; when ε < SNR, Õ(d/ε^2 · poly(1/SNR)) samples suffice for ε-accurate Mahalanobis recovery.
Problem
Computing the likelihood requires summing over all latent-variable values, commonly making the log-likelihood non-convex in λ and hard to optimize.
Source: §1 · p. 2Method
The paper analyzes population and finite-sample EM for balanced mixtures of two Gaussians with equal, known covariance matrices.
Source: §1 · p. 2Results
Except for equidistant starts, population EM converges geometrically to either mean; when ε < SNR, Õ(d/ε^2 · poly(1/SNR)) samples suffice for ε-accurate Mahalanobis recovery.
Source: §1 · pp. 3–4Takeaways & Limitations
The analysis establishes global convergence guarantees for this two-Gaussian setting, including explicit population convergence rates and finite-sample bounds.
Source: §1 · pp. 2–4The setting is a balanced two-Gaussian mixture with equal covariance matrices.
Source: §1 · p. 2
Abstract
from arXiv · showhide
The Expectation-Maximization (EM) algorithm is a widely used method for maximum likelihood estimation in models with latent variables. For estimating mixtures of Gaussians, its iteration can be viewed as a soft version of the k-means clustering algorithm. Despite its wide use and applications, there are essentially no known convergence guarantees for this method. We provide global convergence guarantees for mixtures of two Gaussians with known covariance matrices. We show that the population version of EM, where the algorithm is given access to infinitely many samples from the mixture, converges geometrically to the correct mean vectors, and provide simple, closed-form expressions for the convergence rate. As a simple illustration, we show that, in one dimension, ten steps of the EM algorithm initialized at infinity result in less than 1\% error estimation of the means. In the finite sample regime, we show that, under a random initialization, $\tilde{O}(d/\epsilon^2)$ samples suffice to compute the unknown vectors to within $\epsilon$ in Mahalanobis distance, where $d$ is the dimension. In particular, the error rate of the EM based estimator is $\tilde{O}\left(\sqrt{d \over n}\right)$ where $n$ is the number of samples, which is optimal up to logarithmic factors.
1 Introduction
For balanced mixtures of two multidimensional Gaussians with equal, known covariance, the paper establishes global convergence guarantees for population and finite-sample EM. Its analysis covers arbitrary initializations apart from a measure-zero exception and includes convergence-rate and initialization results.
Motivation
- EM maximizes likelihood with latent variables, where summing over latent states can yield a non-convex objective that is hard to optimize.The paper studies balanced two-Gaussian mixtures with equal, known covariance matrices.Source: §1 · p. 2
Population EM
- Except for initializations equidistant from the two means, population EM converges geometrically to either true mean; equidistant starts converge to the unstable fixed point 0.With a one-dimensional initialization at infinity and SNR 1, ten steps yield 1% error.Source: §1 · p. 3
Motivation
- Earlier analysis of this setting established only local convergence; outside a small neighborhood, the update is non-contracting, leaving global convergence unresolved.The paper presents this as the gap its global analysis addresses.Source: §1 · p. 3
Population EM
- The convergence analysis uses sensitivity of the EM update to changes in the true parameters to reason about progress with the parameters fixed.The paper quantifies this relationship in Eq. (3.2); Figure 1 depicts the sensitivity and its connection to progress.Source: §1 · p. 4, Figure 1 · p. 4
Finite-Sample EM
- Finite-sample analysis estimates the mixture center, then couples correctly centered population updates to incorrectly centered updates and those to finite-sample updates.The sample-based iteration symmetrizes each sampled point with its negative; the analysis also goes through without this stabilization.Source: §1 · p. 4, Figure 2 · p. 5
- The informal finite-sample EM result states that whenever ε < SNR, Õ(d/ε² · poly(1/SNR)) samples suffice for the EM algorithm to approximate µ1 and µ2 within Mahalanobis distance ε.Source: §1 · p. 4
Bootstrapping EM
- Bootstrapping raises the initial projection onto the true mean above a constant, yielding an iteration count logarithmic in dimension for ε-accurate means.The paper contrasts this with a random unit vector's projection, which is on the order of 1/√d.Source: §1 · pp. 4–5
2 Preliminary Observations
The section identifies three fixed points of the EM update and simplifies the update using symmetry and the Gaussian density expressions.
2 Preliminary Observations
- M(−µ, µ), M(0, µ), and M(µ, µ) are fixed points of the EM iteration.The section obtains these by evaluating the update at −µ, 0, and µ.Source: §2 · p. 6
- Symmetry simplifies the rewritten update M(λ, µ).The section next simplifies common terms in the Gaussian densities to obtain an expression for the EM iteration.Source: §2 · p. 6
- The EM update is reformulated by simplifying common terms in the Gaussian densities N(x; λ, Σ).This simplification leads to the expression for the iteration.Source: §2 · p. 6
3 Single-dimensional Convergence
In one dimension, the update is increasing in the current estimate, and its fixed points are the two true means and an unstable zero. The convergence factor decreases over iterations.
3 Single-dimensional Convergence
- M(λ, µ) is strictly increasing in λ because its partial derivative with respect to λ is positive.The proof notes that tanh′ is strictly positive.Source: §3 · p. 6
- For a positive initialization, the update converges toward µ, while a negative initialization converges toward −µ; zero is an unstable fixed point.The section identifies these as the only fixed points of M(·, µ).Source: §3 · p. 6
- κ(t) decreases with t, so the convergence factor improves as the iterations proceed.The theorem states that κ(t) is decreasing.Source: §3 · p. 6
- The proof bounds progress between successive estimates using the Mean Value Theorem applied to the second coordinate of M over [λ, µ].The argument then seeks a lower bound on the partial derivative of M with respect to µ.Source: §3 · p. 7
4 Multi-dimensional Convergence
In multiple dimensions, EM converges to the nearer true mean except for initializations equidistant from the two means, which remain at zero. The convergence factor decreases across iterations.
4 Multi-dimensional Convergence
- The multidimensional analysis measures approximation guarantees with Mahalanobis distance defined using covariance matrix Σ.It applies a change of variables to reduce the covariance matrix to the identity before analyzing the iteration.Source: §4 · p. 8
- An initialization closer to µ than −µ leads EM to converge to µ; an equidistant initialization instead stays at zero.The symmetric case converges to −µ when the initialization is closer to −µ.Source: §4 · p. 8
- The convergence factor κ(t) decreases as the iterations increase.The analysis establishes this by showing that a minimum projection measure does not decrease across updates.Source: §4 · pp. 8–9
- The coordinate analysis reduces one component of the update to a one-dimensional EM iteration, while components indexed i ≥ 3 vanish.The basis is chosen with λ and its in-plane perpendicular direction as its first two vectors.Source: §4 · pp. 8–9
5 An Illustration of the Speed of Convergence
The section illustrates how quickly EM converges in one and multiple dimensions. Its examples show a ten-iteration, 1% error result from an infinitely distant one-dimensional initialization and describe how initialization and signal-to-noise ratio affect convergence.
5 An Illustration of the Speed of Convergence
- For SNRs above 1 convergence is faster; below 1, the reported numbers change gracefully.Source: §5 · p. 10
- At SNR η=1, 10 EM iterations from λ(0)→+∞ yield 1% error in estimating µ.The components are not separated at this SNR.Source: §5 · p. 10
- In multiple dimensions, update directions and decay rates depend on the iterate’s distance from the origin and its angle to µ.Points equidistant from µ and −µ move to 0; points closer to either mean move toward it.Source: §5 · p. 10, Figure 4 · p. 11
- Random initialization gives O(d/SNR^2 · log(1/ϵ)) iterations, while bootstrapping improves the angle to Ω(1) in O(log d/SNR^2) iterations, followed by O(1/SNR^2 · log(1/ϵ)).Source: §5 · p. 11
6 Sample Based Model
This section establishes finite-sample guarantees for EM through a procedure with centering, bootstrap initialization, and a main execution stage. Its analysis accounts for center-estimation error, stabilizes the iteration by adding each sample’s symmetric point, and uses concentration to control the difference between sample-based and population EM iterations.
6.3 Initialization of EM
- O(log d/SNR^2) bootstrap EM iterations from a small-norm random start produce a direction with ⟨λ̂, µ̂⟩Σ ≥ 1/2.The bootstrap uses the approximate linearization of tanh, which makes the update an empirical-covariance power-method iteration; the empirical covariance’s principal eigenvector aligns with µ̂, and the power method reaches a constant angle in O(log d/min(µ^2, 1)) iterations.Source: §6 · p. 12, §6.3 · pp. 14, 18
6 Sample Based Model
- For ε ≤ SNR, Theorem 3 gives an estimate using Õ(d/ε^2) · poly(1/SNR) · log(1/η) samples, with the goal of ε accuracy in Mahalanobis distance.The section states the target as ∥λ − µ∥Σ ≤ ε with high probability.Source: §6 · p. 12
6.1 Centering
- Õ(d/ε^2 · log(1/η)) samples estimate the mixture center with error at most ε in Mahalanobis distance with failure probability η.The estimator averages the empirical first and third quartiles separately along each coordinate axis.Source: §6.1 · p. 13
6.2 Sample Based EM Iteration
- After centering by the estimated mean, finite-sample EM adds each sample’s negative to the data; this stabilization simplifies analysis, but the results also hold without it.The centering error shifts the component means to µ + δ and −µ + δ.Source: §6.2 · p. 13
6.4 Finite-Sample EM Analysis
- The finite-sample analysis compares the sample-based iteration with a population iteration that accounts for centering error and the symmetric-sample construction.The section says the proof follows two steps, but this passage does not specify them.Source: §6.4 · p. 19
- The analysis proceeds by relating the population iteration to the vanilla population EM iteration, then to the sample-based iteration.It uses Theorem 2 to analyze the population iteration before bounding the sample iterate’s deviation from it.Source: §6.4 · pp. 19–20
- Lemma 10 analyzes concentration of the sample-based iterate around its mean, assuming fresh samples at the next time step.The lemma’s displayed sample-size and concentration bounds are incomplete in the supplied passages.Source: §6.4 · p. 21
- ˜O(d/(ε^2μ^4)) samples are used in the proof of Theorem 3 to obtain its finite-sample guarantee.The following proof passages treat the case μ > 1 separately, but their displayed sample bound is incomplete in the supplied text.Source: §6.4 · pp. 25–26