Global analysis of Expectation Maximization for mixtures of two Gaussians

1 Introduction

• EM is popular for its simple iterations and practical performance, but likelihood algorithms may find stationary points far from the maximum-likelihood estimate.Marginalizing unobserved latent variables is a typical source of computational difficulty.Source: §1 · p. 1, §1.1 · p. 2

1.1 Expectation Maximization

• The analysis addresses unanswered questions about EM’s convergence and accuracy for i.i.d. samples from two-Gaussian mixtures by studying an infinite-sample version whose iterates depend on their initialization.The paper calls this idealization Population EM and contrasts it with Sample-based EM.Source: §1.1 · p. 2

1.2 Models and Main Contributions

• The paper analyzes two settings: a symmetric mixture with known covariance and unknown means ±θ⋆, and a two-mean Gaussian mixture with known covariance.Both models use equal mixture weights.Source: §1.2 · pp. 2–3
• Population EM converges to model-specific limit points, and the initial parameters determine which limit is reached; Sample-based EM is consistent when initialized where Population EM converges to the true parameters.For Model 1, the possible limits are θ⋆, −θ⋆, or 0; for Model 2, they are the two correctly ordered means or both means at their midpoint.Source: §1.2 · p. 3

1.3 Background and Related Work

• Unlike local analyses requiring sufficient separation, this work studies asymptotic limits globally; its scope complements finite-sample convergence guarantees for favorable initializations.Balakrishnan et al. (2014) analyze local convergence near the true parameters, while this paper reports a global analysis without a separation assumption.Source: §1.3 · p. 5

2.1 Main Results for Population EM

• For Model 1, Population EM converges to θ⋆ or −θ⋆ from nonorthogonal initializations, but to 0 when the initialization is orthogonal to θ⋆.Source: §2.1 · p. 5
• Theorem 3 states that re-parameterized Population EM iterates converge at a linear rate to the average of the two means; if ⟨b⟨0⟩, θ⋆⟩=0, they converge to (0, 0).Source: §2.1 · p. 6

2.2 Main Results for Sample-based EM

• Sample-based EM iterates and their fixed points converge in probability to the corresponding Population EM outcomes when initialized where Population EM converges to the parameters of interest.Source: §2.2 · p. 7

2.3 Population EM and Expected Log-likelihood

• For Model 1, the expected log-likelihood has only three stationary points: ±θ⋆ are global maxima, while 0 is a local minimum in one dimension and a saddle point in higher dimensions.Source: §2.3 · p. 8
• For Model 2, the expected log-likelihood likewise has three stationary points, with the first two global maxima and the third a saddle point.Source: §2.3 · p. 8

3 Concluding Remarks

• The analysis shows that, for the Gaussian mixture models studied, EM can compute statistically consistent parameter estimates.The authors say their large-sample results remove the need for specific initialization methods in that limit, not in every practical setting.Source: §3 · pp. 8–9
• Finite-sample behavior may differ from the large-sample limit, so initialization methods and non-asymptotic analysis remain needed to understand and apply EM.Source: §3 · p. 9
• The paper identifies growing dimension as a future direction, noting that Theorem 7’s limiting parameter error is of order d/n.Source: §3 · p. 9
• Extending the results to mixtures with unequal weights or covariances, and to other latent-variable models, remains future work.Source: §3 · p. 9

A.2 Connection Between Models 1 and 2

• For Population EM, the appendix connects Model 1 to Model 2 so analysis of the latter can be used to analyze the former.Source: §A.1 · p. 11, §A.2 · pp. 11–12

A.3 Some Structural Properties of Population EM

• Population EM updates are orthogonally invariant, and the iterates remain in the span of the initial estimate and the true parameter; under the stated initial-angle condition, that angle decreases.Source: §A.3 · pp. 12–14

A.5 Proof of Theorem 3

