Agnostic Learning of Monomials by Halfspaces is Hard.
Vitaly FeldmanVenkatesan GuruswamiPrasad RaghavendraYi WuPublished in: Electron. Colloquium Comput. Complex. (2010)
Keyphrases
- agnostic learning
- uniform distribution
- multivariate polynomials
- noise tolerant
- membership queries
- linear threshold functions
- pac learning
- concept class
- target function
- boosting algorithms
- decision lists
- boolean functions
- binary classification problems
- low degree
- term dnf
- learning algorithm
- learning theory
- special case