Proper PAC learning is compressing.
Shay MoranAmir YehudayoffPublished in: Electron. Colloquium Comput. Complex. (2015)
Keyphrases
- pac learning
- uniform distribution
- computational learning theory
- sample size
- learning theory
- sample complexity
- learning problems
- membership queries
- vc dimension
- concept classes
- target concept
- pac learnability
- data compression
- decision lists
- theoretical analysis
- agnostic learning
- contractual obligations
- statistical queries
- boolean functions
- concept class
- noisy data
- high dimensional
- lower bound
- decision trees