CS Paper Radar

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

Yiran Zhang, Mo Zhou, Weihang Xu, Maryam Fazel, Simon S. Du

cs.LG stat.ML ·submitted 2026-10-06 00:29 UTC · v1
theory

Abstract

Learning Gaussian mixture models (GMMs) using the Expectation-Maximization (EM) algorithm and its gradient-based variants is a fundamental problem in machine learning. It is known that randomly initialized (gradient) EM fails to learn multi-component GMMs in the exact-parameterized setting, where the number of components matches that of the ground-truth GMM. Recently, global convergence of gradient EM has been established in the over-parameterized setting, where more components are used, provided that the ground-truth components are well separated. In particular, the minimum separation between ground-truth components is required to scale as $Ω(\sqrt{d})$, where $d$ is the dimension. In this paper, we show that this dimensional dependence is unavoidable in high-dimensional settings. Specifically, we consider a hybrid EM algorithm that uses standard EM updates for the mixing weights and gradient EM updates for the component means. For any $ε> 0$, we prove that when the dimension is sufficiently large, in the worst case a separation of order $Ω(d^{0.5-ε})$ is insufficient to guarantee global convergence of population gradient EM in sub-exponential time under random initialization, even in the over-parameterized regime. Our result establishes an almost optimal worst-case lower bound on the ground-truth separation required for learning Gaussian mixtures via gradient EM in high dimensions.

Comment
51 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Provably Learning Mixtures of Linear Experts

cs.LG ·2026-11-03 ·Adrian Candocia, Aamod Varma, Mark Davenport
similarity 0.68
Abstract

Mixture-of-Experts (MoE) models are widely deployed in modern machine learning. However, few convergence guarantees exist for gradient-based training of MoEs: the objective is nonconvex, and even simple mixtures trap first-order methods in spurious local optima. We analyze a canonical gated mixture featuring linear experts and a gate induced by Gaussian clusters in the input space, and give, to our knowledge, the first global convergence guarantee for jointly training the gate and the experts of such a model by gradient EM on its likelihood. Given a logarithmic overparameterization relative to the true number of experts $m$, gradient EM converges from randomly initialized gates and least-squares-initialized experts to any prescribed accuracy in polynomially many iterations, under a separation condition on the gate centers. Our analysis establishes a gradient-dominance inequality for the coupled dynamics by decoupling the loss into per-cluster subproblems. Empirical results validate the predicted $m\log m$ phase transition and suggest that the least-squares warm start required by our analysis is not needed in practice: randomly initialized experts perform nearly as well. We also find that leaving the mixing weights unconstrained concentrates routing onto the true number of experts, whereas load-balancing penalties spread it, so that the fitted model can be pruned to a fraction of its width without loss of accuracy.

0.14

Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

cs.LG cs.AI ·2026-10-13 ·Behrooz Tahmasebi, Melanie Weber
published similarity 0.61
Abstract · 32 pages, 1 figure. An extended abstract of this paper appeared at the ICML 2026 HiLD Workshop (July 10, 2026)

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{size generalization}: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting $n$ denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error $n^{-Θ(1)}$ and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as $(\log n)^{-Θ(1)}$, yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error $n^{-Θ(1)}$, recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.

0.31

The Multiscale Single-Index Model: An MSE Analysis of Online SGD Dynamics

cs.LG ·2026-11-06 ·Gordon Dai, Joan Bruna
published similarity 0.59
Abstract · 113 pages, 4 figures. NeurIPS 2026

We consider the Multiscale Single-Index Model (MSIM), first introduced by Oymak and Soltanolkotabi (2021), as a stylized model for hierarchical feature learning with scale separation. Each layer extracts a shared single-index feature at one physical scale and passes it to the next, giving a tractable setting in which to study how deep architectures learn local multiscale representations. Under non-degeneracy and delocalization assumptions on the link function and planted features respectively, for the two hidden-layer case ($K=2$), we analyze joint online spherical SGD under MSE loss, which is a canonical regression objective, in discrete time and show that it achieves weak recovery from random initialization in $O(d\log^2 d)$ samples, followed by strong recovery to accuracy $\varepsilon$ in $O(d\log(1/\varepsilon))$ additional samples. The main technical challenge arises from the non-Gaussian learned features observed by the second layer. We address this challenge through a quantitative Gaussian comparison using delocalization, combined with sharp trajectory-level control of the coupled SGD dynamics. This work is a companion to Bruna (2026, arXiv:2607.03347), which studies recovery under a correlation objective for general $K$.

0.30

Diffusion Models for High-Dimensional Clustered Data: Intrinsic-Dimension Adaptivity via Bayesian Classification

cs.LG stat.MLmath.ST ·2026-08-19 ·Yuga Iguchi, Paul Fearnhead
theory similarity 0.59
Abstract

