Agnostic Learning of Monomials by Halfspaces is Hard
Vitaly FeldmanVenkatesan GuruswamiPrasad RaghavendraYi WuPublished in: CoRR (2010)
Keyphrases
- agnostic learning
- uniform distribution
- multivariate polynomials
- membership queries
- linear threshold functions
- pac learning
- noise tolerant
- concept class
- term dnf
- concept classes
- decision lists
- target function
- boosting algorithms
- low degree
- boolean functions
- loss function
- optimal solution
- statistical queries
- efficient learning
- learning theory
- linear combination