PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial Learning of Distribution Families

Mikhail Belkin, Kaushik Sinha

arXiv:1004.4864v1cs.LGcs.DS

TL;DR

The paper addresses the open problem of polynomially learning general high-dimensional Gaussian mixtures with an arbitrary fixed number of components. It develops polynomial-family learning using moments and real algebraic geometry, then applies deterministic dimensionality reduction to Gaussian mixtures. The resulting algorithms learn identifiable mixtures without separation assumptions, including cases with equal component means and different covariance matrices.

  • Problem

    The general question of polynomially learning Gaussian-mixture parameters without component-separation assumptions remained open after prior work handled only restricted cases.

  • Method

    The paper learns low-dimensional polynomial families from polynomial parameter moments using real algebraic geometry, then reduces high-dimensional Gaussian-mixture learning to polynomially many low-dimensional projections.

  • Results

    The results resolve polynomial learning for identifiable high-dimensional Gaussian mixtures with an arbitrary fixed number of components and no separation assumptions.

  • Takeaways & Limitations

    The framework applies beyond Gaussian mixtures to nearly all common polynomial families, their mixtures, tensor products, and some other polynomially reducible families.

  • Takeaways & Limitations

    The parameter-family analysis assumes a compact semi-algebraic parameter set, such as bounded Gaussian-mixture means and covariance matrices.

Abstract

from arXiv · show

The question of polynomial learnability of probability distributions, particularly Gaussian mixture distributions, has recently received significant attention in theoretical computer science and machine learning. However, despite major progress, the general question of polynomial learnability of Gaussian mixture distributions still remained open. The current work resolves the question of polynomial learnability for Gaussian mixtures in high dimension with an arbitrary fixed number of components. The result on learning Gaussian mixtures relies on an analysis of distributions belonging to what we call "polynomial families" in low dimension. These families are characterized by their moments being polynomial in parameters and include almost all common probability distributions as well as their mixtures and products. Using tools from real algebraic geometry, we show that parameters of any distribution belonging to such a family can be learned in polynomial time and using a polynomial number of sample points. The result on learning polynomial families is quite general and is of independent interest. To estimate parameters of a Gaussian mixture distribution in high dimensions, we provide a deterministic algorithm for dimensionality reduction. This allows us to reduce learning a high-dimensional mixture to a polynomial number of parameter estimations in low dimension. Combining this reduction with the results on polynomial families yields our result on learning arbitrary Gaussian mixtures in high dimensions.

1 Introduction

The paper resolves polynomial learnability for high-dimensional Gaussian mixtures with an arbitrary fixed number of components, without separation assumptions, by combining polynomial-family learning with deterministic dimensionality reduction. Its approach uses real algebraic geometry and low-dimensional projections to estimate mixture parameters.

  • Earlier Gaussian-mixture learning results assumed minimum component separation that grew with dimension or the number of components, leaving the unrestricted parameter-learning problem open.
  • The paper proves a polynomial-time algorithm for estimating parameters of general high-dimensional Gaussian mixtures with an arbitrary fixed number of components and no additional assumptions.
  • Polynomial families are distribution families whose moments are polynomial functions of their parameters, including nearly all common distributions, mixtures, and tensor products.
  • Parameters in polynomial families can be learned using finite identifying moments, algebraic equations and inequalities, and quantifier elimination for semi-algebraic sets.
  • Gaussian mixtures are learned in high dimensions by recovering parameters from a polynomial number of low-dimensional projections, with projection dimension 2k^2 + 2 for k components.
  • The resulting Gaussian-mixture guarantees apply without separation assumptions whenever the mixture is identifiable, including mixtures with equal means but different covariance matrices and nonzero weights.

2 Learning Polynomial Families

