# Analysis of KNN Density Estimation

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2020.

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

- [Out-of-Distribution Detection with Deep Nearest Neighbors](https://mlsanity.com/paper/2204.06507/) (2022)
- [Back to the Basics: Revisiting Out-of-Distribution Detection Baselines](https://mlsanity.com/paper/2207.03061/) (2022)
- [CT-PatchTST: Channel-Time Patch Time-Series Transformer for Long-Term Renewable Energy Forecasting](https://mlsanity.com/paper/2501.08620/) (2025)
- [From Posterior Sampling to Meaningful Diversity in Image Restoration](https://mlsanity.com/paper/2310.16047/) (2023)
- [Robust Nonparametric Regression under Poisoning Attack](https://mlsanity.com/paper/2305.16771/) (2023)
- [Model-free Test Time Adaptation for Out-Of-Distribution Detection](https://mlsanity.com/paper/2311.16420/) (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)
- [Enhancing Customer Contact Efficiency with Graph Neural Networks in Credit Card Fraud Detection Workflow](https://mlsanity.com/paper/2504.02275/) (2025)
- [Know When to Abstain: Optimal Selective Classification with Likelihood Ratios](https://mlsanity.com/paper/2505.15008/) (2025)
- [Outlier Synthesis via Hamiltonian Monte Carlo for Out-of-Distribution Detection](https://mlsanity.com/paper/2501.16718/) (2025)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [SketchAgent: Generating Structured Diagrams from Hand-Drawn Sketches](https://mlsanity.com/paper/2508.01237/) (2025)
- [Label Smoothed Embedding Hypothesis for Out-of-Distribution Detection](https://mlsanity.com/paper/2102.05131/) (2021)
- [Active Covering](https://mlsanity.com/paper/2106.02552/) (2021)
- [Detecting and Learning Out-of-Distribution Data in the Open world: Algorithm and Theory](https://mlsanity.com/paper/2310.06221/) (2023)
- [Behavioral Entropy-Guided Dataset Generation for Offline Reinforcement Learning](https://mlsanity.com/paper/2502.04141/) (2025)
- [Nearest-Neighbor Density Estimation for Dependency Suppression](https://mlsanity.com/paper/2603.04224/) (2026)
- [Conformalized Signal Temporal Logic Inference under Covariate Shift](https://mlsanity.com/paper/2603.27062/) (2026)
- [Bagged k-Distance for Mode-Based Clustering Using the Probability of Localized Level Sets](https://mlsanity.com/paper/2210.09786/) (2022)
- [Bootstrapped Edge Count Tests for Nonparametric Two-Sample Inference Under Heterogeneity](https://mlsanity.com/paper/2304.13848/) (2023)
- [ICM Ensemble with Novel Betting Functions for Concept Drift](https://mlsanity.com/paper/2406.15760/) (2024)
- [Density Estimation via Binless Multidimensional Integration](https://mlsanity.com/paper/2407.08094/) (2024)
- [Distribution Learning with Valid Outputs Beyond the Worst-Case](https://mlsanity.com/paper/2410.16253/) (2024)
- [Adaptive Conformal Prediction for Quantum Machine Learning](https://mlsanity.com/paper/2511.18225/) (2025)
- [CREDO: Epistemic-Aware Conformalized Credal Envelopes for Regression](https://mlsanity.com/paper/2603.06826/) (2026)
- [Variance-Reduced Manifold Sampling via Polynomial-Maximization Density Estimation](https://mlsanity.com/paper/2605.19938/) (2026)
- [Estimating Mixture Distributions via Stochastic Mirror Descent](https://mlsanity.com/paper/2605.24929/) (2026)

## Abstract (arXiv)

We analyze the ℓ1 and ℓ_∞ convergence rates of k nearest neighbor density estimation method. Our analysis includes two different cases depending on whether the support set is bounded or not. In the first case, the probability density function has a bounded support and is bounded away from zero. We show that kNN density estimation is minimax optimal under both ℓ1 and ℓ_∞ criteria, if the support set is known. If the support set is unknown, then the convergence rate of ℓ1 error is not affected, while ℓ_∞ error does not converge. In the second case, the probability density function can approach zero and is smooth everywhere. Moreover, the Hessian is assumed to decay with the density values. For this case, our result shows that the ℓ_∞ error of kNN density estimation is nearly minimax optimal. The ℓ1 error does not reach the minimax lower bound, but is better than kernel density estimation.