Solving the Ho--Nguyen Conjecture for Gaussian Mixtures: Applications to Mixtures of Experts

Yuyang Zhang; Qihuang Zhang

cs.LGOct 19, 2026

Solving the Ho--Nguyen Conjecture for Gaussian Mixtures: Applications to Mixtures of Experts

Authors: Yuyang Zhang, Qihuang Zhang

Organizations: McGill University

Abstract

Over-fitted Gaussian mixtures can contain many parameter configurations with nearly the same density, making the order of density cancellation central to their parameter-learning rates. Ho and Nguyen encoded these cancellations in a polynomial system and conjectured its exact order as a function of cluster size. The key to resolving the conjecture is a common positive-variance shift that turns the coefficient equations into Gaussian moment matching. For every cluster size $\Mhn\ge2$ , we prove that the real, nonzero-weight system has order $2\Mhn$ : a sharp sign-change bound forces rigidity at that order, while positive Gauss--Hermite quadrature constructs a non-trivial solution through order $2\Mhn-1$ . Population-density calculations at 110-digit working precision recover the predicted leading term for two to six components; finite multistart searches recover the same observed powers for two to five components, with smaller finite-scale constants for three to five components. For parameter learning, the exact order gives an explicit pointwise maximum-likelihood exponent and an exact local minimax order on specified shrinking neighbourhoods of a fixed known mixing measure. The same coefficient viewpoint separates high-order cancellation from exact parameter symmetries in mixtures of experts. Synchronized replication preserves the conditional density while keeping the corresponding parameter losses positive in two broad standard-softmax classes, showing why statistical rate arguments must account for exact parameter symmetries.

Figures & tables

Figure 1: The Gauss–Hermite path, evaluated with 110-digit working arithmetic for $K=2,\ldots,6$ . Left: TV against the path parameter $t$ ; dashed curves show its theoretical leading term. Middle: local TV slopes against the Euclidean transport distance $W_{1}^{\mathrm{E}}$ on location and variance; the dotted levels are $2K$ . Right: relative deviations from the TV and Hellinger leading terms, shown by circles and squares, respectively, with $O(t^{2})$ reference behavior for both. The zero middle node for odd $K$ contributes a $t^{2}$ term to $W_{1}^{\mathrm{E}}$ and makes the finite-scale transport slope converge more slowly.

$K$	Fixed-weight order $2K$	$\sqrt{\chi^{2}}$ search	Direct Hellinger search
2	4	4.0000	4.0001
3	6	6.0000	6.0000
4	8	8.0000	8.0000
5	10	9.9995	—

Table 1: Observed distance exponents at fixed homogeneous size. Each reported slope uses the four smallest of eight tested sizes and the saved high-precision evaluations of the optimized configurations. The last column is a separate direct-Hellinger search. Its coverage is

K=2,3,4

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

$K$	TV / leading term	$h$ / leading term	Sign changes
2	1.00000106666759	1.00000000000257	4
3	1.00000160714464	1.00000000000201	6
4	1.00000213333623	1.00000000000320	8
5	1.00000265151941	1.00000000000464	10
6	1.00000316484104	1.00000000000633	12

Appendix

Table 2: Recorded leading-term ratios on the constructive path at

t=10^{-3}

. The final column is the numerically located sign-change count. Values are shown at the reported precision.

$K$	$R=2K-1$	$R=2K$	$R=2K+1$
2	$8.38082876\,10^{-35}$	$0.0296423083$	$0.0328742658$
3	$1.09048260\,10^{-33}$	$0.000940991237$	$0.000940991237$
4	$9.27154712\,10^{-33}$	$0.0000576511687$	$5.77030278\,10^{-5}$
5	$8.86527277\,10^{-33}$	$0.00000217377594$	$0.00000217377594$
6	$2.19605855\,10^{-31}$	$9.05174075\,10^{-8}$	$9.05174075\,10^{-8}$

Appendix

Table 3: Smallest coefficient objective found at homogeneous size one. These are sums of squared weighted coefficients.

Size constraint	$K$	$\sqrt{\chi^{2}}$ search	Direct H search
$\\|G\\|_{\mathrm{h}}$	2	4.00002624	4.00006882
	3	6.00001999	6.00002040
	4	8.00002396	7.99999148
	5	9.99949221	—
$W_{1}^{\mathrm{E}}$	2	3.98713528	3.98721777
	3	5.84036305	5.84036830

Appendix

