An O(n) Learning Algorithm for DNF Under the Uniform Distribution.log log n

Yishay MansourCOLT 1992 · OpenReview

Abstract

We show that a DNF with terms of size at most d can be approximated by a function with at most dO(d log 1/ε))non zero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most ε. This property is used to derive a learning algorithm for DNF, under the uniform distribution. The learning algorithm uses queries and learns, with respect to the uniform distribution, a DNF with terms of size at most d in time polynomial in n and dO(d log 1/egr;). The interesting implications are for the case when ε is constant. In this case our algorithm learns a DNF with a polynomial number of terms in time nO(log log n), and a DNF with terms of size at most O(log n/log log n) in polynomial time.
BibTeX
@inproceedings{mansour1992o,
  author = {Yishay Mansour},
  title = {{An O(n) Learning Algorithm for DNF Under the Uniform Distribution.log log n}},
  booktitle = {Conference on Learning Theory},
  year = {1992},
  url = {https://openreview.net/forum?id=vXsSaVno0X_},
}

Loading related content...

Figure