Polynomial families have moments polynomial in their parameters, enabling finite-moment characterization and polynomial-time parameter learning even when parameters are not uniquely identifiable.

  • Polynomial families: Polynomial families are distribution families whose moments are polynomial functions of their parameters and whose distributions are uniquely determined by their moments.The class includes nearly all common distributions, along with mixtures, products, and linear transformations of polynomial families.
  • Parameter identifiability: The framework accounts for non-unique parameterizations by defining neighborhoods that include parameters corresponding to identical distributions.For Gaussian mixtures, non-uniqueness can arise from component permutations, zero mixing weights, or coincident component mean/covariance pairs.
  • Learning algorithm: The learning proof combines lower and upper bounds on moment differences with grid search over a compact semi-algebraic parameter set.Quantifier elimination for semi-algebraic sets supplies a polynomial algorithm for the resulting algebraic parameter-estimation problem.
  • Finite moments: A finite set of moments suffices to determine a polynomial-family distribution, and, for identifiable families, to uniquely identify its parameters.Theorem 2.3 establishes an integer N such that equality of the first N moments is equivalent to equality of the distributions.
  • Learning guarantee: Theorem 2.8 gives a polynomial-time algorithm that uses P(1/δ, B) samples and outputs an estimate in N(θ, ϵ) with probability at least 1 −δ.The guarantee applies to parameters in a radius-B ball and allows the target to be an equivalence-aware neighborhood rather than a unique parameter value.
  • Learning guarantee: For identifiable parameters, the estimate is within min(ϵ, R(θ)); for finite non-identifiable equivalence classes, it is close to one equivalent parameter within the corresponding identifiability radius.The radius of identifiability measures the largest locally identifiable neighborhood and depends on the chosen parameter family.

3 Gaussian Distributions and Polynomially Reducible High Dimensional Families

The section develops polynomial-time learning for high-dimensional Gaussian mixtures by reducing parameter estimation to polynomially many fixed-dimensional projections. It also characterizes identifiability and extends the framework beyond fixed-component Gaussian mixtures.

  • Polynomial reducibility: High-dimensional Gaussian-mixture parameters can be estimated from poly(n) projections onto linear subspaces of dimension independent of n.The paper calls this property polynomial reducibility and uses it to overcome the dimension-dependent parameter count.
  • Gaussian-mixture learning: The resulting algorithm estimates parameters of an identifiable Gaussian mixture in polynomial time using polynomially many samples, without requiring component separation.The guarantee is expressed relative to the radius of identifiability and allows permutation of mixture components.
  • Extensions: The framework also applies to products of fixed-dimensional polynomial-family distributions, including products of Gaussian mixtures with exponentially many components.A product of n d-dimensional mixtures with k components each yields a nd-dimensional mixture with k^n components.
  • Identifiability: The radius of identifiability is unchanged by permuting component triples and obeys a triangle-type inequality.These properties support parameter comparison when mixture components are unlabeled.
  • Polynomial reducibility: A 2k^2-dimensional coordinate plane preserves the mixture’s radius of identifiability up to the stated bound.This low-dimensional subspace supplies the starting point for estimating parameters from projections.

4 Conclusion and Discussion

The paper resolves polynomial learnability for identifiable Gaussian mixtures without separation assumptions and connects algebraic geometry with the method of moments. It also identifies broader applications and future implementation work.

  • Main conclusion: The results resolve polynomial learning of Gaussian mixtures without separation assumptions, provided the mixture is identifiable.This includes mixtures whose components share the same mean but have different covariance matrices and non-zero mixing coefficients.
  • Broader significance: The proof introduces real-algebraic-geometry techniques to the classical method of moments and yields results for broader low- and high-dimensional distribution families.The paper specifically notes applications to products of distributions from fixed low-dimensional polynomial families.
  • Future work: Future work includes investigating additional learning applications and turning the framework into implementable, potentially practical algorithms.The proposed route uses computational algebraic geometry.

A Some Polynomial Families of Distributions

