2012/10/02 by Siu-On Chan, Ilias Diakonikolas, Chan, Siu-on +5 · 6 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1210.0864
openalex publication_date 2012/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let \mathfrakC be a class of probability distributions over the discrete domain [n] = \1,...,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.