The True Sample Complexity of Identifying Good Arms.
Julian Katz-SamuelsKevin G. JamiesonPublished in: AISTATS (2020)
Keyphrases
- sample complexity
- theoretical analysis
- learning problems
- upper bound
- pac learning
- vc dimension
- lower bound
- active learning
- generalization error
- learning algorithm
- special case
- pac learnability
- supervised learning
- concept classes
- sample size
- sample complexity bounds
- learning tasks
- kernel methods
- irrelevant features
- noise tolerant
- linear threshold
- covering numbers
- prior knowledge
- similarity measure