• The proof uses a decreasing angle and an increasing θ⋆ coordinate to bound the ratio involving Rs and θ⋆Ss at every iteration.Source: §A.5 · p. 19
• The proof establishes an upper bound on the iterates’ b norm and a positive lower bound on their b magnitude.The bounds support the argument that the relevant quantities in the convergence analysis stay controlled across iterations.Source: §A.5 · pp. 19–20
• A contraction inequality with a constant κa in (0, 1) bounds a term involving Γ and P by κa xa.Source: §A.5 · p. 20

A.5.1 Proof of Lemma 9

• Lemma 9’s proof bounds the a and b iterates, using a lower bound on P to control a and then deriving an upper bound on the b norm.Source: §A.5.1 · pp. 22–24

A.5.2 Proof of Lemma 10

• Lemma 10’s proof establishes a positive lower bound cl for the b magnitude, combining its behavior near zero with a continuity argument away from zero.Source: §A.5.2 · p. 25

A.6 Proof of Theorem 4

• When a is sufficiently small and b and the projected true parameter stay within specified positive bounds, the proof obtains a contraction bound for the b update.Source: §A.6 · pp. 29, 30, 33, 34
• The proof combines the established bounds and Lemma 18 to complete the argument for the theorem’s claim.Source: §A.6 · pp. 29, 34
• The proof reduces the update analysis to the first two coordinates, using that the iterates lie in the span of the true parameter and current estimate.Source: §A.6 · p. 29

A.7 Proof of Theorem 1

• Setting a⟨0⟩ = 0 keeps a⟨t⟩ = 0 and b⟨t⟩ = θ⟨t⟩, reducing the convergence analysis to the corresponding symmetric dynamics.The passage says convergence of the more general recursion then yields convergence of the symmetric one.Source: §A.7 · p. 35
• In the symmetric case, geometric convergence starts at iteration 1, strengthening the eventual geometric convergence guaranteed by Theorem 4 when the initial projection is positive.Theorem 4 gives a threshold T0; this proof seeks the stronger bound from the outset.Source: §A.7 · p. 36
• A rotation places b⟨t+1⟩ in the span of θ⋆ and b⟨t⟩, so the proof tracks only the first two rotated coordinates.The remaining rotated coordinates are zero.Source: §A.7 · p. 36

A.8.1 Main Steps of the Proof

• Population EM’s stationary points satisfy a = 0 and b ∈ {−θ⋆, 0, θ⋆}.The proof first characterizes the stationary points before analyzing the sequence’s accumulation points.Source: §A.8.1 · p. 37
• Every accumulation point of the Population EM sequence is shown to be a stationary point.This connects the sequence’s limiting behavior to the stationary-point characterization.Source: §A.8.1 · p. 37
• When ⟨b⟨0⟩, θ⋆⟩ = 0, the sequence cannot converge to either ±θ⋆, so it converges to (0, 0).All stationary points have a∞ = 0.Source: §A.8.1 · p. 37

A.8.2 Characterizing the Fixed Points of Population EM

• In one dimension, fixed points have a = 0 and b ∈ {−θ⋆, 0, θ⋆}; the higher-dimensional argument rotates coordinates to reduce the analysis.The proof establishes a = 0 as the only feasible value and then characterizes b; when a coordinate condition holds, it reduces to the one-dimensional case.Source: §A.8.2 · pp. 37–39

A.8.3 Proof of Convergence for Population EM

• When ⟨b⟨0⟩, θ⋆⟩ = 0, sign preservation implies ⟨b⟨t⟩, θ⋆⟩ = 0 for every t; the only possible fixed point and sole accumulation point are (0, 0).Source: §A.8.3 · p. 40

A.9 Proof of Theorem 6

• At each fixed iteration, the sample-based update for a converges in probability to the corresponding Population EM update.The proof establishes this by induction, using the weak law of large numbers and the continuous mapping theorem.Source: §A.9 · p. 41

A.10.1 Roadmap of the Proof

• From initialization near (0, θ⋆), sample-based EM converges with probability tending to 1 to a point at distance O(√(d/n)) from (0, θ⋆).The proof identifies a neighborhood of the target with the same O(√(d/n)) distance scale.Source: §A.10.1 · pp. 43–44

A.10.2 Proof of Lemma 20

