# Generalization analysis with deep ReLU networks for metric and similarity learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 10 May 2024.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Revisiting Training Strategies and Generalization Performance in Deep Metric Learning](https://mlsanity.com/paper/2002.08473/) (2020)
- [Classification with Deep Neural Networks and Logistic Loss](https://mlsanity.com/paper/2307.16792/) (2023)
- [Classification of Data Generated by Gaussian Mixture Models Using Deep ReLU Networks](https://mlsanity.com/paper/2308.08030/) (2023)
- [Guaranteed Classification via Regularized Similarity Learning](https://mlsanity.com/paper/1306.3108/) (2013)
- [Fine-grained Analysis of Non-parametric Estimation for Pairwise Learning](https://mlsanity.com/paper/2305.19640/) (2023)

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

- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Optimization Risk Bounds for Kolmogorov-Arnold Networks Trained by DP-SGD with Correlated Noise](https://mlsanity.com/paper/2605.12648/) (2026)
- [Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning](https://mlsanity.com/paper/2503.01530/) (2025)
- [Metric Learning in an RKHS](https://mlsanity.com/paper/2508.04476/) (2025)

## Abstract (arXiv)

While metric and similarity learning has been extensively studied from several theoretical perspectives, a rigorous understanding of its generalization performance is still lacking. In this paper, we investigate the generalization behavior of metric and similarity learning by exploiting the specific structure of the true metric (i.e., the target function). In particular, by deriving the explicit form of the true metric for metric and similarity learning with the hinge loss, we construct a structured deep ReLU neural network as an approximation of the true metric, whose approximation ability depends on the network complexity. Here, the network complexity is characterized by the network depth, the number of nonzero weights, and the number of computational units. Based on the hypothesis space consisting of such structured deep ReLU networks, we establish excess risk bounds for metric and similarity learning by carefully controlling both the approximation error and the estimation error. An explicit excess risk rate is derived by choosing the proper capacity of the constructed hypothesis space. To the best of our knowledge, this is the first generalization analysis that provides explicit excess risk bounds for metric and similarity learning. In addition, we investigate properties of the true metric for metric and similarity learning under more general loss functions. Experiments show that the proposed model is empirically competitive and better captures the underlying similarity structure.