Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors

Abstract

This paper presents how to perform minimax optimal classification, regression, and density estimation based on fixed-\(k\) nearest neighbor (NN) searches. We consider a distributed learning scenario, in which a massive dataset is split into smaller groups, where the \(k\)-NNs are found for a query point with respect to each subset of data. We propose *optimal* rules to aggregate the fixed-\(k\)-NN information for classification, regression, and density estimation that achieve minimax optimal rates for the respective problems. We show that the distributed algorithm with a fixed \(k\) over a sufficiently large number of groups attains a minimax optimal error rate up to a multiplicative logarithmic factor under some regularity conditions. Roughly speaking, distributed \(k\)-NN rules with \(M\) groups has a performance comparable to the standard \(\Theta(kM)\)-NN rules even for fixed \(k\).

Stats

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

Related papers

• Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression (2019)8.35
• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• A Fast And Easy Regression Technique For K-nn Classification Without Using Negative Pairs (2018)0.00
• A Two-stage Active Learning Algorithm For \(k\)-nearest Neighbors (2022)0.00