# Nearly optimal classification for semimetrics

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

## Key facts

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

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

- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Fast and Multiphase Rates for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2308.08247/) (2023)
- [Optimistic Rates for Multiclass PAC Learning](https://mlsanity.com/paper/2608.10869/) (2026)
- [Transversal Pooling Neural Networks](https://mlsanity.com/paper/2609.36237/) (2026)

## Abstract (arXiv)

We initiate the rigorous study of classification in semimetric spaces, which are point sets with a distance function that is non-negative and symmetric, but need not satisfy the triangle inequality. For metric spaces, the doubling dimension essentially characterizes both the runtime and sample complexity of classification algorithms --- yet we show that this is not the case for semimetrics. Instead, we define the em density dimension and discover that it plays a central role in the statistical and algorithmic feasibility of learning in semimetric spaces. We present nearly optimal sample compression algorithms and use these to obtain generalization guarantees, including fast rates. The latter hold for general sample compression schemes and may be of independent interest.