## Abstract

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

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.

Original language | English |
---|---|

Publisher | Computing Research Repository (CoRR) |

Volume | abs/1210.0864 |

Publication status | Published - 2012 |