Speculate-Correct Error Bounds for k-Nearest Neighbor Classifiers

Eric Bax, Lingjie Weng, Xu Tian

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…