PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical guarantees for the EM algorithm: From population to sample-based analysis

Sivaraman Balakrishnan, Martin J. Wainwright, Bin Yu

arXiv:1408.2156v1math.STcs.LGstat.ML

TL;DR

The paper asks how to provide rigorous guarantees for EM when incomplete-data likelihoods are difficult and the likelihood may be multi-modal. It develops population and finite-sample analyses for EM and gradient EM, viewing their updates as perturbed ascent procedures. The resulting theory gives contraction and finite-sample convergence guarantees under suitable initialization, with applications to three incomplete-data models.

  • Problem

    EM is widely used for incomplete-data problems, but in multi-modal likelihoods it is generally guaranteed only to reach a local optimum, leaving its statistical behavior insufficiently understood.

  • Method

    The paper analyzes population and sample-based EM and gradient EM by viewing their updates as perturbed likelihood-ascent or gradient-ascent procedures.

  • Results

    The theory establishes population contractivity and finite-sample convergence near the population MLE, with concrete results for Gaussian mixtures, mixtures of regressions, and missing-covariate regression.

  • Takeaways & Limitations

    With suitable initialization, EM and gradient EM can reach statistically useful estimates in the three model classes studied, and the techniques may extend to other non-convex algorithms.

  • Takeaways & Limitations

    The concrete analyses assume correct model specification and i.i.d. samples; understanding EM under misspecification remains an open problem.

Abstract

from arXiv · show

We develop a general framework for proving rigorous guarantees on the performance of the EM algorithm and a variant known as gradient EM. Our analysis is divided into two parts: a treatment of these algorithms at the population level (in the limit of infinite data), followed by results that apply to updates based on a finite set of samples. First, we characterize the domain of attraction of any global maximizer of the population likelihood. This characterization is based on a novel view of the EM updates as a perturbed form of likelihood ascent, or in parallel, of the gradient EM updates as a perturbed form of standard gradient ascent. Leveraging this characterization, we then provide non-asymptotic guarantees on the EM and gradient EM algorithms when applied to a finite set of samples. We develop consequences of our general theory for three canonical examples of incomplete-data problems: mixture of Gaussians, mixture of regressions, and linear regression with covariates missing completely at random. In each case, our theory guarantees that with a suitable initialization, a relatively small number of EM (or gradient EM) steps will yield (with high probability) an estimate that is within statistical error of the MLE. We provide simulations to confirm this theoretically predicted behavior.

1 Introduction

The paper addresses the gap between the statistical guarantees of maximum likelihood estimation and EM's usual guarantee of convergence only to a local optimum. It develops tools for understanding when suitable initialization leads EM toward statistically useful solutions.

  • Incomplete-data likelihood maximization is computationally difficult, motivating widespread use of EM.The paper focuses on missing values, corruptions, and latent variables.
  • Although the MLE may have good statistical properties, EM is generally guaranteed only to return a local optimum.This gap is especially important when the likelihood is multi-modal.
  • With suitable initialization, EM often converges to a statistically useful estimate, but the behavior of the reached fixed points is not quantitatively understood.The paper highlights two-stage procedures that initialize EM before refinement.
  • Prior alternating-minimization work shows local effectiveness despite non-convexity in certain special cases, including a degenerate noiseless mixtures-of-regressions setting.The paper extends analysis to noisy mixtures of regressions through its general EM treatment.
  • The paper analyzes standard EM and gradient EM at both population and finite-sample levels.Gradient EM uses a single gradient step per iteration instead of an exact maximization.
  • The paper applies its framework to Gaussian mixtures, mixtures of regressions, and regression with missing covariates.

2 Background and model examples

The paper introduces EM and gradient EM for latent-variable models, distinguishes population from sample-based updates, and reviews Gaussian-mixture and mixture-of-regressions examples. It frames EM as successive maximization of a likelihood lower bound and notes identifiability issues in mixture models.

  • Statistical setup: The estimation target is a population-likelihood maximizer, which need not be unique; mixture-model permutation non-identifiability is addressed through initialization conditions.The observed-data maximum-likelihood estimate maximizes the likelihood over Ω.
  • EM framework: EM handles incomplete data by alternating expectation and maximization steps that successively optimize a lower bound on the observed-data log likelihood.The E-step computes Q(·|θt), while the M-step maximizes this lower bound.
  • EM variants: Generalized EM relaxes exact M-step optimization, requiring only an update θt+1 ∈Ω that satisfies the specified ascent requirement.Different choices of θt+1 define a family of generalized EM algorithms.
  • EM variants: Gradient EM uses a step-size-controlled gradient of Q in its first argument and can be written as the iteration θt+1 = G(θt).For suitable step sizes, the updates satisfy the ascent condition; constrained versions add Euclidean projection.
  • Population versus sample updates: Population updates use expectations corresponding to effectively infinite data, whereas sample updates replace these expectations with empirical averages from n i.i.d. observations.The sample operators provide analogs of the population EM and gradient EM operators.
  • Model examples: The reviewed examples include isotropic balanced Gaussian mixtures and symmetric mixtures of regressions with latent component labels and closed-form sample EM operators.The mixture-of-regressions model uses regression vectors θ∗ and −θ∗ with Gaussian design and observation noise.
  • Model examples: For mixture of regressions, hidden labels select between two opposite regression vectors, and both sample and population EM operators are expressed using a model-specific weight function.The model is connected in the paper to phase-retrieval models over R^d.

