Let @math be a class of probability distributions over the discrete domain @math We show that if @math satisfies a rather general condition -- essentially, that each distribution in @math 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 @math unknown distributions from @math We analyze several natural types of distributions over @math , 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.
On construit des estimateurs non parametriques da la fonction de repartition F et de sa fonction de hasard dans la classe de toutes les distributions IFR Consider non-parametric estimation of a decreasing density function f under the random (right) censorship model. Alternatively, consider estimation of a monotone increasing (or decreasing) hazard rate i based on randomly right censored data. We show that the non-paramet- ric maximum likelihood estimator of the density f (introduced by Laslett, 1982) is asymptotically equivalent to the estimator obtained by differentiating the least concave majorant of the Kaplan-Meier estimator, the non-parametric maximum likelihood estimator of the distribution function F in the larger model without any monotonicity assumption. A similar result is shown to hold for the non-parametric maximum likelihood estimator of an increasing hazard rate A: the non-parametric maximum likelihood estimator of A (introduced in the uncensored case by Prakasa Rao, 1970) is asymptotically equivalent to the estimator obtained by differentiation of the greatest convex minorant of the Nelson-Aalen estimator, the non-parametric maximum likelihood estimator of the cumulative hazard function A in the larger model without any monotonicity assumption. In proving these asymptotic equivalences, we also establish the asymptotic distributions of the different estimators at a fixed point at which the monotonicity assumption is strictly satisfied.  We propose a new method for pointwise estimation of monotone, uni- modal and U-shaped failure rates, under a right-censoring mechanism, using non- parametric likelihood ratios. The asymptotic distribution of the likelihood ratio is pivotal, though non-standard, and can therefore be used to construct asymptotic confidence intervals for the failure rate at a point of interest, via inversion. Major advantages of the new method lie in the facts that it completely avoids estima- tion of nuisance parameters, or the choice of a bandwidth tuning parameter, and is extremely easy to implement. The new method is shown to perform competi- tively in simulations, and is illustrated on a data set involving time to diagnosis of schizophrenia in the Jerusalem Perinatal Cohort Schizophrenia Study.