Tight Bounds on Proper Equivalence Query Learning of DNF
Abstract
We prove a new structural lemma for partial Boolean functions \emphf, which we call the \emphseed lemma for \emphDNF. Using the lemma, we give the first subexponential algorithm for proper learning of poly(\emphn)-term DNF in Angluin’s Equivalence Query (EQ) model. The algorithm has time and query complexity 2^(Õ√\emphn), which is optimal. We also give a new result on certificates for DNF-size, a simple algorithm for properly PAC-learning DNF, and new results on EQ-learning log \emphn-term DNF and decision trees.
Cite
Text
Hellerstein et al. "Tight Bounds on Proper Equivalence Query Learning of DNF." Proceedings of the 25th Annual Conference on Learning Theory, 2012.Markdown
[Hellerstein et al. "Tight Bounds on Proper Equivalence Query Learning of DNF." Proceedings of the 25th Annual Conference on Learning Theory, 2012.](https://mlanthology.org/colt/2012/hellerstein2012colt-tight/)BibTeX
@inproceedings{hellerstein2012colt-tight,
title = {{Tight Bounds on Proper Equivalence Query Learning of DNF}},
author = {Hellerstein, Lisa and Kletenik, Devorah and Sellie, Linda and Servedio, Rocco},
booktitle = {Proceedings of the 25th Annual Conference on Learning Theory},
year = {2012},
pages = {31.1-31.18},
volume = {23},
url = {https://mlanthology.org/colt/2012/hellerstein2012colt-tight/}
}