# Adaptive Metric Dimensionality Reduction

arXiv: https://arxiv.org/abs/1302.2752 · HTML: https://mlsanity.com/paper/1302.2752/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2013.

## Built on by (most cited first, 14 of 14)

- [Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation](https://mlsanity.com/paper/2301.11509/) (2023)
- [Intrinsic Dimension Estimation Using Wasserstein Distances](https://mlsanity.com/paper/2106.04018/) (2021)
- [Covariate balancing using the integral probability metric for causal inference](https://mlsanity.com/paper/2305.13715/) (2023)
- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [Optimal Scalarizations for Sublinear Hypervolume Regret](https://mlsanity.com/paper/2307.03288/) (2023)
- [Near-optimal learning with average H"older smoothness](https://mlsanity.com/paper/2302.06005/) (2023)
- [Trustworthy Actionable Perturbations](https://mlsanity.com/paper/2405.11195/) (2024)
- [Private Evolution Converges](https://mlsanity.com/paper/2506.08312/) (2025)
- [Teacher Guided Training: An Efficient Framework for Knowledge Transfer](https://mlsanity.com/paper/2208.06825/) (2022)
- [Efficient Agnostic Learning with Average Smoothness](https://mlsanity.com/paper/2309.17016/) (2023)
- [Variational Entropic Optimal Transport](https://mlsanity.com/paper/2602.02241/) (2026)
- [Non-Linear Spectral Dimensionality Reduction Under Uncertainty](https://mlsanity.com/paper/2202.04678/) (2022)
- [Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces](https://mlsanity.com/paper/2402.05576/) (2024)
- [Fine-Grained Uncertainty Quantification via Collisions](https://mlsanity.com/paper/2411.12127/) (2024)

## Abstract (arXiv)

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.