Polynomial Learning of Distribution Families

Abstract

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.

24 pages

References in corpus (3)

• A Two-round Variant of EM for Gaussian Mixtures
• Learning Mixtures of Gaussians using the k-means Algorithm
• Learning Gaussian Mixtures with Arbitrary Separation

Cited by in corpus (55)

• A Spectral Algorithm for Latent Dirichlet Allocation
• An Analysis of the t-SNE Algorithm for Data Visualization
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• A Method of Moments for Mixture Models and Hidden Markov Models
• Moment Varieties of Gaussian Mixtures
• Learning mixtures of structured distributions over discrete domains
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
• $k$-means as a variational EM approximation of Gaussian mixture models
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• $k$-MLE: A fast algorithm for learning statistical mixture models
• Local algorithms for interactive clustering
• The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures
• Ten Steps of EM Suffice for Mixtures of Two Gaussians
• Training Gaussian Mixture Models at Scale via Coresets
• Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
• Improved Spectral-Norm Bounds for Clustering
• Near-optimal-sample estimators for spherical Gaussian mixtures
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions
• Learning Mixtures of Gaussians in High Dimensions
• A Latent Source Model for Online Collaborative Filtering
• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
• On learning parametric-output HMMs
• Robustly Learning any Clusterable Mixture of Gaussians
• Optimal estimation of Gaussian mixtures via denoised method of moments
• Monotone probability distributions over the Boolean cube can be learned with sublinear samples
• A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
• Smoothed Analysis of Tensor Decompositions
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Theoretical Analysis of the $k$-Means Algorithm - A Survey
• Sketching for Large-Scale Learning of Mixture Models
• Divide-and-Conquer Learning by Anchoring a Conical Hull
• Coresets for Gaussian Mixture Models of Any Shape
• Learning High-Dimensional Mixtures of Graphical Models
• Fourier PCA and Robust Tensor Decomposition
• Identifiability and optimal rates of convergence for parameters of multiple types in finite mixtures
• Robustly Clustering a Mixture of Gaussians
• Provable Sparse Tensor Decomposition
• Recovery guarantees for exemplar-based clustering
• Recovering Structured Probability Matrices
• Estimating the number and effect sizes of non-null hypotheses
• Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries
• On the Behavior of the Expectation-Maximization Algorithm for Mixture Models
• Sparse Solutions to Nonnegative Linear Systems and Applications
• Learning Mixtures of Arbitrary Distributions over Large Discrete Domains
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• On Convergence of Epanechnikov Mean Shift
• Some techniques in density estimation
• Using Multiple Samples to Learn Mixture Models
• Efficient Tensor Decomposition
• Learning Parametric-Output HMMs with Two Aliased States
• Algebraic and Analytic Approaches for Parameter Learning in Mixture Models
• Efficient Density Estimation via Piecewise Polynomial Approximation
• Geometric Methods for Robust Data Analysis in High Dimension