• Lemma 20 bounds the iterate errors using contraction factors κa, κb ∈ (0, 1) and per-step error bounds εa, εb.The proof applies the lemma to control accumulated errors over iterations.Source: §A.10.1 · p. 44, §A.10.2 · pp. 48–49

A.10.1 Roadmap of the Proof

• When per-iteration errors are bounded by εa and εb, accumulated errors remain bounded, in the worst case proportionally to √εa and εb.Thus, errors that vanish as n grows yield vanishing overall errors under the lemma’s conditions.Source: §A.10.1 · p. 44

• The displayed bound fragments involve dimension d, sample size n, and failure probability δ.The passages do not provide enough of the inequalities to identify their bounded quantities.Source: §A.10.3 · pp. 49–50
• The observations are represented as y_i = ζ_iθ⋆ + ω_i, with Rademacher signs ζ_i and Gaussian noise ω_i.The mixture is 0.5N(θ⋆, I) + 0.5N(−θ⋆, I).Source: §A.10.3 · p. 49
• The proof combines symmetrization, Rademacher variables, and a 1/2-covering of the unit sphere to derive probability bounds.The stated probability guarantee is at least 1−δ.Source: §A.10.3 · pp. 51, 53

A.10.4 Proof of Lemma 22

• Under the lemma’s initialization conditions, one update contracts the error in a and bounds the next b-error by its previous error plus a term proportional to the a-error.The contraction factors and proportionality constant depend on the stated model bounds.Source: §A.10.4 · pp. 54–55

B.1 Proof of Lemma 4

• The cited relation states that, at iteration t+1, the inner product of a(t+1) and b(t+1) equals the squared norm of b(t+1) multiplied by (1 − 2p(t+1)).Source: §B.1 · p. 55

B.2 Proof of Lemma 5

• The expected weight w_d(Y−a,b) and its counterpart with −b sum to one.The proof uses this symmetry in an induction argument.Source: §B.2 · p. 57

B.3 Proof of Lemma 13

• For b≥0, the function P is decreasing in a.The proof treats separately the cases a≥θ and a<θ.Source: §B.3 · pp. 57–58

B.4 Proof of Lemma 12

• The proof bounds an expression involving W(x)=φ(x)−x(1−Φ(x)) using Lemma 25.It then applies that bound to the target inequality.Source: §B.4 · pp. 58–59

B.5 Proof of Lemma 25

• The auxiliary function r(x) is shown to be positive for every x>0 using its derivative behavior and endpoint values.The proof shows r first increases and then decreases.Source: §B.5 · pp. 59–60

B.6 Proof of Lemma 14

• The derivative under study exceeds 0.5, a fact used in a contradiction argument for Lemma 14.Source: §B.6 · p. 60

B.7 Proof of Lemma 15

• The proof establishes that an auxiliary function is increasing and concave for x≥0.Integration by parts is used in the derivative calculations.Source: §B.7 · p. 61

B.8 Proof of Lemma 16

• J(x)>0 for every x>0.The proof uses the behavior of J and its derivatives at zero and infinity.Source: §B.8 · pp. 61–62

B.9 Proof of Lemma 19

• F is increasing and strictly concave in x_b>0.Source: §B.9 · p. 62

B.10 Proof of Lemma 18

• Outside a δ-neighborhood of x_b=x_θ, the map F contracts the distance to x_θ under the stated parameter bounds.The contraction factor depends on L_b, U_b, L_θ, and ∥θ⋆∥.Source: §B.10 · p. 63

B.11 Cluster Points of Population EM

• Every cluster point of the Population EM estimates satisfies the stated fixed-point equations.The proof argues that successive iterate differences vanish before taking limits along a convergent subsequence.Source: §B.11 · p. 64
• The Population EM likelihood sequence is non-decreasing and converges.The proof uses that the likelihood is upper bounded.Source: §B.11 · p. 65
• The expected squared change in the component responsibilities tends to zero for each z∈{0,1}.The proof first establishes convergence on bounded observations, then controls the tail.Source: §B.11 · p. 66