We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let @math be an arbitrary distribution over an interval @math which is @math -close (in total variation distance) to an unknown probability distribution @math that is defined by an unknown partition of @math into @math intervals and @math unknown degree- @math polynomials specifying @math over each of the intervals. We give an algorithm that draws @math samples from @math , runs in time @math , and with high probability outputs a piecewise polynomial hypothesis distribution @math that is @math -close (in total variation distance) to @math . This sample complexity is essentially optimal; we show that even for @math , any algorithm that learns an unknown @math -piecewise degree- @math probability distribution over @math to accuracy @math must use @math samples from the distribution, regardless of its running time. Our algorithm combines tools from approximation theory, uniform convergence, linear programming, and dynamic programming. We apply this general algorithm to obtain a wide range of results for many natural problems in density estimation over both continuous and discrete domains. These include state-of-the-art results for learning mixtures of log-concave distributions; mixtures of @math -modal distributions; mixtures of Monotone Hazard Rate distributions; mixtures of Poisson Binomial Distributions; mixtures of Gaussians; and mixtures of @math -monotone densities. Our general technique yields computationally efficient algorithms for all these problems, in many cases with provably optimal sample complexities (up to logarithmic factors) in all parameters.
The main result of @cite_15 is an efficient algorithm for learning any @math -mixture of @math -piecewise constant distributions:
@cite_15
1763164889
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.