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 -NN regression is also adaptive to intrinsic dimension. In particular our rates are local to a query and depend only on the way masses of balls centered at vary with radius. Furthermore, we show a simple way to choose locally at any so as to nearly achieve the minimax rate at in terms of the unknown intrinsic dimension in the vicinity of . 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.
Chat is not available.