Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.
Ilias DiakonikolasRyan O'DonnellRocco A. ServedioYi WuPublished in: SODA (2011)
Keyphrases
- agnostic learning
- threshold functions
- low degree
- decision lists
- linear threshold
- noise tolerant
- uniform distribution
- decision trees
- membership queries
- binary classification problems
- pac learning
- learning algorithm
- boolean functions
- learning problems
- sampling algorithm
- concept class
- sample complexity
- exact learning
- learning tasks
- supervised learning
- machine learning