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

Authors

  • Heinrich Jiang Google

DOI:

https://doi.org/10.1609/aaai.v33i01.33013999

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 in the sup-norm. 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.

Downloads

Published

2019-07-17

How to Cite

Jiang, H. (2019). Non-Asymptotic Uniform Rates of Consistency for k-NN Regression. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 3999-4006. https://doi.org/10.1609/aaai.v33i01.33013999

Issue

Section

AAAI Technical Track: Machine Learning