← Back to papers
2014 NIPS NeurIPS 2014

Optimal rates for k-NN density and mode estimation

Abstract

We present two related contributions of independent interest: (1) high-probability finite sample rates for $k$-NN density estimation, and (2) practical mode estimators -- based on $k$-NN -- which attain minimax-optimal rates under surprisingly general distributional conditions.

🧭 Keyword Pioneer — mode estimation
🐣 Hot Topic Early Bird — density estimation
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy

Authors

Sanjoy Dasgupta , Samory Kpotufe

Topics

Machine Learning > Core Methods > Clustering Machine Learning > Core Methods > Regression Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Optimization & Theory > Theory Machine Learning > Core Methods > Density Estimation

Keywords

density estimation mode estimation nonparametric statistics minimax rate minimax optimal rate k-nn estimation minimax-optimal rate k-nn density estimation finite sample rate
Download PDF

Related papers

Information-based learning by agents in unbounded state spaces 2014
Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm 2014
Partition-wise Linear Models 2014
Active Regression by Stratification 2014
Cone-Constrained Principal Component Analysis 2014