Agnostic Learning of Monomials by Halfspaces Is Hard.
Vitaly FeldmanVenkatesan GuruswamiPrasad RaghavendraYi WuPublished in: FOCS (2009)
Keyphrases
- agnostic learning
- uniform distribution
- multivariate polynomials
- membership queries
- noise tolerant
- pac learning
- linear threshold functions
- concept class
- boosting algorithms
- decision lists
- target function
- binary classification problems
- learning theory
- concept classes
- dnf formulas
- low degree
- version space
- feature selection
- exact learning
- term dnf
- loss function
- training data