Non-Asymptotic Uniform Rates of Consistency for k-NN Regression

Abstract

We derive high-probability finite-sample uniform rates of consistency for $k$-NN regression that are optimal up to logarithmic factors under mild assumptions. We moreover show that $k$-NN regression adapts to an unknown lower intrinsic dimension automatically. We then apply the $k$-NN regression rates to establish new results about estimating the level sets and global maxima of a function from noisy observations.

In Proceedings of 33rd AAAI Conference on Artificial Intelligence (AAAI 2019)

References in corpus (2)

• Density Level Set Estimation on Manifolds with DBSCAN
• Adaptive Hausdorff estimation of density level sets

Cited by in corpus (2)

• Nonparametric Stochastic Contextual Bandits
• Exploring Partially Observed Networks with Nonparametric Bandits