# Dimension Free Generalization Bounds for Non Linear Metric Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 7 Feb 2021.

## Builds on (most cited first, 7 of 7)

- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Sample complexity of learning Mahalanobis distance metrics](https://mlsanity.com/paper/1505.02729/) (2015)
- [On the Robustness of Regularized Pairwise Learning Methods Based on Kernels](https://mlsanity.com/paper/1510.03267/) (2015)

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

- [Learning Smooth Distance Functions via Queries](https://mlsanity.com/paper/2412.01290/) (2024)

## Abstract (arXiv)

In this work we study generalization guarantees for the metric learning problem, where the metric is induced by a neural network type embedding of the data. Specifically, we provide uniform generalization bounds for two regimes -- the sparse regime, and a non-sparse regime which we term bounded amplification. The sparse regime bounds correspond to situations where ℓ1-type norms of the parameters are small. Similarly to the situation in classification, solutions satisfying such bounds can be obtained by an appropriate regularization of the problem. On the other hand, unregularized SGD optimization of a metric learning loss typically does not produce sparse solutions. We show that despite this lack of sparsity, by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees. Consequently, these bounds can explain generalization in non sparse real experimental situations. We illustrate the studied phenomena on the MNIST and 20newsgroups datasets.