# Efficient Classification for Metric Data

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

## Key facts

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

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

- [Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networks](https://mlsanity.com/paper/2104.05097/) (2021)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Fat-Shattering Dimension of k-fold Aggregations](https://mlsanity.com/paper/2110.04763/) (2021)
- [Generalization in Nonlinear Least Squares via Learned Feature Geometry](https://mlsanity.com/paper/2606.08799/) (2026)
- [k-Center Clustering with Outliers in Sliding Windows](https://mlsanity.com/paper/2201.02448/) (2022)
- [Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variables](https://mlsanity.com/paper/2505.19470/) (2025)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [Margin in Abstract Spaces](https://mlsanity.com/paper/2603.07221/) (2026)
- [Realizable Bayes-Consistency for General Metric Losses](https://mlsanity.com/paper/2605.03823/) (2026)
- [On the Geometry of Multimodal Saturation: Riemannian VICReg](https://mlsanity.com/paper/2610.06096/) (2026)

## Abstract (arXiv)

Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as string edit and earthmover distance. A general framework developed for this purpose by von Luxburg and Bousquet [JMLR, 2004] left open the questions of computational efficiency and of providing direct bounds on generalization error. We design a new algorithm for classification in general metric spaces, whose runtime and accuracy depend on the doubling dimension of the data points, and can thus achieve superior classification performance in many common scenarios. The algorithmic core of our approach is an approximate (rather than exact) solution to the classical problems of Lipschitz extension and of Nearest Neighbor Search. The algorithm's generalization performance is guaranteed via the fat-shattering dimension of Lipschitz classifiers, and we present experimental evidence of its superiority to some common kernel methods. As a by-product, we offer a new perspective on the nearest neighbor classifier, which yields significantly sharper risk asymptotics than the classic analysis of Cover and Hart [IEEE Trans. Info. Theory, 1967].