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

Do, Thanh-Toan ORCID: 0000-0002-6249-0848, Tran, Toan, Reid, Ian, Kumar, Vijay, Hoang, Tuan and Carneiro, Gustavo (2019) A Theoretically Sound Upper Bound on the Triplet Loss for Improving the Efficiency of Deep Distance Metric Learning. In: 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019-6-15 - 2019-6-20.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1109/cvpr.2019.01065

Abstract

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).

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	07 Jun 2019 10:17
Last Modified:	31 Jan 2023 08:32
DOI:	10.1109/CVPR.2019.01065
Open Access URL:	https://arxiv.org/abs/1904.08720
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3042551