3 General convergence results

The paper establishes general convergence conditions for population and sample-based EM and gradient EM, using contractive oracle updates and deviation bounds. Under local regularity and suitable initialization, iterates converge geometrically to the MLE or an ε-ball around it.

  • Overview: The analysis covers population operators and sample-based updates for both standard EM and gradient EM.The sample-based operators approximate population updates using subsets of samples, with probabilistic deviation bounds.
  • Overview: Population convergence follows by viewing EM and gradient EM as perturbed versions of oracle likelihood-ascent and gradient-ascent operators.Theorems 1 and 3 establish contractivity on a ball around a population-likelihood maximizer.
  • 3.1.1 Guarantees for population-level EM: The FOS condition, together with strong concavity of q, makes the population EM operator contractive on a neighborhood of θ∗.Theorem 1 assumes 0 ≤ γ < λ and yields linear convergence for initializations inside B2(r; θ∗).
  • 3.1.2 Guarantees for sample-based EM: Sample-based EM satisfies a geometric-plus-statistical-error bound, converging toward a ball whose radius is determined by uniform empirical deviations.The bound combines a decreasing term κ^t∥θ0 − θ∗∥2 with a tolerance proportional to εunif_M(n, δ).
  • 3.2 Guarantees for gradient EM: Gradient EM has analogous population and sample-based guarantees under strong concavity, smoothness, and gradient stability conditions.Theorems 3 and 4 give contractivity and ε-ball convergence, while the sample-based bounds match the EM form after replacing deviation terms.
  • 3.2.3 Stochastic version of gradient EM: The stochastic gradient EM analysis uses decreasing step sizes and provides a separate bound for its iterates.Theorem 5 specifies updates with step size α_t := 3/(2ξ(t+2)).

4 Consequences for specific models

The paper applies its general EM theory to Gaussian mixtures, mixtures of regressions, and regression with missing covariates. Across these models, suitable conditions yield local contractivity and finite-sample error guarantees, while simulations examine convergence rates and initialization effects.

  • Gaussian mixture models: For Gaussian mixtures, sufficiently large SNR gives a population basin of attraction whose radius is a constant fraction of the signal strength.The population convergence rate is geometric, with a contraction factor that decreases exponentially as SNR increases.
  • Gaussian mixture models: Larger SNR produces faster Gaussian-mixture convergence, matching the predicted contraction behavior.The simulations plot log optimization error across 10 trials for each SNR.
  • Mixtures of regressions: For mixtures of regressions, the population EM and gradient EM operators are locally contractive under a sufficiently large SNR condition.The contraction coefficient decreases with SNR, although its functional form is less explicit than for Gaussian mixtures.
  • Linear regression with missing covariates: For missing-covariate regression, the gradient EM operator is contractive only under an upper bound on signal-to-noise ratio, and increasing signal strength can reduce the convergence radius.The stated condition is supported by minimax lower bounds because missing information increases with signal magnitude.
  • Mixtures of regressions: Mixture-of-regressions guarantees include near-optimal finite-sample error for sample-splitting EM and an O(1/t) statistical-error rate for stochastic gradient EM.The sample-splitting result incurs a logarithmic sample-complexity penalty, while stochastic gradient EM uses one sample per iteration.

5 Discussion

The paper presents general techniques for analyzing EM and gradient EM at population and finite-sample levels, while identifying extensions and initialization requirements.

  • The framework may help analyze convergence of other algorithms for potentially non-convex problems.
  • The treated models assume correct specification and i.i.d. samples, leaving robustness under model misspecification as an open problem.
  • Suitable initialization is required, and pilot estimators such as PCA or plug-in methods can provide it in the three treated model classes.

A Proofs for stochastic gradient EM

The proof establishes contraction for population gradient EM by comparing it with classical gradient ascent, then controls projected stochastic updates through conditional expectations and contraction inequalities.

  • Classical gradient ascent is contractive under λ-concavity and µ-smoothness for step sizes 0 < α ≤ 2/(λ+µ).
  • The population gradient EM operator is contractive with parameter κ(α) = 1 − αξ for the same step-size range.
  • The stochastic proof writes each update as a projected pre-projection vector and tracks differences from the target parameter.
  • Conditional expectations and the contractivity of the population operator combine to establish the finite-sample claim.

