On Agnostic Learning of Parities, Monomials, and Halfspaces.
Vitaly FeldmanParikshit GopalanSubhash KhotAshok Kumar PonnuswamiPublished in: SIAM J. Comput. (2009)
Keyphrases
- agnostic learning
- multivariate polynomials
- uniform distribution
- noise tolerant
- membership queries
- pac learning
- binary classification problems
- decision lists
- concept class
- target function
- boosting algorithms
- low degree
- concept classes
- exact learning
- learning algorithm
- complexity analysis
- random sampling
- boolean functions
- lower bound