PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences

Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin J. Wainwright, Michael Jordan

arXiv:1609.00978v1stat.MLcs.LGmath.OC

TL;DR

The paper investigates whether population likelihoods of Gaussian mixtures can have bad local maxima, a question relevant to the quality of EM’s solutions. It analyzes these likelihoods and random initialization, showing both arbitrarily poor local maxima and a high probability that EM variants converge to suboptimal critical points. Its first-order EM result further indicates that bad local maxima, rather than strict saddles, account for the method’s poor outcomes.

  • Problem

    Whether population likelihoods for uniformly weighted isotropic Gaussian mixtures have bad local maxima remained open, despite the conjecture that their absence would justify EM for large samples.

    Source: §1 · p. 2

  • Method

    The paper analyzes population likelihood structure and the behavior of EM and first-order EM under random initialization.

    Source: §1 · pp. 3–4

  • Results

    A three-component well-separated spherical mixture has local maxima arbitrarily worse than global maxima, and random initialization leads EM variants to suboptimal critical points with probability at least 1 − e^(−cM).

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The results indicate that careful initialization is needed for local search even in large-sample, extremely well-behaved mixture settings.

    Source: §1 · p. 4

    The proof that first-order EM almost surely avoids strict saddles relies on properties specific to that algorithm; a similar result for EM is conjectured but not established.

    Source: §3.2 · p. 9

Abstract

from arXiv · show

We provide two fundamental results on the population (infinite-sample) likelihood function of Gaussian mixture models with $M \geq 3$ components. Our first main result shows that the population likelihood function has bad local maxima even in the special case of equally-weighted mixtures of well-separated and spherical Gaussians. We prove that the log-likelihood value of these bad local maxima can be arbitrarily worse than that of any global optimum, thereby resolving an open question of Srebro (2007). Our second main result shows that the EM algorithm (or a first-order variant of it) with random initialization will converge to bad critical points with probability at least $1-e^{-\Omega(M)}$. We further establish that a first-order variant of EM will not converge to strict saddle points almost surely, indicating that the poor performance of the first-order method can be attributed to the existence of bad local maxima rather than bad saddle points. Overall, our results highlight the necessity of careful initialization when using the EM algorithm in practice, even when applied in highly favorable settings.

1 Introduction

The paper asks whether population likelihoods for favorable Gaussian mixtures have bad local maxima, and whether random initialization leads EM into them. It answers both questions affirmatively and shows that first-order EM’s poor outcomes are associated with bad local maxima rather than strict saddles.

1 Introduction

  • Uniformly weighted isotropic Gaussian mixtures were conjectured to have no bad population-likelihood maxima, a property that would justify EM for large samples, while EM generally guarantees only convergence to a stationary point.Prior two-component evidence suggested no bad local optima, but the question remained open for larger mixtures.Source: §1 · pp. 2–3
  • A uniform mixture of three well-separated spherical unit-variance Gaussians has bad population-likelihood local maxima whose values can be arbitrarily worse than the global maxima.This resolves Srebro’s open question and rules out global convergence of any local search method from all starting points, even for well-separated mixtures.Source: §1 · p. 3
  • With random initialization, EM and first-order EM converge to suboptimal critical points with probability at least 1 − e^(−cM), for a universal constant c > 0.In the infinite-sample limit, the initialization scheme is equivalent to drawing M initial centers i.i.d. from the mixture; obtaining satisfactory likelihood by repeating it may require exponentially many runs in M.Source: §1 · p. 4
  • With the same random initialization and a suitable stepsize, first-order EM almost surely does not converge to a strict saddle point.The authors infer that bad local optima, rather than strict saddles, are the main source of local-search failure for GMMs.Source: §1 · p. 4
  • The results indicate that careful initialization is needed for local search, even for large-sample, extremely well-behaved mixture models.The paper’s proofs introduce techniques for analyzing population-likelihood structure and bad local optima.Source: §1 · p. 4

2 Background and Preliminaries

The paper studies equally weighted, identity-covariance Gaussian mixtures and their population likelihoods, then analyzes EM, its first-order variant, and random initialization. Its setup connects this idealized model to the question of whether population likelihoods can have bad local optima.

2.1 Gaussian Mixture Models

  • For equally weighted identity-covariance mixtures, the population likelihood is maximized at the true means, up to permutations, yet a one-dimensional mixture of three well-separated Gaussians can have arbitrarily bad local optima.The model estimates component means; the population objective is the infinite-sample limit of the sample likelihood.Source: §2.1 · p. 5

