k-NN Regression Adapts to Local Intrinsic Dimension

Abstract

Many nonparametric regressors were recently shown to converge at rates that depend only on the intrinsic dimension of data. These regressors thus escape the curse of dimension when high-dimensional data has low intrinsic dimension (e.g. a manifold). We show that k-NN regression is also adaptive to intrinsic dimension. In particular our rates are local to a query x and depend only on the way masses of balls centered at x vary with radius. Furthermore, we show a simple way to choose k = k(x) locally at any x so as to nearly achieve the minimax rate at x in terms of the unknown intrinsic dimension in the vicinity of x. We also establish that the minimax rate does not depend on a particular choice of metric space or distribution, but rather that this minimax rate holds for any metric space and doubling measure.

References in corpus (2)

• Local polynomial regression on unknown manifolds
• Escaping the curse of dimensionality with a tree-based regressor

Cited by in corpus (20)

• Kernel Mean Embedding of Distributions: A Review and Beyond
• Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
• Nonparametric Conditional Density Estimation in a High-Dimensional Regression Setting
• A Spectral Series Approach to High-Dimensional Nonparametric Regression
• Approximation of Functions over Manifolds: A Moving Least-Squares Approach
• Density-sensitive semisupervised inference
• Active Nearest-Neighbor Learning in Metric Spaces
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression
• Nearest Neighbor and Kernel Survival Analysis: Nonasymptotic Error Bounds and Strong Consistency Rates
• Classification with unknown class-conditional label noise on non-compact feature spaces
• Adaptive Non-Parametric Regression With the $K$-NN Fused Lasso
• Functions with average smoothness: structure, algorithms, and learning
• Multiscale regression on unknown manifolds
• K-NN active learning under local smoothness assumption
• Global and Local Two-Sample Tests via Regression
• Breaking the curse of dimensionality with Isolation Kernel
• Optimal choice of $k$ for $k$-nearest neighbor regression
• Locally-Adaptive Nonparametric Online Learning
• Minimum discrepancy principle strategy for choosing $k$ in $k$-NN regression