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
2106458073 1763164889 2570121038 2952554977
We give a computationally efficient algorithm that learns (under distributional assumptions) a halfspace in the difficult agnostic framework of Kearns, Schapire, and Sellie [Mach. Learn., 17 (1994), pp. 115-141], where a learner is given access to a distribution on labelled examples but where the labelling may be arbitrary (similar to malicious noise). It constructs a hypothesis whose error rate on future examples is within an additive @math of the optimal halfspace, in time poly @math for any constant @math , for the uniform distribution over @math or unit sphere in @math as well as any log-concave distribution in @math . It also agnostically learns Boolean disjunctions in time @math with respect to any distribution. Our algorithm, which performs @math polynomial regression, is a natural noise-tolerant arbitrary-distribution generalization of the well-known “low-degree” Fourier algorithm of Linial, Mansour, and Nisan. We observe that significant improvements on the running time of our algorithm would yield the fastest known algorithm for learning parity with noise, a challenging open problem in computational learning theory. 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. Let @math be a uniformly distributed random @math -SAT formula with @math variables and @math clauses. We present a polynomial time algorithm that finds a satisfying assignment of @math with high probability for constraint densities @math , where @math . Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond @math [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312-355]. In this paper we consider a fragment of the first-order theory of the real numbers that includes systems of equations of continuous functions in bounded domains, and for which all functions are computable in the sense that it is possible to compute arbitrarily close piece-wise interval approximations. Even though this fragment is undecidable, we prove that there is a (possibly non-terminating) algorithm for checking satisfiability such that (1) whenever it terminates, it computes a correct answer, and (2) it always terminates when the input is robust. A formula is robust, if its satisfiability does not change under small perturbations. As a basic tool for our algorithm we use the notion of degree from the field of (differential) topology.