On Using Extended Statistical Queries to Avoid Membership Queries.
Nader H. BshoutyVitaly FeldmanPublished in: COLT/EuroCOLT (2001)
Keyphrases
- statistical queries
- membership queries
- uniform distribution
- pac learning
- boolean functions
- concept class
- dnf formulas
- target concept
- noise tolerant
- exact learning
- concept classes
- classification noise
- learning algorithm
- pac model
- efficient learning
- agnostic learning
- version space
- equivalence queries
- learning theory
- lower bound
- sample size
- sample complexity
- target function
- data sets