Table 4: Stored fixed-size slopes over the four smallest sizes. Columns give the coefficient-search slope of

\sqrt{\chi^{2}}

and the direct-H search slope after high-precision integration. The

W_{1}^{\mathrm{E}}

rows show the finite-scale effect of changing the size constraint.

Gaussian Mixture Models

Gaussian Mixture Models represent data distributions as weighted combinations of Gaussian components for clustering, density estimation, and multimodal prediction.

See all 63 papers

Oct 1, 2026

Polylogarithmic Sparsity of Randomly Reweighted NPMLEs for Gaussian Mixtures

The nonparametric maximum likelihood estimator (NPMLE) of a Gaussian location mixture maximizes the likelihood over the infinite-dimensional space of mixing distributions. The maximizing mixing distribution can be nonunique, and the classical bound on its number of atoms grows linearly with the sample size

n

. We show that a vanishingly small random perturbation of the likelihood yields exact polylogarithmic sparsity. The resulting randomly reweighted NPMLE maximizes a weighted likelihood whose independent weights, taken to be Gamma in our analysis, concentrate around one as

n

grows. With high probability, it is unique, has

O\{(\log n/\log\log n)^d+\log n\}

atoms in dimension

d

, nearly maximizes the ordinary likelihood, and estimates the mixture density at a Hellinger rate that is parametric up to logarithmic factors. This sparsity holds for the estimator itself, not for an approximation of it, and requires no support penalty. The proof rests on an effective-dimension principle for positive kernel mixtures: low-dimensional variation of the fitted values controls the support of every extreme point of the set of maximizers. Numerical illustrations verify that the reweighted NPMLE has Hellinger risk and support size comparable to those of the ordinary NPMLE.

Hansheng Jiang

University of Toronto

Gaussian Mixture Models Density Estimation

Ask PDF

May 29, 2026

Local linear convergence of gradient methods for overparameterized Gaussian mixtures

We study the problem of learning Gaussian mixture models under overparameterization. Prior work has shown that while overparameterization is essential for avoiding spurious local optima and enables global recovery of the ground-truth model using the gradient-EM (expectation-maximization) algorithm, it can dramatically slow down the local rate of convergence. Under certain assumptions on the mixture weights, we show that a standard divergence measure minimized by statistical learning procedures possesses a manifold of slow growth on which the well-known Polyak stepsize reduces the loss geometrically, and design a gradient-based method that converges to minimizers at a locally linear rate. Additionally, we show that our method converges to nearly optimal solutions -- up to a natural misspecification threshold -- for mixtures with arbitrary weights. At a high level, the method alternates between several "short" gradient descent steps that approach the manifold and "long" Polyak steps that contract the distance to minimizers. Our results suggest that slow convergence is not an intrinsic challenge of overparameterization, but can be overcome by exploiting the favorable structure of the loss landscape.

Jingxing Wang, Vasileios Charisopoulos, Maryam Fazel

Electrical & Computer Engineering, University of Washington, Seattle, WA · National Institute for Theory and Mathematics in Biology, Chicago, IL · Amazon, Inc.

Gradient Descent Gaussian Mixture Models Convergence Analysis

Ask PDF

Apr 19, 2024

Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models

In this paper, we study the problem of learning one-dimensional Gaussian mixture models (GMMs) with a specific focus on estimating both the model order and the mixing distribution from independent and identically distributed (i.i.d.) samples. This paper establishes the optimal sampling complexity for model order estimation in one-dimensional Gaussian mixture models. We prove a fundamental lower bound on the number of samples required to correctly identify the number of components with high probability, showing that this limit depends critically on the separation between component means and the total number of components. We then propose a Fourier-based approach to estimate both the model order and the mixing distribution. Our algorithm utilizes Fourier measurements constructed from the samples, and our analysis demonstrates that its sample complexity matches the established lower bound, thereby confirming its optimality. Numerical experiments further show that our method outperforms conventional techniques in terms of efficiency and accuracy.

Xinyu Liu, Hai Zhang

Department of Mathematics Hong Kong University of Science and Technology Clear Water Bay, Hong Kong SAR, China

Sample Complexity Gaussian Mixture Models

Ask PDF

Abstract

Gaussian Mixture Models

Explore similar work

Polylogarithmic Sparsity of Randomly Reweighted NPMLEs for Gaussian Mixtures

Local linear convergence of gradient methods for overparameterized Gaussian mixtures

Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models