Learning DNF Under the Uniform Distribution in Quasi-Polynomial Time
Abstract
Abstract One of the longest standing open problems in the theory of learnability within the Valiant Learning Framework is the question of the learnability of the class of DNF formulae. Recent results by [LMN 89] make progress towards resolving this question by giving an algorithm for learning the class of DNF formulae under the uniform distribution requiring quasi-polynomial time and a quasi-polynomial number of examples. In this paper, we give an algorithm for learning DNF under the uniform distribution which also requires quasi-polynomial time, but which requires only a polynomial number of examples. In addition to the improvement from a quasi-polynomial to a polynomial sample complexity, the proofs given here are notably simpler than those of [LMN 89].
Cite
Text
Verbeurgt. "Learning DNF Under the Uniform Distribution in Quasi-Polynomial Time." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50027-8Markdown
[Verbeurgt. "Learning DNF Under the Uniform Distribution in Quasi-Polynomial Time." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/verbeurgt1990colt-learning/) doi:10.1016/B978-1-55860-146-8.50027-8BibTeX
@inproceedings{verbeurgt1990colt-learning,
title = {{Learning DNF Under the Uniform Distribution in Quasi-Polynomial Time}},
author = {Verbeurgt, Karsten A.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1990},
pages = {314-326},
doi = {10.1016/B978-1-55860-146-8.50027-8},
url = {https://mlanthology.org/colt/1990/verbeurgt1990colt-learning/}
}