B Proofs for Gaussian mixture models

The Gaussian-mixture proofs first establish population contractivity and then derive bounds for sample-based EM updates.

  • The analysis separates population contractivity of the EM operator from bounds for sample-based EM updates.

B.1 Proof of Corollary 1

The Gaussian-mixture proof verifies the regularity conditions needed for population EM contraction and controls empirical deviations using symmetry, rotations, concentration, and discretization.

  • The proof applies the general theorem by verifying λ-concavity and the FOS(γ) condition on a ball around the target parameter.
  • The objective q is strongly concave on R^d with λ = 1.
  • Under the corollary conditions, γ ≤ exp(−c2η^2), yielding contraction when γ < 1.
  • The proof exploits symmetry of the model and rotates coordinates so the relevant mean aligns with the first basis vector before bounding operator norms.
  • Uniform empirical-process control uses sphere coverings, symmetrization, contraction for Rademacher processes, and Chernoff bounds when n ≥ c1d log(1/δ).

B.3 Guarantees for EM with sample-splitting

This section establishes sample-splitting EM guarantees for Gaussian mixtures under an SNR condition and a suitable initialization. With a sufficiently large sample split across a prescribed number of iterations, the iterates satisfy a high-probability bound, with improved dependence on signal and noise relative to an earlier result at a logarithmic cost.

  • Guarantee: Under the SNR(η) condition, initialization within ∥θ∗∥2 of θ∗ places the algorithm in the analyzed region.The stated initialization condition is ∥θ0 − θ∗∥2 ≤ ∥θ∗∥2.
  • Guarantee: n ≥16T log(6T/δ) samples suffice for the sample-splitting EM guarantee to hold with probability at least 1 −δ.The sample size depends on the prescribed number T of iterations and confidence parameter δ.
  • Comparison: Sample-splitting EM is more sensitive to the iteration count because that count determines the batch size and must be chosen in advance.The comparison concerns the earlier Corollary 2 result.
  • Comparison: With an optimally chosen iteration count, the result improves dependence on ∥θ∗∥2 and σ while incurring a logarithmic factor in n.This is the stated trade-off relative to Corollary 2.
  • Proof strategy: The proof bounds the finite-sample error εM(n, δ) by separately controlling update terms through concentration inequalities.The argument uses Hoeffding and sub-exponential or sub-Gaussian bounds before combining the controls for T1 and T2.

C Proofs for mixtures of regressions

The mixture-of-regressions proofs establish population-level EM properties by analyzing the objective, its curvature, and the first-order stability condition. Gaussian moment identities and the model representation supply the technical ingredients for contraction.

  • Proof scope: The appendix proves the population EM result first, followed by sample-splitting EM and stochastic gradient EM results for mixture regressions.These correspond to Corollaries 3, 4, and 5.
  • Population analysis: The population objective is strongly concave with parameter λ = 1 because E[XXT] = I.The curvature parameter is the smallest eigenvalue of E[XXT].
  • Population analysis: The proof verifies the first-order stability condition by comparing responsibility differences wθ(X, Y ) − wθ∗(X, Y ).The difference function and parameter vectors are introduced explicitly for this purpose.
  • Model representation: The regression response is represented as Y d= (2Z −1)⟨X, θ∗⟩+ v with Z ∼Ber(1/2), enabling the subsequent contraction analysis.Here Z is a Bernoulli variable and v is the noise term in the model representation.
  • Population analysis: The smoothness parameter is μ = 1 because the Hessian has largest eigenvalue 1 under E[XXT] = I.The proof then checks the gradient-stability condition using the preceding lemma.
  • Technical lemma: Gaussian rotational invariance yields the needed moment identities for fixed vectors u and v.The proof rotates u to a coordinate direction and reduces the calculation to standard Gaussian coordinates.

C.1.1 Proof of inequality (84a)

The proof of inequality (84a) controls the responsibility-difference terms along the interpolation θu = θ∗ + u∆. It combines separate cases, event decompositions, conditional covariance bounds, and concentration estimates to obtain the desired contraction bound.

  • Case split: The proof treats separately the regimes ∥∆∥2 ≤1 and ∥∆∥2 > 1.The second regime uses several probability events and a threshold τ.
  • Conclusion: Choosing cτ and the SNR constant η sufficiently large yields the claimed inequality (84a).The proof reaches this conclusion after combining the five event contributions and the lower bound on ∥θu∥2.
  • Small-error case: For ∥∆∥2 ≤1, Cauchy–Schwarz and Gaussian moment bounds control B1 and B2, yielding the target bounds on both terms.The resulting inequalities combine to complete (84a) in the small-error case.
  • Conditional covariance: Lemma 8 bounds conditional covariance operators by 2 for the relevant events.This bound is repeatedly used to control conditional second moments.
  • Large-error case: For ∥∆∥2 > 1, the analysis decomposes the target quantity over five events and bounds each contribution separately.The proof introduces Ψ(E) and uses successive conditioning to organize the decomposition.

