Learning mixtures of structured distributions over discrete domains

DOI10.1137/1.9781611973105.100MaRDI QIDQ5741809zbMATH OpenOpenAlexFDO

Authors Siu On Chan, Ilias Diakonikolas, Xiaorui Sun, Rocco A. Servedio

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.0864

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Characterization and structure theory of statistical distributions (62E10) Analysis of algorithms (68W40)

Abstract: Let $mathfrakC$ be a class of probability distributions over the discrete domain $[n]=1,\mathrm{...},n.$ We show that if $mathfrakC$ satisfies a rather general condition -- essentially, that each distribution in $mathfrakC$ 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 $mathfrakC.$ 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.

Recommendations

• Learning Mixtures of Product Distributions over Discrete Domains
• Efficient density estimation via piecewise polynomial approximation
• Learning mixtures of arbitrary distributions over large discrete domains
• Learning \(k\)-modal distributions via testing
• Learning \(k\)-modal distributions via testing

Cited in

(12)

• scientific article; zbMATH DE number 7525505 (Why is no real title available?)
• Efficient density estimation via piecewise polynomial approximation
• Robust estimators in high-dimensions without the computational intractability
• Learning mixtures of arbitrary distributions over large discrete domains
• Testing Data Binnings
• On the nonparametric maximum likelihood estimator for Gaussian location mixture densities with application to Gaussian denoising
• Efficiently learning structured distributions from untrusted batches
• Sampling correctors
• Density estimation for shift-invariant multidimensional distributions
• Learning Mixtures of Product Distributions over Discrete Domains
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• Testing shape restrictions of discrete distributions

This page was built for publication: Learning mixtures of structured distributions over discrete domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741809)