2.2 Expectation-Maximization Algorithm

  • A GMM’s sample log-likelihood is non-concave, so EM alternates between steps that maximize a lower bound rather than maximizing the likelihood directly.In the population setting, the objective takes an expectation over data drawn from the specified mixture.Source: §2.1 · p. 5, §2.2 · p. 6
  • First-order EM replaces exact optimization of the lower bound with a gradient step on that bound using a chosen stepsize.For the model studied, its population updates are described as gradient EM updates.Source: §2.2 · p. 6

2.3 Random Initialization

  • The analyzed random initialization samples each initial center uniformly from the data; in the population setting, this is equivalent to drawing centers i.i.d. from the mixture distribution.This data-adaptive scheme scatters initial centers when true centers are far apart and keeps them close when true centers are concentrated.Source: §2.3 · p. 7

3 Main results

The paper shows that population GMM likelihoods can have arbitrarily poor local maxima even for well-separated, equally weighted spherical mixtures with at least three components. It also establishes that random initialization can lead EM and a first-order variant to suboptimal points, with the first-order method’s failures most likely attributable to bad local maxima rather than strict saddles.

3.1 Structural properties

  • For every M ≥3, a well-separated uniform mixture of unit-variance spherical Gaussians can have a local maximum arbitrarily worse in log-likelihood than the true parameters.This refutes Srebro’s conjecture about the absence of bad local maxima in the population likelihood.Source: §3.1 · p. 7
  • For M=3, the construction places one fitted center between a close pair of true centers and two fitted centers at the third; a neighborhood argument establishes a suboptimal local maximum.The neighborhood excludes global maxima and has lower likelihood on its boundary than at the suboptimal configuration.Source: §3.1 · p. 7

3.2 Algorithmic consequences

  • For the constructed mixture, random-initialized EM has exponentially small success probability, so constant-probability global recovery requires e^Ω(M) runs.The theorem concerns well-separated, uniformly weighted mixtures of M unit-variance spherical Gaussians.Source: §3.2 · p. 8
  • A recursive arrangement of far-separated clusters and mini-clusters makes favorable random initializations exponentially unlikely in M.The construction repeats the clustering structure for Ω(log M) levels.Source: §3.2 · p. 8
  • With a sufficiently restrained step size, first-order EM also retains the problem of converging to suboptimal fixed points; EM and gradient ascent require exponentially many random restarts for meaningful estimates in this setting.The stated step-size restriction is weak and includes the theoretically optimal choice in the two-Gaussian setting studied by Balakrishnan et al. [4].Source: §3.2 · p. 9
  • The results support the view that first-order EM’s frequent suboptimal convergence is more likely due to bad local maxima than strict saddle points.The proof uses properties specific to first-order EM that do not hold for EM; a similar result for EM is conjectured, with a generalized stable manifold theorem suspected to be needed.Source: §3.2 · p. 9

4 Proofs

The proofs establish bad local maxima for Gaussian mixtures and analyze how EM and first-order EM behave around unfavorable configurations, including a Hessian bound for the first-order EM analysis. They also show that first-order EM with a step size in (0, 1) converges to a critical point and, under random initialization, almost surely avoids strict saddle points.

4.1.1 Existence of a local maximum

  • For M = 3, a finite-parameter GMM has a local maximum that is not global: an interior likelihood exceeds the boundary, while the global maxima lie outside the set.The interior-versus-boundary comparison holds for sufficiently large γ.Source: §4.1.1 · p. 11

4.1.2 Log-likelihood at a local maximum

  • As R grows, the likelihood gap between the global maximum and a local maximum can exceed any prescribed C_gap > 0.Continuity in R yields a sufficiently large finite R for each desired gap.Source: §4.1.2 · p. 11

4.1.3 Extension to the case M > 3

  • For M > 3, the proof extends the local-maximum construction to a closed set, using the same argument as for M = 3.The construction works when γ is sufficiently large.Source: §4.1.3 · p. 11

4.2 Proof of Theorem 2

  • Theorem 2’s construction makes good initializations exponentially unlikely, bounding the chance that EM reaches a global maximum by an exponentially small quantity.For the diffuse mixtures considered, the lemma restricts potentially successful initializations to specified center-count configurations, and the recursive bound gives P(F_M | E_M) ≤ e^(-cM).Source: §4.2 · p. 14
  • The construction also traps EM configurations in which one center represents two true centers in an urn, and sufficiently large R makes the likelihood gap arbitrarily large.The proof uses continuity in R to obtain a finite sufficiently large separation.Source: §4.2 · p. 14

4.3 Proof of Theorem 3

  • The first-order EM update is a less aggressive version of the EM update, and this suffices for Lemma 1’s guarantees to continue to hold for first-order EM, completing Theorem 3.First-order EM uses a step size s in (0, 1).Source: §4.3 · p. 15

