Adaptive Metric Dimensionality Reduction
This work addresses the challenge of high-dimensional data in machine learning by adapting dimensionality reduction to metric spaces, offering potential efficiency gains for tasks like proximity search, though it appears incremental in extending PCA-like methods to non-Euclidean settings.
The paper tackles the problem of dimensionality reduction in supervised learning for metric spaces by providing a generalization bound for Lipschitz functions and an efficient algorithm to approximate intrinsic dimension, leading to more efficient algorithms and improved generalization bounds.
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.