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.
| Author(s): | Kpotufe, S. |
| Book Title: | Advances in Neural Information Processing Systems 24 |
| Pages: | 729-737 |
| Year: | 2011 |
| Day: | 0 |
| Editors: | J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger |
| Bibtex Type: | Conference Paper (inproceedings) |
| Event Name: | Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS 2011) |
| Event Place: | Granada, Spain |
| Digital: | 0 |
| Electronic Archiving: | grant_archive |
| Links: | |
BibTex
@inproceedings{Kpotufe2012,
title = {k-NN Regression Adapts to Local Intrinsic Dimension},
booktitle = {Advances in Neural Information Processing Systems 24},
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.},
pages = {729-737},
editors = {J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger},
year = {2011},
slug = {kpotufe2012},
author = {Kpotufe, S.}
}