mlsanityData to 13 Oct 2026

On the Stability and Generalization of Triplet Learning

arXiv 2302.09815 ↗First posted 20 Feb 2023stat.ML cs.LGcited by 2

Not on the map. Why?

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.

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

Builds on

35 of 92 references.

References · 35

  1. 2015FaceNet: A Unified Embedding for Face Recognition and Clusteringcited by 2,838
  2. 2021Generalizing to Unseen Domains: A Survey on Domain Generalizationcited by 764
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 549
  4. 2021Towards Out-Of-Distribution Generalization: A Surveycited by 432
  5. 2021Accuracy on the Line: On the Strong Correlation Between Out-of-Distribution and In-Distribution Generalizationcited by 249
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  8. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  9. 2018Deep Metric Learning with Hierarchical Triplet Losscited by 112
  10. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  11. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  12. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 95
23 more
  1. 2021Towards a Theoretical Framework of Out-of-Distribution Generalizationcited by 94
  2. 2019Sharper bounds for uniformly stable algorithmscited by 92
  3. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 91
  4. 2019Convergence rates for the stochastic gradient descent method for non-convex objective functionscited by 66
  5. 2015Learning Descriptors for Object Recognition and 3D Pose Estimationcited by 60
  6. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  7. 2015Cross-domain Image Retrieval with a Dual Attribute-aware Ranking Networkcited by 53
  8. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  9. 2016Learning Deep Embeddings with Histogram Losscited by 52
  10. 2021A Theory of Label Propagation for Subpopulation Shiftcited by 48
  11. 2015Simultaneous Feature Learning and Hash Coding with Deep Neural Networkscited by 44
  12. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 42
  13. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  14. 2016Learning Deep Feature Representations with Domain Guided Dropout for Person Re-identificationcited by 41
  15. 2017Algorithmic stability and hypothesis complexitycited by 39
  16. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  17. 2022Minimax Regret Optimization for Robust Machine Learning under Distribution Shiftcited by 31
  18. 2019Hypothesis Set Stability and Generalizationcited by 23
  19. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  20. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  21. 2016Trunk-Branch Ensemble Convolutional Neural Networks for Video-based Face Recognitioncited by 16
  22. 2017Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Boundscited by 15
  23. 2019Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learningcited by 8

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Enhancing Small-Scale Dataset Expansion with Triplet-Connection-based Sample Re-Weightingcited by 1
  2. 2025Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learningcited by 0