Research map / Learning theory and algorithms / Matrix and tensor methods

Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Nonconvex low-rank and sparse optimization

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.

Shows that for hybrid population EM (EM weights, gradient EM means) a separation of d^{0.5-eps} from random initialization fails to reach small KL loss in sub-exponential time in high dimension, and that 10*sqrt(d) separation suffices for exponentially small loss, so the sqrt(d) separation is near-optimal.

Problem

Whether the Omega(sqrt(d)) minimum component separation required by prior global convergence results for over-parameterized gradient EM on Gaussian mixtures can be reduced, i.e., whether it is necessary in high dimensions.

Approach

Constructs a worst-case instance with equilateral true means at separation d^{0.5-eps} and proves via a stage-wise dynamical analysis that random-initialized hybrid population gradient EM collapses onto a single component and keeps KL loss bounded below for exponentially long time; complements with a sqrt(d)-separation positive result.

Key results

• For separation d^{0.5-eps} and n >= 3 log m / pi_min, with prob. at least 1-1/m the hybrid population gradient EM loss stays >= (1-pi_1*)^2/3 for all t <= exp(d/100)/eta.
• With separation at least 10 sqrt(d) (and d large), the same hybrid update reaches loss <= exp(-d/200) within polynomial time window 10d/(eta pi_min) <= t <= exp(d/50)/eta.
• Simulations with d=10 succeed in fitting both components while d=500 underfits with one component taking all weight (two-component mixture, n=10).

Surprising findings

• Even with over-parameterization (n > m), random-initialized hybrid gradient EM can collapse onto a single component when separation is only d^{0.5-eps}.

Limitations

• Result is an exponent-level lower bound for worst-case instances; does not rule out thresholds like sqrt(d)/log d.
• Applies only when n is small relative to d (n <= c rho d^{eps/15}); does not cover n comparable to or larger than d.
• Analysis is for population (infinite-sample) hybrid EM updates with EM weights, not classical EM or finite-sample version.

Experimental setup

Metrics: KL divergence loss mixing weight dynamics

Builds on: gradient EM global convergence over-parameterized GMM population EM analysis

Closest papers by meaning

• Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models (NeurIPS 2024 · similarity 0.93)
• Convergence of Gradient EM on Multi-component Mixture of Gaussians (NeurIPS 2017 · similarity 0.92)
• Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions (NeurIPS 2021 · similarity 0.88)
• Sublinear Variational Optimization of Gaussian Mixture Models with Millions to Billions of Parameters (NeurIPS 2026 · similarity 0.87)
• Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification (NeurIPS 2026 · similarity 0.86)
• On Learning Parallel Pancakes with Mostly Uniform Weights (ICML 2025 · similarity 0.86)