Optimal Quantum Sample Complexity of Learning Algorithms.
Srinivasan ArunachalamRonald de WolfPublished in: J. Mach. Learn. Res. (2018)
Keyphrases
- sample complexity
- learning algorithm
- learning problems
- theoretical analysis
- active learning
- upper bound
- supervised learning
- vc dimension
- generalization error
- lower bound
- training examples
- pac learning
- worst case
- special case
- linear threshold
- sample size
- dynamic programming
- machine learning algorithms
- optimal solution
- number of irrelevant features
- learning tasks
- training data
- concept classes
- objective function
- pac learning model