Tight bounds on proper equivalence query learning of DNF

Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco Servedio

    Research output: Contribution to journalConference articlepeer-review


    We prove a new structural lemma for partial Boolean functions f, which we call the seed lemma for DNF. Using the lemma, we give the first subexponential algorithm for proper learning of poly(n)- Term DNF in Angluin's Equivalence Query (EQ) model. The algorithm has time and query complexity 2( Õ √ n), 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 n-term DNF and decision trees.

    Original languageEnglish (US)
    Pages (from-to)31.1-31.18
    JournalJournal of Machine Learning Research
    StatePublished - 2012
    Event25th Annual Conference on Learning Theory, COLT 2012 - Edinburgh, United Kingdom
    Duration: Jun 25 2012Jun 27 2012


    • Certificates
    • DNF
    • Exact learning
    • Proper learning
    • Query learning

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Statistics and Probability
    • Artificial Intelligence


    Dive into the research topics of 'Tight bounds on proper equivalence query learning of DNF'. Together they form a unique fingerprint.

    Cite this