Average-Case PAC-Learning from Nisan's Natural Proofs.
Ari KarchmerPublished in: Electron. Colloquium Comput. Complex. (2023)
Keyphrases
- compression scheme
- average case
- pac learning
- vc dimension
- uniform distribution
- computational learning theory
- efficiently learnable
- concept classes
- sample complexity
- boolean functions
- mistake bound
- concept class
- agnostic learning
- target concept
- learning theory
- data mining
- data sets
- membership queries
- training examples
- sample size
- model selection
- vector space
- statistical queries
- special case
- inductive inference
- noisy data