Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise.
Shiwei ZengJie ShenPublished in: CoRR (2023)
Keyphrases
- threshold functions
- low degree
- pac learning
- uniform distribution
- decision lists
- agnostic learning
- concept classes
- boolean functions
- computational learning theory
- linear threshold
- pac model
- noise model
- sample complexity
- learning theory
- membership queries
- concept class
- statistical queries
- sample size
- mistake bound
- efficient learning
- learning problems
- target concept
- decision trees
- noise tolerant
- upper bound
- special case
- pairwise