PaperlayerView exact revision on arXiv

Source-linked AI summary

Polylogarithmic Sparsity of Randomly Reweighted NPMLEs for Gaussian Mixtures

Hansheng Jiang

arXiv:2610.01088v1stat.MEcs.LGmath.STstat.TH

TL;DR

The Gaussian-mixture NPMLE optimizes over an infinite-dimensional set, and its maximizing mixing distribution need not be unique or sparse. This paper randomly reweights the likelihood and obtains a unique exact maximizer with polylogarithmic support and near-parametric Hellinger accuracy.

  • Problem

    The Gaussian-mixture NPMLE optimizes over an infinite-dimensional set, whose maximizing mixing distribution may lack a simple structure or be nonunique.

    Source: §1 · p. 2, §2.1 · p. 5

  • Method

    A vanishingly small random reweighting yields a unique exact maximizer, with the proof using sparsity of extreme optimizers to establish uniqueness.

    Source: §1 · p. 3, §4.2 · p. 13

  • Results

    With high probability, the reweighted NPMLE is unique, has polylogarithmically many atoms, nearly maximizes the ordinary likelihood, and achieves parametric Hellinger accuracy up to logarithmic factors.

    Source: §1 · p. 3, §6 · pp. 16–17

  • Takeaways & Limitations

    The contribution is exact polylogarithmic support for a randomly reweighted likelihood maximizer over a fixed compact parameter set.

    Source: §6 · p. 17

    Different weight draws may select different sparse mixing distributions, and the support bound applies only to exact maximizers.

    Source: §6 · p. 17

Abstract

from arXiv · show

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.

1 Introduction

The ordinary Gaussian-mixture NPMLE can have many atoms, and existing results do not give exact polylogarithmic support bounds in several dimensions. The paper uses a single, increasingly concentrated random reweighting to obtain a unique, exactly sparse estimator with high-probability likelihood and density guarantees.

1 Introduction

  • The ordinary NPMLE has a classical n-atom bound, which does not explain smaller models seen in practice; no polylogarithmic support bound is established for exact ordinary NPMLEs in several dimensions.The cited multidimensional results establish finite support or generic uniqueness, but not that support bound.Source: §1 · p. 2
  • A single increasingly concentrated random-weight draw defines the estimator, rather than repeated draws serving as a bootstrap or approximate posterior distribution.The weights have mean one and variance 1/α_n, with α_n tending to infinity.Source: §1 · pp. 2–3
  • With high probability, the reweighted NPMLE is unique with at most Cb r̄_n atoms, a polylogarithmic bound in fixed dimensions, and ordinary log-likelihood gap at most Cb/log n.In several dimensions, the atom bound is O{(log n/log log n)^d}.Source: §1 · p. 3
  • For positive continuous kernels, low-dimensional variation of fitted vectors bounds the atoms of every extreme weighted-likelihood optimizer by the effective dimension plus a logarithmic term.For Gaussian kernels, analyticity gives the required effective-dimension bound, while a generic linear-independence property supports uniqueness.Source: §1 · pp. 3–4
  • The structural and likelihood bounds also hold for datasets of radius O(√log n) without requiring correct model specification.The density-accuracy result is separately stated under correct specification.Source: §1 · p. 3
  • Under correct specification, the fitted density has a parametric-up-to-logarithms Hellinger bound; the argument also covers approximate numerical maximizers, but its logarithmic factors are not claimed optimal.The bound follows by applying a uniform likelihood-ratio result to mixtures whose log-likelihood is within one of the true mixture's.Source: §1 · pp. 3–4
  • Across three designs and eleven design–sample-size cells, the balanced-concentration estimator has essentially the ordinary NPMLE's Hellinger risk and resolved support size.With concentration α = 1, resolved support falls slightly in some experiments, but ordinary log-likelihood gap and Hellinger risk are larger.Source: §1 · p. 4

2 Model, reweighted NPMLE, and main results

The paper studies Gaussian location-mixture NPMLEs over a fixed compact parameter set and introduces a randomly reweighted estimator. With high probability, this estimator is unique and exactly sparse, while retaining density-estimation accuracy.

2.1 Gaussian location mixtures

  • The model fixes dimension d and a compact parameter set K; allowing K to grow with n would require tracking how the bounds depend on its radius.The unrestricted maximizers can be represented using the data-dependent convex hull, whose radius grows on the order of √log n.Source: §2.1 · p. 5

2.2 The randomly reweighted NPMLE

  • Independent random weights perturb the empirical distribution while leaving the population criterion unchanged; the perturbation vanishes as the concentration αn grows.A single draw defines the estimator, rather than treating repeated draws as a distribution of maximizers as in the Bayesian bootstrap.Source: §2.2 · p. 6

