Speculate-Correct Error Bounds for k-Nearest Neighbor Classifiers

We introduce the speculate-correct method to derive error bounds for local classifiers. Using it, we show that k-nearest neighbor classifiers, in spite of their famously (fractured decision boundaries, have exponential error bounds (k) with O lnn)/n error bound range for n in-sample examples. Keywords: nearest neighbors, statistical learning, supervised learning, error bounds, generalization 2000 MSC: 62G99, 2000 MSC: 68Q32, 2000 MSC: 62M99 1. Introduction Local classifiers use only a small subset of their examples to classify each input. The best-known local classifier is the nearest neighbor classifier. To classify an example, a k-nearest neighbor (k-nn) classifier uses a majority vote over the k in-sample examples closest to the example. We assume k is odd, and we assume binary classification.