On PAC learning algorithms for rich Boolean function classes

Lisa Hellerstein, Rocco A. Servedio

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube {0, 1}n and sparse GF2 polynomials over {0, 1}n.

    Original languageEnglish (US)
    Pages (from-to)66-76
    Number of pages11
    JournalTheoretical Computer Science
    Volume384
    Issue number1
    DOIs
    StatePublished - Sep 24 2007

    Keywords

    • Computational learning theory
    • PAC learning
    • Polynomial threshold function

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'On PAC learning algorithms for rich Boolean function classes'. Together they form a unique fingerprint.

    Cite this