# On the Stability and Generalization of Triplet Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 92 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 30 of 35)

- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Generalizing to Unseen Domains: A Survey on Domain Generalization](https://mlsanity.com/paper/2103.03097/) (2021)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [Accuracy on the Line: On the Strong Correlation Between Out-of-Distribution and In-Distribution Generalization](https://mlsanity.com/paper/2107.04649/) (2021)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Deep Metric Learning with Hierarchical Triplet Loss](https://mlsanity.com/paper/1810.06951/) (2018)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Towards a Theoretical Framework of Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.04496/) (2021)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Convergence rates for the stochastic gradient descent method for non-convex objective functions](https://mlsanity.com/paper/1904.01517/) (2019)
- [Learning Descriptors for Object Recognition and 3D Pose Estimation](https://mlsanity.com/paper/1502.05908/) (2015)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Cross-domain Image Retrieval with a Dual Attribute-aware Ranking Network](https://mlsanity.com/paper/1505.07922/) (2015)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Learning Deep Embeddings with Histogram Loss](https://mlsanity.com/paper/1611.00822/) (2016)
- [A Theory of Label Propagation for Subpopulation Shift](https://mlsanity.com/paper/2102.11203/) (2021)
- [Simultaneous Feature Learning and Hash Coding with Deep Neural Networks](https://mlsanity.com/paper/1504.03410/) (2015)
- [Toward Better Generalization Bounds with Locally Elastic Stability](https://mlsanity.com/paper/2010.13988/) (2020)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Learning Deep Feature Representations with Domain Guided Dropout for Person Re-identification](https://mlsanity.com/paper/1604.07528/) (2016)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Minimax Regret Optimization for Robust Machine Learning under Distribution Shift](https://mlsanity.com/paper/2202.05436/) (2022)
- [Hypothesis Set Stability and Generalization](https://mlsanity.com/paper/1904.04755/) (2019)

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

- [Enhancing Small-Scale Dataset Expansion with Triplet-Connection-based Sample Re-Weighting](https://mlsanity.com/paper/2508.07723/) (2025)
- [Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning](https://mlsanity.com/paper/2503.01530/) (2025)

## Abstract (arXiv)

Triplet learning, i.e. learning from triplet data, has attracted much attention in computer vision tasks with an extremely large number of categories, e.g., face recognition and person re-identification. Albeit with rapid progress in designing and applying triplet learning algorithms, there is a lacking study on the theoretical understanding of their generalization performance. To fill this gap, this paper investigates the generalization guarantees of triplet learning by leveraging the stability analysis. Specifically, we establish the first general high-probability generalization bound for the triplet learning algorithm satisfying the uniform stability, and then obtain the excess risk bounds of the order O(n^-frac12 logn) for both stochastic gradient descent (SGD) and regularized risk minimization (RRM), where 2n is approximately equal to the number of training samples. Moreover, an optimistic generalization bound in expectation as fast as O(n-1) is derived for RRM in a low noise case via the on-average stability analysis. Finally, our results are applied to triplet metric learning to characterize its theoretical underpinning.