Bellman Strikes Again! The Growth Rate of Sample Complexity with Dimension for the Nearest Neighbor Classifier.
Santosh S. VenkateshRobert R. SnappDemetri PsaltisPublished in: COLT (1992)
Keyphrases
- sample complexity
- nearest neighbor classifier
- growth rate
- theoretical analysis
- training samples
- nearest neighbor
- pac learning
- learning algorithm
- vc dimension
- upper bound
- learning problems
- supervised learning
- special case
- active learning
- generalization error
- lower bound
- distance measure
- dynamic time warping
- training examples
- economic development
- complexity measures
- concept classes
- sample size
- irrelevant features
- pattern recognition
- training data
- highly correlated
- machine learning algorithms
- high dimensional
- neural network