Explaining the Success of Nearest Neighbor Methods in Prediction

Many modern methods for prediction leverage nearest neighbour search to find past training examples most similar to a test example, an idea that dates back in text to at least the 11th century and has stood the test of time.This monograph explains the success of these methods, both in theory, covering foundational nonasymptotic statistical guarantees on nearest-neighbour-based regression and classification, and in practice, gathering prominent methods for approximate nearest neighbor search that have been essential to scaling prediction systems reliant on nearest neighbor analysis to handle massive datasets. Furthermore, it looks at connections to learning distances for use with nearest neighbor methods, including how random decision trees and ensemble methods learn nearest neighbor structure, as well as recent developments in crowdsourcing and graphons.