Learning mixtures of structured distributions over discrete domains

DOI10.1137/1.9781611973105.100zbMATH Open1421.68144arXiv1210.0864OpenAlexW1763164889MaRDI QIDQ5741809FDOQ5741809

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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (12)

• Title not available (Why is that?)
• 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)