Size-Independent Sample Complexity of Neural Networks.
Noah GolowichAlexander RakhlinOhad ShamirPublished in: COLT (2018)
Keyphrases
- sample complexity
- neural network
- theoretical analysis
- vc dimension
- special case
- upper bound
- learning problems
- pac learning
- supervised learning
- constant factor
- active learning
- learning algorithm
- lower bound
- generalization error
- pac learnability
- covering numbers
- sample complexity bounds
- training examples
- computational complexity
- sample size
- concept classes
- uniform convergence
- linear threshold
- sufficient conditions
- data sets