  We study adaptive data-dependent dimensionality reduction in the context of
supervised learning in general metric spaces. Our main statistical contribution
is a generalization bound for Lipschitz functions in metric spaces that are
doubling, or nearly doubling. On the algorithmic front, we describe an analogue
of PCA for metric spaces: namely an efficient procedure that approximates the
data's intrinsic dimension, which is often much lower than the ambient
dimension. Our approach thus leverages the dual benefits of low dimensionality:
(1) more efficient algorithms, e.g., for proximity search, and (2) more
optimistic generalization bounds.
