Research map / Optimization / Implicit bias and generalization
Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that population gradient EM globally converges at an O(1/sqrt(t)) rate when fitting an over-parameterized n-component Gaussian mixture to a single ground-truth Gaussian, via a likelihood-based (KL loss) analysis, and shows an exponentially long trap region.
Problem
Global convergence of gradient EM for over-parameterized Gaussian mixture models (n>2 components) fitting a single ground-truth Gaussian, where convergence is sublinear and non-monotonic in parameter space.
Approach
Views gradient EM as gradient descent on the KL/MLE loss and proves convergence of the likelihood loss rather than parameter distance, using a Stein-identity gradient lower bound, a local smoothness lemma, and a potential function U to keep parameters bounded.
Key results
- Theorem gives global convergence of gradient EM with rate loss(mu(t)) <= 1/sqrt(gamma t) for n-component GMM fitting a single Gaussian, the first such result for more than 2 components.
- Constructs bad initialization regions where gradient EM is trapped for exp(Theta(U(0))) steps, showing an exponential factor in the rate is unavoidable.
- Experiments with n=2,5,10 components (d=5, eta=0.7) show sublinear convergence of likelihood loss and parameter distance; statistical error scales approximately as n^{-1/4}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an n-component student GMM to learn a single-Gaussian ground truth with population gradient EM | Population gradient EM · Single-Gaussian ground truth, n-component GMM | KL loss convergence rate: O(1/√t) | Helped |
| Over-parameterize the student from one Gaussian to a mixture model | Gaussian learning with gradient EM · Single-Gaussian ground truth | Convergence rate: O(1/√t) vs. exp(−Ω(t)) | Hurt |
| Initialize in the specified bad region with equal weights | Population gradient EM · Bad initialization region, n≥3 | Time trapped in bad region: T≔1/(30η)eᵈ = 1/(30η)exp(Θ(U(0))) | Hurt |
| Use more evenly distributed mixture weights | 3-component GMM trained with gradient EM · Single-Gaussian ground truth | Convergence speed | Helped |
| Increase the dimension for the specified bad initialization | Gradient EM at the bad initialization · Bad initialization point | Gradient norm: exp(−d) | Hurt |
| Increase training sample size | Gradient EM on 5-component GMM with equal weights · Statistical-rate experiment | Parametric error after convergence: n⁻¹/⁴ | Helped |
Surprising findings
- Convergence is sublinear and non-monotonic in parameter space, and bad regions can trap gradient EM for exponentially many steps in U(0).
- More evenly distributed mixing weights lead to faster convergence in experiments.
Limitations
- Analysis restricted to population (infinite-sample) gradient EM with a single Gaussian ground truth.
- Convergence rate is exponentially small in the initialization scale U(0) for arbitrary initialization.
- Does not address multi-component ground truth GMMs.
Experimental setup
Metrics: likelihood loss KL(p_mu* || p_mu) parametric distance gradient norm statistical error vs sample size
Baselines: linear convergence of exact-parameterized EM 2-Gaussian symmetric-mean over-parameterized EM analysis
Builds on: EM algorithm gradient descent analysis Stein's identity
Closest papers by meaning
- Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? (NeurIPS 2026 · similarity 0.93)
- Sublinear Variational Optimization of Gaussian Mixture Models with Millions to Billions of Parameters (NeurIPS 2026 · similarity 0.90)
- Big Learning Expectation Maximization (AAAI 2024 · similarity 0.89)
- Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification (NeurIPS 2026 · similarity 0.88)
- End-to-end Learning of Gaussian Mixture Priors for Diffusion Sampler (ICLR 2025 · similarity 0.87)
- Learning Mixtures of Experts with EM: A Mirror Descent Perspective (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.