2 papers
cs.LG2013
Efficient Density Estimation via Piecewise Polynomial Approximation
Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio +1
We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let …
cs.LG2011
Tight Bounds on Proper Equivalence Query Learning of DNF
Lisa Hellerstein, Devorah Kletenik, Linda Sellie +1
We prove a new structural lemma for partial Boolean functions , which we call the seed lemma for DNF. Using the lemma, we give the first subexponential algorithm for proper lear…