# Minimax Optimal Algorithms with Fixed-k-Nearest Neighbors

arXiv: https://arxiv.org/abs/2202.02464 · HTML: https://mlsanity.com/paper/2202.02464/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2022.

## Built on by (most cited first, 1 of 1)

- [Learning conditional distributions on continuous spaces](https://mlsanity.com/paper/2406.09375/) (2024)

## Abstract (arXiv)

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.