# Guaranteed Classification via Regularized Similarity Learning

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

## Key facts

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

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

- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Generalization analysis with deep ReLU networks for metric and similarity learning](https://mlsanity.com/paper/2405.06415/) (2024)
- [Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning](https://mlsanity.com/paper/2309.04626/) (2023)

## Abstract (arXiv)

Learning an appropriate (dis)similarity function from the available data is a central problem in machine learning, since the success of many machine learning algorithms critically depends on the choice of a similarity function to compare examples. Despite many approaches for similarity metric learning have been proposed, there is little theoretical study on the links between similarity met- ric learning and the classification performance of the result classifier. In this paper, we propose a regularized similarity learning formulation associated with general matrix-norms, and establish their generalization bounds. We show that the generalization error of the resulting linear separator can be bounded by the derived generalization bound of similarity learning. This shows that a good gen- eralization of the learnt similarity function guarantees a good classification of the resulting linear classifier. Our results extend and improve those obtained by Bellet at al. [3]. Due to the techniques dependent on the notion of uniform stability [6], the bound obtained there holds true only for the Frobenius matrix- norm regularization. Our techniques using the Rademacher complexity [5] and its related Khinchin-type inequality enable us to establish bounds for regularized similarity learning formulations associated with general matrix-norms including sparse L 1 -norm and mixed (2,1)-norm.