4.4 Proof of Theorem 4

  • For any scalar s ∈ (0, 1) and any μ, the proof establishes the Hessian bound s∇²L(μ) ≻ −I.Source: §4.4 · p. 16
  • For any step size s in (0, 1), first-order EM strictly increases population likelihood away from critical points and converges to a critical point.The likelihood is upper bounded for mixtures of M spherical Gaussians, so the increasing sequence converges.Source: §4.4 · p. 16
  • The set of initial points leading first-order EM to a strict saddle has zero Lebesgue measure, so absolutely continuous random initialization avoids strict saddles almost surely.The proof applies a stable-manifold result when the update map is a local diffeomorphism everywhere.Source: §4.4 · pp. 16–17
  • The update map is a local diffeomorphism everywhere because its Jacobian, I+s∇²L(µ), is strictly positive definite and therefore invertible.This follows from Lemma 2 for the stated step-size range.Source: §4.4 · pp. 16–17

A Proofs of Technical Lemmas

This section proves Lemma 1 using several technical lemmas.

A Proofs of Technical Lemmas

A.1 Proof of Lemma 1

The proof uses an auxiliary result about the weighted data assigned to centers in a specified interval to establish Lemma 1.

A.1 Proof of Lemma 1

  • Under the stated mixture and center-configuration assumptions, for any current parameter µ_i ∈ [0, 4a], the weighted expectation E_wi(X)X is nonnegative.The true distribution is an M-component GMM; its centers lie in (−∞, −10a) ∪ (a, +∞), with at least one in (a, 3a), and a > log M + 3.Source: §A.1 · p. 20
  • The proof invokes Lemma 4 to show that an EM update moves a center in the specified ball into the required region.The proof reduces the claim to showing that after one EM step the new iterate meets the target condition; the excerpt does not include the completed condition.Source: §A.1 · p. 20
  • The inequalities used to establish the auxiliary result follow by shifting the variable and applying Lemma 4 to each shifted variable.The proof defines Z = X − (c − 2)δ and Y = (c + 2)δ − X for the two inequalities.Source: §A.1 · p. 20

A.2 Proof of Lemma 4

The proof uses the directional effects of distant Gaussian components on current centers to establish an auxiliary result under separated-center assumptions.

A.2 Proof of Lemma 4

  • A Gaussian component with mean at least a > log M + 3 pushes any current center µ_i ≥ 0 to the right, regardless of the other centers.This is the stated intuition for Lemma 5 when the data are generated by a single such Gaussian.Source: §A.2 · p. 20
  • A component with mean −r pulls a nonnegative center toward the negative direction only slightly when another current center lies within r of that component mean.The excerpt introduces this as the claim of Lemma 6.Source: §A.2 · p. 21
  • The proof of Lemma 4 selects the smallest positive true center, which lies in (a, 3a), and combines the two directional bounds.The excerpt states that Lemma 6 bounds the first term and that the remaining terms are nonnegative or sufficiently large; it then concludes the proof.Source: §A.2 · p. 21

A.3 Proof of Lemma 5

The proof computes the first two terms using Lemma 7, then handles two claims under different parameter conditions.

A.3 Proof of Lemma 5

  • Lemma 7 is introduced for arbitrary nonnegative values of µ1 through µM.Source: §A.3 · p. 22
  • The first claim is completed using µ∗ > a > log M + 3 and the positivity of the third term.Source: §A.3 · p. 22
  • For the second claim, under µ∗ ≤ 3a and µi ≤ 4a, an inequality over x ∈ [a, 3a] is justified by integrating over a unit interval around µ∗ inside (a, 3a).Source: §A.3 · p. 22

A.3.1 Proof of Lemma 7

The proof splits Lemma 7 into cases and establishes a comparison between Aij values across positive and nonpositive inputs.

A.3.1 Proof of Lemma 7

  • For µi ∈ [0, 2], the proof states that maxx∈(−∞,0] wi(x) ≤ 1.Source: §A.3.1 · p. 22
  • For any x ∈ [1, 2] and x′ ∈ (−∞, 0], Aij(x) ≤ M Aij(x′).Source: §A.3.1 · p. 23
  • When µj ≤ µi, x′ < x implies Aij(x) ≤ Aij(x′); the proof then separately considers µi < µj.Source: §A.3.1 · p. 23

A.4 Proof of Lemma 6

The excerpt presents a term-by-term proof, treating the first term on a specified interval before combining it with the second term.

A.4 Proof of Lemma 6

  • The first term is considered for x ∈ (−∞, −2r/3].Source: §A.4 · p. 23
  • The proof next treats the second term separately.Source: §A.4 · p. 23
  • The two pieces are then put together to obtain the stated conclusion.Source: §A.4 · p. 23
Loading 1609.00978v1…