  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.
