# Sample complexity of learning Mahalanobis distance metrics

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2015.

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

- [Optimal Sample Complexity of Contrastive Learning](https://mlsanity.com/paper/2312.00379/) (2023)
- [Metric Learning from Limited Pairwise Preference Comparisons](https://mlsanity.com/paper/2403.19629/) (2024)
- [Dimension Free Generalization Bounds for Non Linear Metric Learning](https://mlsanity.com/paper/2102.03802/) (2021)
- [Learning Rates for Nonconvex Pairwise Learning](https://mlsanity.com/paper/2111.05232/) (2021)
- [Compressive Mahalanobis Metric Learning Adapts to Intrinsic Dimension](https://mlsanity.com/paper/2309.05751/) (2023)
- [Towards Efficient Contrastive PAC Learning](https://mlsanity.com/paper/2502.15962/) (2025)
- [Metric Learning in an RKHS](https://mlsanity.com/paper/2508.04476/) (2025)

## Abstract (arXiv)

Metric learning seeks a transformation of the feature space that enhances prediction quality for the given task at hand. In this work we provide PAC-style sample complexity rates for supervised metric learning. We give matching lower- and upper-bounds showing that the sample complexity scales with the representation dimension when no assumptions are made about the underlying data distribution. However, by leveraging the structure of the data distribution, we show that one can achieve rates that are fine-tuned to a specific notion of intrinsic complexity for a given dataset. Our analysis reveals that augmenting the metric learning optimization criterion with a simple norm-based regularization can help adapt to a dataset's intrinsic complexity, yielding better generalization. Experiments on benchmark datasets validate our analysis and show that regularizing the metric can help discern the signal even when the data contains high amounts of noise.