Learning mixtures of structured distributions over discrete domains

Abstract

Let $\mathfrak{C}$ be a class of probability distributions over the discrete domain $[n]=\{1,...,n\}.$ We show that if $\mathfrak{C}$ satisfies a rather general condition -- essentially, that each distribution in $\mathfrak{C}$ can be well-approximated by a variable-width histogram with few bins -- then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of $k$ unknown distributions from $\mathfrak{C}.$ We analyze several natural types of distributions over $[n]$, including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems.

arXiv commentpreliminary full version of soda'13 paper

References in corpus (3)

• Maximum likelihood estimation of a log-concave density and its distribution function: Basic properties and uniform consistency
• A Two-round Variant of EM for Gaussian Mixtures
• Polynomial Learning of Distribution Families

Cited by in corpus (19)

• Optimal Testing for Properties of Distributions
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
• Near-optimal-sample estimators for spherical Gaussian mixtures
• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Learning Multivariate Log-concave Distributions
• Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
• 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
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Computationally Efficient Robust Estimation of Sparse Functionals
• A Polynomial Time Algorithm for Lossy Population Recovery
• A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
• Learning Structured Distributions From Untrusted Batches: Faster and Simpler
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
• Tight bounds for learning a mixture of two gaussians
• Reinforcement Learning in Reward-Mixing MDPs
• On the Sample Complexity of Learning Sum-Product Networks
• Topological mixture estimation
• Efficient Density Estimation via Piecewise Polynomial Approximation