Non-Asymptotic Uniform Rates of Consistency for k-NN Regression
This provides theoretical guarantees for k-NN regression and its applications in function estimation, though it appears incremental in extending existing asymptotic results to non-asymptotic settings.
The paper derived optimal finite-sample uniform consistency rates for k-NN regression under mild assumptions, showing it automatically adapts to unknown lower intrinsic dimensions, and applied these rates to establish new results for estimating function level sets and global maxima from noisy observations.
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.