Distribution-Specific Analysis of Nearest Neighbor Search and Classification

Worst-case bounds described as optimal can remain loose for the data encountered in practice. This talk develops distribution-specific analyses for local, nonparametric methods, focusing on nearest neighbors. The statistical results give closely matching upper and lower bounds for classification convergence for each data distribution, characterize metric measure spaces supporting universal consistency, and motivate a smoothness concept adapted to nearest-neighbor methods. The algorithmic results characterize the performance of tree-based nearest-neighbor search through the configuration of the data, with specializations to common forms of structure. The talk concludes with open statistical and algorithmic questions.