General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Bounding
Javed A. AslamScott E. DecaturPublished in: FOCS (1993)
Keyphrases
- pac learning
- statistical queries
- learning problems
- classification noise
- pac model
- uniform distribution
- noise tolerant
- pac learning model
- sample complexity
- learning theory
- lower bound
- noisy data
- computational learning theory
- upper bound
- learning algorithm
- learning tasks
- mistake bound
- vc dimension
- concept learning
- sample size
- attribute noise
- supervised learning
- decision trees
- exact learning
- machine learning algorithms
- agnostic learning
- decision lists
- learning process
- concept class
- noise model
- machine learning
- reinforcement learning
- boolean functions
- membership queries
- pac learnable