C.1.2 Proof of inequality (84b)

The proof of inequality (84b) uses Taylor expansion and event-based concentration to control the remaining stability term. It combines Gaussian covariance, tail, and empirical-process bounds with the contraction of the population operator.

  • Proof setup: The proof again separates the cases ∥∆∥2 ≤1 and ∥∆∥2 ≥1 before applying Taylor expansion to the responsibility difference.The expansion reduces the task to bounding terms involving θu and ∆.
  • Event decomposition: Event decompositions and successive conditioning reduce the analysis to separate bounds on Ψ(E) for events E3, E4, and E5.The proof controls each component individually before recombining them.
  • Event bounds: Conditional event bounds control the terms involving E5 using the threshold relation |⟨X, θu⟩| ≥τ.The resulting estimates use Cauchy–Schwarz and the event-specific moment bounds.
  • Gaussian tools: Lemma 9 supplies Gaussian conditional covariance control for sign-change events involving ⟨X, θ∗⟩ and ⟨X, θu⟩.The proof applies the lemma to relate event probabilities and conditional covariance operators.
  • Finite-sample control: For the empirical finite-sample terms, random matrix bounds control the sample covariance while symmetrization and contraction control the vector deviation.A sphere-cover argument extends fixed-direction bounds to the full norm.
  • Conclusion: The population operator is a contraction, and combining the controls for T1 and T2 yields the final bound.The proof substitutes the two component bounds into the decomposition and concludes the claim.

D Proofs for missing covariates

The proof verifies the population-level conditions needed for missing-covariate regression by analyzing the quadratic function q and the GS condition. Under the corollary’s assumptions, q has unit smoothness and strong concavity parameters, and the contraction coefficient satisfies γ < 1.

  • Population-level conditions: q is quadratic, and its Hessian is independent of the missingness pattern after averaging over (Xobs, Y).The expectation is taken over missingness patterns and the random observed covariates and response.
  • Population-level conditions: The quadratic function q satisfies smoothness and strong concavity with µ = λ = 1.This follows from q having an identity Hessian.
  • Condition GS: The GS condition requires a γ ∈ [0, 1) such that ∥E[V]∥2 ≤ γ∥θ − θ∗∥2, with V defined from the model moments.The proof computes E[V] for fixed missingness patterns and bounds the resulting terms.
  • Condition GS: The proof bounds the missing-coordinate and moment terms independently of the missingness pattern, then averages over independent coordinate missingness with probability ρ.It defines η := (1 − ρ)δ + ρ < 1 and uses norm assumptions on θ∗ and θ − θ∗ to control γ.
  • Condition GS: Under the stated conditions of the corollary, γ < 1, completing the population-level proof.This establishes the required GS contraction condition.

D.2 Proof of Corollary 7

The proof establishes finite-sample control for missing-covariate EM updates by decomposing the deviation into two terms and applying sub-Gaussian, sub-exponential, and covering arguments. These bounds imply Corollaries 7 and 8 through Theorems 2 and 5.

  • Deviation bounds: The sample deviation ∥G(θ) − Gn(θ)∥2 is decomposed into two terms, T1 and T2, uniformly over θ in a neighborhood of θ∗.The neighborhood is B2(r; θ∗) = {θ ∈ Rd | ∥θ − θ∗∥2 ≤ ξ2σ}.
  • Controlling T1: The proof controls T1 using empirical covariance concentration and sub-exponential quadratic-form tails.For fixed unit vectors, the relevant covariance fluctuation is shown to be zero-mean and sub-exponential.
  • Controlling T1: The variables B1 through B4 are shown to be sub-Gaussian with bounded parameters, enabling concentration for the first deviation component.The bounds use independence and the constraint ∥θ − θ∗∥2 ≤ ξ2σ.
  • Controlling T2: The proof controls T2 by a variational representation, a 1/2-cover of the sphere with M ≤ 2^d, and sub-exponential product-tail bounds.Each covered term is a product of the sub-Gaussian response y and a sub-Gaussian projection involving µθ.
  • Conclusion: Combining the T1 and T2 bounds yields a high-probability bound on εG(n, δ), and Corollary 7 follows from Theorem 2.The displayed result is stated with probability at least 1 − δ.
Loading 1408.2156v1…