mlsanityData to 7 Oct 2026

Analysis of KNN Density Estimation

arXiv 2010.00438 ↗First posted 30 Sep 2020stat.ML cs.LGcited by 28

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 3; 2023: 6; 2024: 5; 2025: 7; 2026: 5.

28 papers.

Sort:

By area:

  1. 2022Out-of-Distribution Detection with Deep Nearest Neighborscited by 596
  2. 2022Back to the Basics: Revisiting Out-of-Distribution Detection Baselinescited by 16
  3. 2025CT-PatchTST: Channel-Time Patch Time-Series Transformer for Long-Term Renewable Energy Forecastingcited by 15
  4. 2023From Posterior Sampling to Meaningful Diversity in Image Restorationcited by 12
  5. 2023Robust Nonparametric Regression under Poisoning Attackcited by 11
  6. 2023Model-free Test Time Adaptation for Out-Of-Distribution Detectioncited by 9
  7. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  8. 2024Contextual Bandits for Unbounded Context Distributionscited by 8
  9. 2025Enhancing Customer Contact Efficiency with Graph Neural Networks in Credit Card Fraud Detection Workflowcited by 8
  10. 2025Know When to Abstain: Optimal Selective Classification with Likelihood Ratioscited by 5
  11. 2025Outlier Synthesis via Hamiltonian Monte Carlo for Out-of-Distribution Detectioncited by 4
  12. 2024Learning with User-Level Local Differential Privacycited by 3
16 more
  1. 2025SketchAgent: Generating Structured Diagrams from Hand-Drawn Sketchescited by 3
  2. 2021Label Smoothed Embedding Hypothesis for Out-of-Distribution Detectioncited by 1
  3. 2021Active Coveringcited by 1
  4. 2023Detecting and Learning Out-of-Distribution Data in the Open world: Algorithm and Theorycited by 1
  5. 2025Behavioral Entropy-Guided Dataset Generation for Offline Reinforcement Learningcited by 1
  6. 2026Nearest-Neighbor Density Estimation for Dependency Suppressioncited by 1
  7. 2026Conformalized Signal Temporal Logic Inference under Covariate Shiftcited by 1
  8. 2022Bagged k-Distance for Mode-Based Clustering Using the Probability of Localized Level Setscited by 0
  9. 2023Bootstrapped Edge Count Tests for Nonparametric Two-Sample Inference Under Heterogeneitycited by 0
  10. 2024ICM Ensemble with Novel Betting Functions for Concept Driftcited by 0
  11. 2024Density Estimation via Binless Multidimensional Integrationcited by 0
  12. 2024Distribution Learning with Valid Outputs Beyond the Worst-Casecited by 0
  13. 2025Adaptive Conformal Prediction for Quantum Machine Learningcited by 0
  14. 2026CREDO: Epistemic-Aware Conformalized Credal Envelopes for Regressioncited by 0
  15. 2026Variance-Reduced Manifold Sampling via Polynomial-Maximization Density Estimationcited by 0
  16. 2026Estimating Mixture Distributions via Stochastic Mirror Descentcited by 0