Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
Ilias DiakonikolasRyan O'DonnellRocco A. ServedioYi WuPublished in: CoRR (2010)
Keyphrases
- agnostic learning
- threshold functions
- low degree
- decision lists
- uniform distribution
- noise tolerant
- linear threshold
- boolean functions
- learning problems
- pac learning
- concept class
- reinforcement learning
- learning theory
- learning algorithm
- binary classification problems
- target function
- pac model
- decision trees
- concept classes
- positive and negative
- theoretical analysis
- supervised learning
- training data