2.3 The joint sparsity and accuracy theorem

  • With high probability, the reweighted NPMLE is unique and has O((log n/log log n)^d) atoms for d ≥ 2 and O(log n) atoms for d = 1.The guarantee holds uniformly over correctly specified mixing distributions in the fixed compact set.Source: §2.3 · p. 7
  • An inverse-polynomially small weight perturbation can still yield a unique sparse estimator with the theorem’s Hellinger conclusion.Corollary 1 takes αn = n^(2L+2) for any L > 0.Source: §2.3 · pp. 7–8
  • Under correct specification, the reweighted estimator retains a fitted-density Hellinger rate that is parametric up to logarithmic factors.The theorem’s Hellinger conclusion requires G*∈P(K).Source: §2.3 · pp. 7–8

3 An effective-dimension bound on the number of atoms

For positive kernels, the paper relates the support size of extreme optimizers to low-dimensional variation in relative fitted vectors. It uses curvature and a change of variables to obtain a bound on exact support size.

3 An effective-dimension bound on the number of atoms

  • For positive continuous kernels, low-dimensional variation of relative fitted vectors bounds the atom count of every extreme optimizer, with a logarithmic term.For Gaussian kernels, the fitted-vector condition yields an effective dimension of order rn.Source: §3 · p. 8, §3.2 · pp. 9–10

3.1 Positive kernel hulls and optimizer fibers

  • The weighted objective depends on a mixing distribution through its fitted vector, and the maximizing distributions with a given weighted fit form an optimizer fiber.The argument first bounds the largest support among the fiber’s extreme points.Source: §3.1 · pp. 8–9

3.2 Effective dimension

  • The effective-dimension theorem bounds support for exact extreme optimizers; for τ-optimal fits it instead controls the log-likelihood gap and log-fit discrepancy.The bound applies simultaneously to τ-optimal fits for the theorem’s stated tolerance range.Source: §3.2 · p. 10

3.3 Curvature and change of variables

  • Curvature links the support of an extreme optimizer to the Hessian of the value function, and a change of variables makes the resulting moment bound control atom count itself.The method bounds the number of atoms rather than small-mass sizes or approximation error.Source: §3.3 · pp. 10–11

4 Gaussian mixtures: effective dimension, uniqueness and accuracy

Gaussian evaluation vectors admit a low-rank approximation, yielding sparse extreme optimizers; generic evaluation independence then turns that sparsity into uniqueness. A uniform Hellinger bound converts the likelihood guarantee into density accuracy, under correct specification and compact support.

4.1 Analytic low-rank approximation

  • With m ≍ log n / log log n, the Gaussian residual-width approximation has rank O(r_n) and error below any prescribed inverse power of n.The construction reduces Gaussian fitted vectors to multivariate exponential functions and truncates their Taylor series.Source: §4.1 · pp. 11–12

4.2 From sparse extreme optimizers to a unique maximizer

  • When every extreme optimizer has at most m atoms and 2m(d + 1) ≤ n, generic evaluation independence makes the optimizer fiber a singleton.The generic independence property holds simultaneously for all distinct atom locations, including locations chosen after observing the data.Source: §4.2 · p. 12
  • Random reweighting supplies the sparsity needed for uniqueness: the extreme optimizers have at most C_b r̄_n atoms, satisfying 2m(d + 1) ≤ n for sufficiently large n.The ordinary extreme-optimizer bound can be n atoms; the reweighted bound is polylogarithmic.Source: §4.1 · p. 12, §4.2 · p. 13

4.3 Hellinger accuracy

  • The Hellinger guarantee applies uniformly to mixtures with log-likelihood at least L_n(G*) − 1, giving the reweighted estimator density accuracy from its likelihood gap.This step uses correct specification and assumes G* is supported in the known compact set K; the authors do not claim optimal logarithmic factors.Source: §4.3 · pp. 13–14
  • For τ_n ≤ c_0 / log n, approximate weighted maximizers retain likelihood, fitted-vector, and Hellinger guarantees, but their atom counts are not bounded by the exact-estimator result.Adding atoms of negligible mass can leave the likelihood nearly unchanged.Source: §4.3 · p. 14

5 Numerical evidence: sparsity and proximity to the ordinary NPMLE

Simulations compare reweighted and ordinary NPMLEs across three designs and eleven design–sample-size cells, and examine how concentration changes fits on a fixed sample. At balanced concentration, risk and resolved support are comparable; nonconcentrated weights degrade fit.

