Explaining The Success Of Nearest Neighbor Methods In Prediction

Abstract

Many modern methods for prediction leverage nearest neighbor 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 aims to explain the success of these methods, both in theory, for which we cover foundational nonasymptotic statistical guarantees on nearest-neighbor-based regression and classification, and in practice, for which we gather 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, we discuss 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. In terms of theory, our focus is on nonasymptotic statistical guarantees, which we state in the form of ho

Stats

• citations89
• S2 citations—
• github stars0
• HF likes0
• heat score18.63
• arxiv keychen2025explaining

Related papers

• Graph-based Nearest Neighbor Search: From Practice To Theory (2019)0.00
• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Why Do Nearest Neighbor Language Models Work? (2023)3.56
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• Learning To Index For Nearest Neighbor Search (2018)10.35
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• Fast And Bayes-consistent Nearest Neighbors (2019)0.00
• Worst-case Performance Of Popular Approximate Nearest Neighbor Search Implementations: Guarantees And Limitations (2023)5.84