Fast And Bayes-consistent Nearest Neighbors

Abstract

Research on nearest-neighbor methods tends to focus somewhat dichotomously either on the statistical or the computational aspects -- either on, say, Bayes consistency and rates of convergence or on techniques for speeding up the proximity search. This paper aims at bridging these realms: to reap the advantages of fast evaluation time while maintaining Bayes consistency, and further without sacrificing too much in the risk decay rate. We combine the locality-sensitive hashing (LSH) technique with a novel missing-mass argument to obtain a fast and Bayes-consistent classifier. Our algorithm's prediction runtime compares favorably against state of the art approximate NN methods, while maintaining Bayes-consistency and attaining rates comparable to minimax. On samples of size \(n\) in \(\R^d\), our pre-processing phase has runtime \(O(d n log n)\), while the evaluation phase has runtime \(O(dlog n)\) per query point.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyefremenko2019fast

Related papers

• Nearest-neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions (2017)0.00
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Associative Memories To Accelerate Approximate Nearest Neighbor Search (2016)6.34
• Local Distance Metric Learning For Nearest Neighbor Algorithm (2018)0.00
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44