Polynomial families are distribution families whose moments are polynomial in their parameters. The appendix illustrates this property for common distributions and notes that reparameterization can make moments polynomial.

  • Definition: Polynomial families are characterized by moments that are polynomial in the distribution parameters.The appendix lists moment expressions or recurrence relations demonstrating this property.
  • Scope: Most commonly used distributions in the appendix form polynomial families, while Table 3 lists two families that do not.The appendix includes explicit expressions for the first three moments for many listed families.
  • Reparameterization: For the binomial example, replacing p with m = p/(1−p) makes the moments polynomial in r and m.The reparameterization changes the form used to express the moments.

B Separation Preserving Coordinate Planes

The paper constructs low-dimensional coordinate planes that preserve pairwise separation among Gaussian mixture means and covariance matrices. These planes use at most k^2 coordinates for either means or covariances, and a 2k^2-coordinate plane can preserve both.

  • Mean separation: A k^2-coordinate plane can preserve every pairwise separation among projected component means.The preserved separation is measured by the projected Euclidean distance relative to the original l1 distance.
  • Combined plane: Projecting onto the span of the mean-preserving and covariance-preserving planes yields a 2k^2-coordinate plane preserving both types of separation.The two planes are combined by taking their span.
  • Covariance separation: A k^2-coordinate plane can likewise preserve every pairwise separation among projected covariance matrices.The construction selects coordinate pairs corresponding to differing diagonal or off-diagonal covariance entries.

C Proof of Theorem 3.1, Theorem 3.2 and Theorem 3.7

The proof learns high-dimensional Gaussian mixtures by selecting a low-dimensional coordinate subspace, estimating projected parameters, and recovering the remaining parameters through controlled projections. Polynomially many invocations and samples suffice, with recovery up to component permutation when the target precision is below the identifiability radius.

  • Theorem 3.1: A 2k^2-dimensional coordinate subspace decreases the radius of identifiability by at most a factor of 1/n.The subspace is guaranteed to preserve enough separation for subsequent parameter learning.
  • Step 2: Projected mixture parameters are estimated first, including mixing weights, projected means, and covariance minors within the selected subspace.This initializes recovery of the full parameter vector.
  • Step 2a: Each coordinate outside the selected subspace is added individually to estimate corresponding means, diagonal covariances, and selected off-diagonal entries.The radius of identifiability does not decrease when moving from the selected subspace to these one-coordinate extensions.
  • Step 2b: Remaining covariance entries are recovered by projecting onto subspaces that add pairs of coordinates outside the selected subspace.The procedure repeats over the relevant coordinate pairs, while preserving the identifiability radius.
  • Final guarantee: If ǫ < R(θ), the resulting parameter estimate is within ǫ of the target up to permutation with probability greater than 1 −δ using polynomially many samples.The total number of calls to Theorem 2.8 and Corollary 2.11 is polynomial in n.
  • Theorem 3.2: The algorithm identifies the subspace by examining all 2k^2-coordinate projections and choosing the one with the largest estimated identifiability radius.The estimates are obtained using Theorem 2.8 and combined with a union bound over projections.

D Moment Concentration

The moment concentration argument bounds the deviation of empirical moments from their population values uniformly over an initial set of moments. A polynomial sample size in the number of moments, parameter radius, accuracy, and confidence is sufficient.

  • Uniform concentration: M > CNB^2⌈N/2⌉/(ǫ^2δ) samples suffice to estimate the first N lexicographically ordered moments within ǫ with probability greater than 1 −δ.Here C is a constant, and the bound applies simultaneously to every moment indexed by i ≤ N.
  • Moment estimates: The empirical moments are formed from monomials whose expectations equal the corresponding population moments.For each polynomial monomial f_i, E[f_i(X)] = M_i(θ), while the empirical counterpart averages f_i over the samples.
  • Proof strategy: Chebyshev’s inequality bounds each empirical moment’s error, and a union bound makes the guarantee simultaneous over the first N moments.The lexicographic ordering controls the maximum degree among the moments included in the bound.
Loading 1004.4864v1…