Experimental designs

  • Three correctly specified designs, sample sizes 200–2000, and three weight concentrations are compared using resolved support, squared Hellinger losses and distances, likelihood gaps, and log-fit discrepancies.The designs are one-dimensional three-point and uniform mixtures and a two-dimensional four-point mixture; BB-scale uses α = 1 and serves as a control.Source: §5 · pp. 14–15

Regularization path

  • −0.503: the fitted weight-perturbation slope as concentration increases; slopes for the ordinary likelihood gap, log-fit discrepancy, and squared Hellinger distance are −1.016, −1.012, and −1.016, respectively.The reported path is based on 30 Gamma-weight draws at each concentration for one n = 500 sample; Figure 1 shows medians and 10th–90th percentile bands.Source: §5 · p. 15, Figure 1 · p. 15

Representative fits

  • At balanced concentration, the median squared Hellinger loss is 0.002664 versus 0.002662 for the ordinary NPMLE, and both resolved support sizes are 3.The figure discussion reports that the ordinary, Balanced, and Tiny fitted densities overlap closely, while the BB-scale fit is visibly displaced.Source: §5 · p. 16, Figure 2 · p. 16

Monte Carlo comparison

  • 1.001–1.020: the balanced reweighted-to-ordinary NPMLE Hellinger-risk ratio across all eleven cells; resolved support sizes agree in 90.3% of 920 paired replications.The cell means of the ordinary log-likelihood gap, multiplied by log n, range from 0.253 to 0.532; BB-scale risk ratios range from 1.60 to 2.19.Source: §5 · p. 16

6 Discussion

A vanishingly small random likelihood reweighting yields a unique exact maximizer with polylogarithmic support, a small ordinary-likelihood gap, and a parametric-up-to-logarithms Hellinger rate. The discussion notes that different weight draws can select different mixing distributions and that computed approximate solutions lack the exact support guarantee.

6 Discussion

  • The exact reweighted maximizer is unique and has polylogarithmically many atoms, with ordinary log-likelihood gap O(1 / log n) and a parametric-up-to-logarithms Hellinger rate.The result holds with high probability over a vanishingly small weight perturbation on a fixed compact parameter set.Source: §6 · pp. 16–17
  • Different auxiliary weight draws may select different sparse mixing distributions, although their fitted densities lie in the same shrinking Hellinger neighborhood with high probability.For computed solutions, the paper retains likelihood and Hellinger guarantees but assesses support using resolved support size.Source: §6 · p. 17
  • Extending the result to other mixtures requires low-rank approximation, a uniqueness mechanism, and a Hellinger bound; other smooth-density independent weight laws may also be usable with additional remainder control.The discussion names exponential-family mixtures, heteroscedastic Gaussian mixtures, and mixtures of regressions as candidates.Source: §6 · p. 17

A.1 Proof of Theorem 1

  • The proof combines a high-probability bounded-radius data event with sparse extreme optimizers; generic evaluation independence then makes the optimizer fiber a singleton.The proof also applies a uniform Hellinger bound after establishing the likelihood gap.Source: §A.1 · p. 19

A.2 Proofs of the corollaries

The corollaries extend the structural and accuracy guarantees to very concentrated weights and establish consistency of the mixing distribution. The appendix also gives the Gamma–Dirichlet representation underlying the reweighting.

A.2 Proofs of the corollaries

  • For m = ceil(C_L log n / log log n), with C_L sufficiently large, and q = (b + 2) log n, conditions (13) hold for large n; every extreme optimizer has O_{b,L}(r̄_n) atoms, and uniqueness follows.The ordinary log-likelihood gap is at most C_{b,L}r̄_n/n^(2L+2) = o(1).Source: §A.2 · pp. 19–20
  • Hellinger convergence and compactness imply that every subsequential limit of the estimated mixing distributions equals G*, using the nonvanishing Gaussian Fourier transform.Thus the reweighted mixing distributions converge weakly to G*.Source: §A.2 · p. 20
  • For τ_n ≤ c_0 / log n, every τ_n-optimal weighted fit retains the likelihood and Hellinger conclusions, but the result does not bound its atom count.The likelihood and fitted-vector bounds apply simultaneously to the approximate fits.Source: §A.2 · p. 20

A.3 Dirichlet representation and Gamma concentration

  • Independent Gamma(α_n, α_n) weights induce normalized Dirichlet(α_n, …, α_n) weights independent of their sum; each Gamma coordinate has mean one and variance 1 / α_n.The Gamma concentration lemma bounds the probability of deviations from one.Source: §A.3 · pp. 20–21

B Proof of the effective-dimension theorem

