Carnegie Mellon University
Browse

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

Download (277.33 kB)
journal contribution
posted on 1992-06-01, 00:00 authored by Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu
Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in Rn x {-1; 1}.

History

Date

1992-06-01

Usage metrics

    Categories

    Keywords

    computer sciencesInformation and Computing Sciences not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC