PAC-learning is Undecidable.
Sairaam VenkatramanS. BalasubramanianR. Raghunatha SarmaPublished in: CoRR (2018)
Keyphrases
- learning algorithm
- pac learning
- sample complexity
- learning problems
- membership queries
- computational learning theory
- uniform distribution
- target concept
- concept classes
- learning theory
- vc dimension
- np complete
- learning tasks
- pac learnability
- agnostic learning
- training data
- sample size
- decision lists
- statistical queries
- boolean functions
- dnf formulas