# A Theoretically Sound Upper Bound on the Triplet Loss for Improving the Efficiency of Deep Distance Metric Learning

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2019.

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

- [On the Unreasonable Effectiveness of Centroids in Image Retrieval](https://mlsanity.com/paper/2104.13643/) (2021)
- [Zero-Shot Learning on 3D Point Cloud Objects and Beyond](https://mlsanity.com/paper/2104.04980/) (2021)
- [Bayesian Learning-driven Prototypical Contrastive Loss for Class-Incremental Learning](https://mlsanity.com/paper/2405.11067/) (2024)
- [Few-Shot Learning with Uncertainty-based Quadruplet Selection for Interference Classification in GNSS Data](https://mlsanity.com/paper/2402.09466/) (2024)
- [N-pad : Neighboring Pixel-based Industrial Anomaly Detection](https://mlsanity.com/paper/2210.08768/) (2022)
- [Introspective Deep Metric Learning](https://mlsanity.com/paper/2309.09982/) (2023)
- [Auxiliary Cross-Modal Representation Learning with Triplet Loss Functions for Online Handwriting Recognition](https://mlsanity.com/paper/2202.07901/) (2022)
- [Sports Re-ID: Improving Re-Identification Of Players In Broadcast Videos Of Team Sports](https://mlsanity.com/paper/2206.02373/) (2022)
- [Frequency-Semantic Enhanced Variational Autoencoder for Zero-Shot Skeleton-based Action Recognition](https://mlsanity.com/paper/2506.22179/) (2025)
- [Magnification Generalization for Histopathology Image Embedding](https://mlsanity.com/paper/2101.07757/) (2021)
- [NPT-Loss: A Metric Loss with Implicit Mining for Face Recognition](https://mlsanity.com/paper/2103.03503/) (2021)
- [Atlas Based Representation and Metric Learning on Manifolds](https://mlsanity.com/paper/2106.07062/) (2021)
- [Deep Metric Learning with Chance Constraints](https://mlsanity.com/paper/2209.09060/) (2022)
- [Deep Simplex Classifier for Maximizing the Margin in Both Euclidean and Angular Spaces](https://mlsanity.com/paper/2212.11747/) (2022)
- [Graph Your Own Prompt](https://mlsanity.com/paper/2509.23373/) (2025)
- [Reshaping the Forward-Forward Algorithm with a Similarity-Based Objective](https://mlsanity.com/paper/2509.08697/) (2025)
- [Improving Image co-segmentation via Deep Metric Learning](https://mlsanity.com/paper/2103.10670/) (2021)
- [Introspective Deep Metric Learning for Image Retrieval](https://mlsanity.com/paper/2205.04449/) (2022)
- [Representation Learning for Tablet and Paper Domain Adaptation in Favor of Online Handwriting Recognition](https://mlsanity.com/paper/2301.06293/) (2023)
- [Shadow loss: Memory-linear deep metric learning for efficient training](https://mlsanity.com/paper/2311.14012/) (2023)
- [I2CKD : Intra- and Inter-Class Knowledge Distillation for Semantic Segmentation](https://mlsanity.com/paper/2403.18490/) (2024)
- [Context-Aware Siamese Networks for Efficient Emotion Recognition in Conversation](https://mlsanity.com/paper/2404.11141/) (2024)
- [Semantic-Enhanced Relational Metric Learning for Recommender Systems](https://mlsanity.com/paper/2406.10246/) (2024)
- [Maintaining Difficulty: A Margin Scheduler for Triplet Loss in Siamese Networks Training](https://mlsanity.com/paper/2603.26389/) (2026)
- [SeCo-SBIR: Semantically Consistent Prompt Learning for Zero-Shot Sketch-Based Image Retrieval](https://mlsanity.com/paper/2608.03120/) (2026)

## Abstract (arXiv)

We propose a method that substantially improves the efficiency of deep distance metric learning based on the optimization of the triplet loss function. One epoch of such training process based on a naive optimization of the triplet loss function has a run-time complexity O(N^3), where N is the number of training samples. Such optimization scales poorly, and the most common approach proposed to address this high complexity issue is based on sub-sampling the set of triplets needed for the training process. Another approach explored in the field relies on an ad-hoc linearization (in terms of N) of the triplet loss that introduces class centroids, which must be optimized using the whole training set for each mini-batch - this means that a naive implementation of this approach has run-time complexity O(N^2). This complexity issue is usually mitigated with poor, but computationally cheap, approximate centroid optimization methods. In this paper, we first propose a solid theory on the linearization of the triplet loss with the use of class centroids, where the main conclusion is that our new linear loss represents a tight upper-bound to the triplet loss. Furthermore, based on the theory above, we propose a training algorithm that no longer requires the centroid optimization step, which means that our approach is the first in the field with a guaranteed linear run-time complexity. We show that the training of deep distance metric learning methods using the proposed upper-bound is substantially faster than triplet-based methods, while producing competitive retrieval accuracy results on benchmark datasets (CUB-200-2011 and CAR196).