The empirical success of diffusion models in generative modelling has motivated theoretical work, including quantitative error bounds and qualitative analyses that characterise the different phases of denoising. We bring these two areas together by studying the adaptivity of diffusion models to the structured geometry of multimodal high-dimensional data that consists of multiple clusters in $\mathbb{R}^D$, each with its own low-dimensional structure, and inter-cluster separation depending on $D$. We employ $K$-mixture Gaussian distributions as a canonical framework to capture this geometry and establish two theoretical results. First, we interpret denoising as a dynamical Bayesian classifier: the mixture score is a posterior-weighted average of cluster-wise scores, and we show that, with high probability, the posterior class probabilities concentrate on a single cluster once the signal-to-noise ratio reaches the scale $Θ(\log (KD)/D)$. Second, by separately analysing the denoising process in its mixing and cluster-commitment phases, we prove that the KL error bound depends linearly on the maximum intrinsic dimension of a cluster, up to a logarithmic factor, even when $K$ grows polynomially with $D$. This improves on ambient-dimensional bounds and extends existing low-dimensional adaptivity analyses to multimodal distributions with heterogeneous, approximately low-rank covariances.

0.26

An Optimization Framework for Denoising Generation

cs.LG ·2026-11-17 ·Xinyu Zhou, Jiawei Zhang, Stephen J. Wright
similarity 0.59
Abstract

Noise-unconditioned denoising learns a single score, so generation can be viewed as gradient ascent on a fixed log-density landscape. This optimization interpretation leaves two questions: do trajectories approach meaningful data, and do different initializations retain diverse outcomes? We establish both phenomena for empirical and population multi-scale Gaussian-mixture objectives. Under explicit posterior and landscape conditions, ascent converges almost surely within $O(mσ_{\min}^2/τ)$ of an $m$-dimensional reference manifold with reach at least $τ$. We derive a source--sink identity for the same fixed field and use it to prove finite-resolution regional coverage. In an affine construction, we further identify a positive-bandwidth regime where even empirical-score optimization can avoid training-sample memorization while preserving diversity at the training resolution. The same fixed objective naturally supports penalty-guided controllable generation. Experiments support our predicted mechanisms, show improved robustness under large-step guidance, and demonstrate downstream gains consistent with finite-data generative generalization.

0.17

Derivative Gaussian Processes on a Two-Direction Budget

cs.LG stat.ML ·2026-10-07 ·Hyunseok Seung, Matthias Katzfuss
similarity 0.58
Abstract

Gradient observations promise more accurate Gaussian process (GP) surrogates, but the cost of incorporating them has long stood in the way of realizing that promise. We propose a derivative GP with a budget of just two directions per observed gradient. One direction focuses on each gradient's direct contribution to target prediction, while the other aggregates its indirect contributions through correlations with the conditioning function values. Within a Vecchia approximation, where each prediction conditions on $m$ nearby inputs in $d$ dimensions, this construction represents their $md$ gradient coordinates using at most $2m$ directional derivatives, giving $\mathcal{O}(m^3)$ dense factorization cost per prediction target. For general conditioning sets, we bound the posterior approximation error relative to using full gradients and characterize when the error is small or the approximation is exact. In simulations, our method matches the accuracy of a leading exact gradient-reduction method at equal conditioning set size. Because its cost grows much more slowly with that size, it can use conditioning sets well beyond the memory limit of the exact method, reaching lower prediction error with a small fraction of the time and memory. Notably, our method can exploit gradient observations while requiring less computation time or memory than function-only GP baselines.

0.29

New Multiple Descent Phenomena Induced by Heterogeneous Data

cs.LG stat.ML ·2026-10-27 ·Mark-Anthony Moisescu-Pareja, Elvis Dohmatob
similarity 0.58
Abstract

Modern machine learning models are often trained on large datasets assembled from many different sources, whose statistical properties can differ substantially. Understanding how this heterogeneity affects generalization performance is therefore important for explaining how model performance changes as model size increases. In this work, we study this question in linear random-feature models and show that mixtures of datasets with different covariance structures can give rise to a range of multiple-descent phenomena. We derive exact asymptotic expressions for the test error of each data source in the high-dimensional regime, and show how heterogeneity in covariance scale and spectral structure can introduce additional, group-dependent interpolation thresholds as model size increases. These phenomena arise even with noiseless labels and linear activations, showing that neither label noise nor activation nonlinearity is necessary for multiple-descent. Our results therefore provide a different perspective from classical explanations of multiple descent. More broadly, our results have potential implications for algorithmic fairness by showing that model scaling can affect different data groups unevenly, amplifying disparities in their generalization errors. We validate our theoretical results on synthetic Gaussian mixtures and real-world datasets, including MNIST and CIFAR-10.

0.11

Minimax Optimality of the NPMLE for Gaussian Mixtures in Hellinger Distance

cs.IT math.STcs.LG ·2026-10-21 ·Shayan Hundrieser, Tudor Manole
similarity 0.58
Abstract

We analyze the problem of estimating univariate Gaussian mixture densities using the nonparametric maximum likelihood estimator (NPMLE) based on $n$ independent and identically distributed samples. We show that the unconstrained NPMLE achieves the minimax optimal rate $\log(n)/n$ in squared Hellinger distance, when the true mixing measure is sub-Gaussian. In addition, we show that when the true mixing measure has compact support, the NMPLE constrained to a compact interval also achieves the minimax optimal rate, which is slightly faster and of order $\log(n)/(n \log \log n)$. Our proof consists of sharply characterizing the local Hellinger bracketing entropy of the class of finite Gaussian mixtures. One of our key technical innovations is to sharply bound the $L^2$ bracketing entropy of balls of bounded-degree polynomials, which may be of independent interest. As an application, we establish the regret-optimality of $g$-modeling procedures based on the NPMLE in the Gaussian Empirical Bayes problem with bounded priors.

0.30