The proof builds an effective-dimension bound by linking optimizer support to curvature of the weighted value function, then controls that curvature under concentrated Gamma weights. For Gaussian kernels, a low-dimensional approximation of fitted vectors yields the stated polylogarithmic support bound and likelihood guarantees.

B.1 Basic convex geometry

  • An extreme optimizer has at most n atoms, with support characterized by linear independence of its atoms’ evaluation vectors.The maximizing fitted vector is unique, and the fitted-vector and log-fit maps are locally Lipschitz.Source: §B.1 · pp. 21–22

B.2 Support directions and radial localization

  • For an extreme optimizer with k atoms, feasible mass changes span k − 1 fitted-vector directions, yielding a curvature lower bound for the value function.The Hessian dominates the projection onto the weighted support-variation space almost everywhere.Source: §B.2 · p. 23
  • The localization argument bounds the weighted fit’s deviation from the ordinary fit using the perturbation visible in the effective subspace and its total size.The proof applies to exact and near-optimal fits within its stated radius conditions.Source: §B.2 · pp. 23–24

B.3 The Gamma change of variables

  • A change of variables for Gamma weights uses an injective map and a Jacobian lower bound to control the probability of the localized event.The determinant bound incorporates a projection whose rank is tied to the extreme optimizer’s support.Source: §B.3 · p. 25

B.4 Proof of the effective-dimension theorem

  • The proof combines concentration of visible and coordinatewise Gamma perturbations with localization to obtain likelihood-gap and log-fit bounds.These bounds hold together on the event used for the support conclusion.Source: §B.4 · p. 26

C.1 Proof of the Gaussian residual-width bound

  • For Gaussian kernels, fitted vectors lie close to a low-dimensional subspace, with the residual-width argument supplying the effective-dimension control.The approximation integrates a coordinatewise error bound over mixing distributions.Source: §C.1 · p. 27

C.2 Proof of the conditional Gaussian corollary

  • The hypotheses of Theorem 2 hold; with failure probability at most 3n^(-b-2), it yields sext(W) ≤ C_b r̄_n, plus likelihood and fitted-vector conclusions.Source: §C.2 · p. 28

C.3 Proof of generic evaluation independence

For almost every dataset, generic independence of Gaussian evaluation vectors converts sparse extreme optimizers into a unique optimizer. A separate finite-net construction approximates Gaussian-mixture densities while controlling Hellinger and log-likelihood errors.

C.3 Proof of generic evaluation independence

  • If every extreme optimizer has at most m atoms and 2m(d + 1) ≤ n, the optimizer is unique.The proof establishes simultaneous evaluation-column independence outside a Borel null set.Source: §C.3 · p. 29

D.1 A finite Gaussian-mixture likelihood net

  • A finite Gaussian-mixture net is built by moment matching and discretizing locations and masses, with log-cardinality O(k_m log n).Moment matching controls approximation errors, and the resulting Hellinger error is at most n^−3 for all large n.Source: §D.1 · pp. 30–31
  • The net construction matches moments through degree 2m using a mixing distribution with at most k_m atoms.The construction then rounds locations and weights to form the finite set.Source: §D.1 · p. 30

D.2 Proof of the uniform Hellinger bound

The proof of the uniform Hellinger bound uses a finite net and likelihood tests to control all fits satisfying the stated likelihood condition.

D.2 Proof of the uniform Hellinger bound

  • For each fit satisfying the likelihood hypothesis, the proof associates a finite-net density with controlled approximation error on the radius event.This transfers the net-point Hellinger control to the full class of such fits.Source: §D.2 · p. 31
  • Likelihood tests rule out net points whose Hellinger distance from the true density is at least the specified threshold, except on an event of probability at most e^−1 n^−b−2.The argument combines this event with the high-probability radius event.Source: §D.2 · p. 31
  • The entropy bound and uniform exceptional-probability control yield the claimed Hellinger rate for all mixing distributions in the stated likelihood class.The bound is uniform over the true mixing distribution.Source: §D.2 · p. 31

E Numerical implementation and replication details

The appendix reports implementation and replication details and includes a Monte Carlo comparison at the largest sample size in each design.

E Numerical implementation and replication details

  • The appendix covers the designs, computation, performance measures, accuracy checks, regularization path, and Monte Carlo study.The passage describes the appendix scope without reporting further numerical outcomes.Source: E Numerical implementation and… · p. 31
  • Table 1 compares the ordinary NPMLE with Balanced, Tiny, and BB-scale reweighted fits using Monte Carlo means and standard errors.It reports resolved support size and ordinary log-likelihood gap.Source: Table 1 · p. 32

