# Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2019.

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

- [Robust Nonparametric Regression under Poisoning Attack](https://mlsanity.com/paper/2305.16771/) (2023)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Under-bagging Nearest Neighbors for Imbalanced Classification](https://mlsanity.com/paper/2109.00531/) (2021)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selection](https://mlsanity.com/paper/2402.01635/) (2024)
- [Enhancing Learning with Label Differential Privacy by Vector Approximation](https://mlsanity.com/paper/2405.15150/) (2024)
- [On Theoretical Limits of Learning with Label Differential Privacy](https://mlsanity.com/paper/2502.14309/) (2025)
- [Model Privacy: A Unified Framework for Understanding Model Stealing Attacks and Defenses](https://mlsanity.com/paper/2502.15567/) (2025)
- [Conditional mean embeddings and optimal feature selection via positive definite kernels](https://mlsanity.com/paper/2305.08100/) (2023)
- [Soft Label PU Learning](https://mlsanity.com/paper/2405.01990/) (2024)

## Abstract (arXiv)

k Nearest Neighbor (kNN) method is a simple and popular statistical method for classification and regression. For both classification and regression problems, existing works have shown that, if the distribution of the feature vector has bounded support and the probability density function is bounded away from zero in its support, the convergence rate of the standard kNN method, in which k is the same for all test samples, is minimax optimal. On the contrary, if the distribution has unbounded support, we show that there is a gap between the convergence rate achieved by the standard kNN method and the minimax bound. To close this gap, we propose an adaptive kNN method, in which different k is selected for different samples. Our selection rule does not require precise knowledge of the underlying distribution of features. The new proposed method significantly outperforms the standard one. We characterize the convergence rate of the proposed adaptive method, and show that it matches the minimax lower bound.