E.1 Designs and computation

The study compares ordinary and reweighted NPMLEs across one- and two-dimensional mixture designs, then assesses their numerical computation and performance measures. Numerical checks support the comparisons but do not certify a continuous global optimum or uniqueness.

E.1 Designs and computation

  • The Monte Carlo study pairs ordinary and three reweighted fits on the same data across three designs, with sample sizes up to 2000 in one dimension and 1000 in two dimensions.The one-dimensional designs include a three-point mixture and a uniform mixing distribution; the two-dimensional design places equal mass at four corners. There are 100 replications per one-dimensional design and 40 per two-dimensional design.Source: §E.1 · p. 32
  • The regularization path uses 16 concentrations and 30 independent weight vectors per concentration, for 480 weighted fits.Raw weights are Gamma(α, α), normalized to have sample mean one without changing the maximizers; the path includes the balanced concentration αn = 59.76.Source: §E.1 · p. 32
  • Fully corrective column generation adds approximate maximizers of the weighted optimality residual and reoptimizes all atom masses; fits failing residual thresholds are searched again on denser meshes.The final search includes active support locations, and nearly coincident atoms are merged using tolerances no larger than the support-counting resolution.Source: §E.1 · pp. 32–33
  • Every weighted fit starts from the computed ordinary NPMLE, so when α is very large, differences smaller than optimization accuracy are unresolved.Data and weight seeds are deterministic functions of design, sample size, replication, and concentration, allowing reported numbers to be regenerated.Source: §E.1 · p. 33

E.2 Performance measures and accuracy

  • Squared Hellinger distances are numerically integrated on specified grids, while resolved support counts cluster positive-mass atoms within 0.01 in one dimension or 0.05 in two dimensions.This support count is a numerical resolution convention, not an exact floating-point atom count.Source: §E.2 · p. 33
  • Across 4160 recorded fits, the largest recorded residual is at most 8.03 × 10^-7, but the checks do not certify a continuous global optimum or uniqueness.Denser searches and wider, finer Hellinger grids provide independent numerical checks; six negative ordinary log-likelihood gaps were attributed to optimization error, leaving gaps of that order or smaller numerically unresolved.Source: §E.2 · p. 33

E.3 Additional results

The additional results examine the regularization path and compare Hellinger risk, likelihood gaps, and resolved support for balanced, Tiny, and BB-scale fits. Balanced fits closely track the ordinary NPMLE, while BB-scale fits have higher estimated risk and Tiny-fit differences are below optimization accuracy.

E.3 Additional results

  • On the regularization path, 28 balanced-concentration draws have 3 atoms and 2 have 4; at α = n^3, all 30 draws have 3 atoms.At α = 1, the 90th percentile of resolved support size is 4. At α = n^3, median squared Hellinger distance to the ordinary NPMLE is 1.52 × 10^-11 and median ordinary log-likelihood gap is 1.65 × 10^-8.Source: §E.3 · pp. 33–34
  • Figure 3 plots estimated Hellinger risk, the Monte Carlo mean of squared Hellinger loss, against sample size, with bands of ±1.96 standard errors.The supplied results identify the plotted quantity and uncertainty bands but do not give specific curve values.Source: Figure 3 · p. 34, §E.3 · p. 34
  • Across eleven design–sample-size cells, Balanced-to-ordinary estimated Hellinger risk ratios range from 1.001 to 1.020, averaging 1.013.The resolved support sizes agree in 90.3% of 920 paired replications, and mean support-size differences lie between −0.125 and 0.025 in every cell.Source: §E.3 · p. 34
  • Balanced-fit ordinary log-likelihood gap cell means range from 0.0345 to 0.0964, and multiplying by log n gives 0.253 to 0.532.After the same scaling, log-fit discrepancy ranges from 0.479 to 0.928 across cells.Source: §E.3 · p. 34
  • Tiny-fit estimated Hellinger risk ratios range from 0.999985 to 1.000017, and resolved support agrees with the ordinary NPMLE in 100.0% of replications.Their mean squared Hellinger distance to the ordinary NPMLE ranges from 8.03 × 10^-14 to 1.32 × 10^-9; these differences lie below optimization accuracy and cannot separate the exact reweighted maximizer from the ordinary one.Source: §E.3 · p. 34
  • BB-scale estimated Hellinger risk ratios range from 1.60 to 2.19, with mean ordinary log-likelihood gaps from 2.14 to 7.86.These fits sometimes have slightly smaller resolved support, but at a material statistical cost; at α = 1, weights do not concentrate and the objective does not approach the ordinary one.Source: §E.3 · p. 34
Loading 2610.01088v1…