Robust and Decomposable Average Precision for Image Retrieval
Year: 2022

Abstract:
In image retrieval, standard evaluation metrics rely on score ranking, e.g. average precision (AP). In this paper, we introduce a method for robust and decomposable average precision (ROADMAP) addressing two major challenges for end-to-end training of deep neural networks with AP: non-differentiability and non-decomposability. Firstly, we propose a new differentiable approximation of the rank function, which provides an upper bound of the AP loss and ensures robust training. Secondly, we design a simple yet effective loss function to reduce the decomposability gap between the AP in the whole training set and its averaged batch approximation, for which we provide theoretical guarantees. Extensive experiments conducted on three image retrieval datasets show that ROADMAP outperforms several recent AP approximation methods and highlight the importance of our two contributions. Finally, using ROADMAP for training deep models yields very good performances, outperforming state-of-the-art results on the three datasets. Code and instructions to reproduce our results will be made publicly available at https://github.com/elias-ramzi/ROADMAP.

heading: 1 Introduction
text: The task of ‘query by example’ is a major prediction problem, which consists in learning a similarity function able to properly rank all the instances in a retrieval set according to their relevance to the query, such that relevant items have the largest similarity. In computer vision, it drives several major applications, e.g. content-based image retrieval, face recognition or person re-identification.
Such tasks are usually evaluated with rank-based metrics, e.g. Recall@k, Normalized Discounted Cumulative Gain (NDCG), and Average Precision (AP). AP is also the de facto metric used in several vision tasks implying a large imbalance between positive and negative samples, e.g. object detection.
In this paper, we address the problem of direct AP training with stochastic gradient-based optimization, e.g. using deep neural networks, which poses two major challenges.
Firstly, the AP loss LAP = 1− AP is not differentiable and is thus not directly amenable to gradientbased optimization. There has been a rich literature for providing smooth and upper bound surrogate
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
losses for LAP [43, 21, 22, 6, 25]. More recently, smooth differentiable rank approximations have been proposed [35, 14, 15, 3, 27, 8, 2], but generally lose the important LAP upper bound property. The second important issue of AP optimization relates to its non-decomposability: LBAP averaged over batches underestimates LAP on the whole training dataset, which we refer as the decomposability gap. In image retrieval, the attempts to circumvent the problem involve ad hoc methods based on batch sampling strategies [10, 32, 20, 32, 30], or storing all training representations/scores [39, 3, 27, 25], leading to complex models with a large computation and memory overhead.
In this paper, we introduce a method for RObust And DecoMposable Average Precision (ROADMAP), which explicitly addresses the aforementioned challenges of AP optimization.
Our first contribution is to propose a new surrogate loss LSupAP for LAP. In particular, we introduce a smooth approximation of the rank function, with a different behaviour for positive and negative examples. By this design, LSupAP provides an upper bound of LAP, and always back-propagates gradients when the correct ranking is not satisfied. These two features illustrated in the the toy example on Figure 1a are not fulfilled by binning approaches [3, 27] or by SmoothAP [2].
As a second contribution, we propose to improve the non-decomposability in AP training. To this end, we introduce a simple yet effective training objective Lcalibr., which calibrates the scores among different batches by controlling the absolute value of positive and negative samples. We provide a theoretical analysis showing that Lcalibr. decreases the decomposability gap. Figure 1 illustrates how Lcalibr. can be leveraged to improve the overall ranking. We provide a thorough experimental validation including three standard image retrieval datasets and show that ROADMAP outperforms state-of-the-art methods. We also report the large and consistent gain compared to rank/AP approximation baselines, and we highlight in the ablation studies the importance of our two contributions. Finally, ROADMAP does not entail any memory or computation overhead and remains competitive even with small batches.

heading: 2 Related work
text: We discuss here the literature in image retrieval dedicated to AP optimization, and compare to other approaches based on optimizing representations [23, 1, 44, 46, 33] in the experiments.
Smooth AP approximations Studying smooth surrogate losses for AP has a long history. The widely used surrogate for retrieval is to consider constraints based on pairs [41, 12, 26], triplets [11], quadruplets [18] or n-uplets [30] to enforce partial ranking. These metric learning methods optimize a very coarse upper bound on AP and need complex post-processing and tricks to be effective.
One option for training with AP is to design smooth upper bounds on the AP loss. Seminal works are based on structural SVMs [43, 21], with extensions to speed-up the "loss-augmented inference" [22] or to adapt to weak supervision [6]. Recently, a generic blackbox combinatorial solver has been introduced [25] and applied to AP optimization [28]. To overcome the brittleness of AP with respect to
small score variations, an ad hoc perturbation is applied to positive and negative scores during training. These methods provide elegant AP upper bounds, but generally are coarse AP approximations.
Other approaches rely on designing smooth approximations of the the rank function. This is done in soft-binning techniques [14, 15, 35, 3, 27] by using a smoothed discretization of similarity scores. Other approaches rely on explicitly approximating the non-differentiable rank functions using neural networks [8], or with a sum of sigmoid functions in the recent SmoothAP approach [2]. These approaches enable accurate AP approximations by providing tight and smooth approximations of the rank function. However, they do not guarantee that the resulting loss is an AP loss upper bound. The LSupAP introduced in this work is based on a smooth approximation of the rank function leading to an upper bound on the AP loss, making our approach both accurate and robust.
Decomposability in AP optimization Batch training is mandatory in deep learning. However, the non-decomposability of AP is a severe issue, since it yields an inconsistent AP gradient estimator.
Non-decomposability is related to sampling informative constraints in simple AP surrogates, e.g. triplet losses, since the constraints’ cardinality on the whole training set is prohibitive. This has been addressed by efficient batch sampling [13, 10, 32] or selecting informative constraints within mini-batches [30, 9, 4, 32]. In cross-batch memory technique [39], the authors assume a slow drift in learned representations to store them and compute global mining in pair-based deep metric learning.
In AP optimization, the non-decomposability has essentially been addressed by a brute force increase of the batch size [3, 27, 25]. This includes an important overhead in computation and memory, generally involving a two-step approach for first computing the AP loss and subsequently re-computing activations and back-propagating gradients. In contrast, our loss Lcalibr. does not add any overhead and enables good performances for AP optimization even with small batches.

heading: 3 Robust and decomposable AP training
text: We present here our method for RObust And DecoMposable AP (ROADMAP) dedicated to direct optimization of a smooth surrogate of AP with stochastic gradient descent (SGD), see Fig. 2.
Training context Let us consider a retrieval set Ω = {xj}j∈J1;NK composed of N elements, and a set of M queries included in Ω, i.e. Q = {qi}i∈J1;MK ⊆ Ω. For each query qi, each element in Ω is assigned a label y(xj , qi) ∈ {+1;−1}, such that y(xj , qi) = 1 (resp. y(xj , qi) = −1) if xj is relevant (resp. irrelevant) with respect to qi. This defines a query-dependent partitioning of Ω such that Ω = Pi ∪Ni, where Pi := {xj ∈ Ω|y(xj , qi) = +1} and Ni := {xj ∈ Ω|y(xj , qi) = −1}. For each xj ∈ Ω, we define a prediction model parametrized by parameters θ, e.g. a deep neural network, which provides a vectorial embedding vqi ∈ Rd of each element, i.e.: vqi := fθ(qi). In the embedded space Rd, we compute a similarity score between each query qi and each element in Ω, e.g. by using the cosine similarity: s(qi,xj) = vqi Tvj
||vqi ||2||vj||2 .
During training, our goal is to optimize, for each query qi, the model parameters θ such that positive elements are ranked before negatives. More precisely, we aim at minimizing the AP loss LAPi for each query qi in the retrieval set Ω. Our overall AP loss LAP is averaged over all queries:
LAP(θ) = 1− 1
M M∑ i=1 APi(θ), APi(θ) = 1 |Pi| ∑ k∈Pi Pre(k, θ) = 1 |Pi| ∑ k∈Pi rank+(k, θ) rank(k, θ) (1)
where Pre(k, θ) is the precision for the kth positive example xk, rank+(k, θ) its rank among positives Pi, and the rank(k, θ) its rank over Ω = Pi ∪Ni. As previously mentioned, there are two main challenges with SGD optimization of AP in Eq. (1): i) AP(θ) is not differentiable with respect to θ, and ii) AP does not linearly decompose into batches. ROADMAP addresses both issues: we introduce the robust differentiable LSupAP surrogate (Section 3.1), and add the Lcalibr. loss (Section 3.2) to improve AP decomposability. Our final loss LROADMAP is a linear combination of LSupAP and Lcalibr., weighted by the hyperparameter λ:
LROADMAP(θ) = (1− λ) · LSupAP(θ) + λ · Lcalibr.(θ) (2)

heading: 3.1 Robustness in smooth rank approximation
text: The non-differentiablity in Eq (1) comes from the ranking operator, which can be viewed as counting the number of instances that have a similarity score greater than the considered instance, i.e.1:
rank+(k) = 1 + ∑
j∈Pi\{k}
H(sj − sk), where H(t) = {
1 if t ≥ 0 0 otherwise
rank(k) = rank+(k) + ∑ j∈Ni H(sj − sk) = rank+(k) + rank−(k) (3)
From Eq. (3) it becomes clear that the non-differentiablity is due to the Heaviside (step) function H , whose derivative is either zero or undefined. Note that the computation of rank+(k) and rank−(k) in Eq. (3) relates to the rank of positive instances xk ∈ Pi: the score sk in Eq. (3) is always the score of a positive, whereas sj can either be a negative’s or positive’s score.
Smooth loss LSupAP To provide a smooth approximation of LAP in Eq. (1), we introduce a smooth approximation of the rank function. In particular, we propose a different behaviour between rank+(k) and rank−(k) in Eq. (3) by defining two functions H+ and H−.
For rank+(k), we choose to keep the Heaviside (step) function, i.e. H+ = H (see Fig. 3a), which consists in ignoring rank+(k) in gradient-based AP optimization. This is done on purpose since ∂AP
∂ rank+(k) = rank −(k) (rank+(k)+rank−(k))2
≥ 0: the gradient would tend to increase rank+(k) and to decrease the score of sk. Reminding xk is always a positive instance, this behaviour is undesirable.
For rank−(k), we define the following smooth surrogate H− for H , shown in Fig 3b:
H−(t) =  σ( tτ ) if t ≤ 0, where σ is the sigmoid function (Fig. 3c) σ( tτ ) + 0.5 if t ∈ [0; δ] with δ ≥ 0 ρ · (t− δ) + σ( δτ ) + 0.5 if t > δ
(4)
where τ and ρ are hyperparameters, and δ is defined such that the sigmoidal part of H− reaches the saturation regime and is fixed for the rest of the paper (see supplementary Sec. A). From
1For the sake of readability we drop in the following the dependence on θ for the rank, i.e. rank(k) := rank(k, θ) and on the query for the similarity, i.e. sj := s(qi, xj).
the H− smooth approximation defined in Eq. (4), we obtain the following smooth approximation rank−s (k) = ∑ j∈Ni H−(sj − sk), leading to the following smooth AP loss approximation:
LSupAP(θ) = 1− 1
M M∑ i=1 1 |Pi| ∑ k∈Pi
rank+(k)
rank+(k) + rank−s (k) (5)
LSupAP in Eq. (5) fulfills two main features for AP optimization: I 1 LSupAP is an upper bound of LAP in Eq. (1). Since H− in Eq. (4) is an upper bound of a step function (Fig 3b), it is easy to see that LSupAP ≥ LAP. This is a very important property, since it ensures that the model keeps training until the correct ranking is obtained. It is worth noting that existing smooth rank approximations in the literature [35, 3, 27, 2] do not fulfill this property.
I 2 LSupAP brings training gradients until the correct ranking plus a margin is fulfilled. When the ranking is incorrect, the negative xj is ranked before the positive xk, thus sj > sk and H−(sj − sk) in Eq. (4) has a non-null derivative. We use a sigmoid to have a large gradient when sj − sk is small. To overcome vanishing gradients of the sigmoid for large values sj − sk, we use a linear function ensuring constant ρ derivative. When the ranking is correct (sj < sk), we enforce robustness by imposing a margin parametrized by τ (sigmoid in Eq. (4)). This margin overcomes the brittleness of rank losses, which vanish as soon as the ranking is correct [14, 3, 25].
Comparison to SmoothAP [2] LSupAP differs from LSmoothAP in [2] by i) providing an upper bound on LAP, ii) improving the gradient flow (Fig. 3b vs Fig. 3c), and iii) overcoming adverse effects of the sigmoid for rank+, as shown in Fig. 1a (and in supplementary sec. A). We experimentally verify the consistent gain brought out by LSupAP over LSmoothAP.

heading: 3.2 Decomposable Average Precision
text: In Eq. (1), AP decomposes linearly between queries qi, but APi does not decomposes linearly between samples. We therefore focus our analysis of the non-decomposability on a single query. For a retrieval set Ω of N elements, we consider {Bb}b∈{1:K} batches of size B, such that N/B = K ∈ N. Let APbi (θ) be the AP in batch b for query qi, we define the "decomposability gap" DGAP as follows:
DGAP(θ) = 1
K K∑ b=1 APbi (θ)− APi(θ) (6)
DGAP in Eq. (6) is a direct measure of the non-decomposability of AP (see supplementary Sec. A). Our motivation here is to decrease DGAP, i.e. to have the average AP over the batches as close as possible to the AP computed over the whole training set. To this aim, we introduce the following loss
during training:
Lcalibr.(θ) = 1
M M∑ i=1 1 |Pi| ∑ xj∈Pi
[α− sj ]+︸ ︷︷ ︸ L+calibr.
+ 1 |Ni| ∑ xj∈Ni
[sj − β]+︸ ︷︷ ︸ L−calibr.
(7)
where [x]+ = max(0, x). The loss L+calibr. enforces the score of the positive xi ∈ Pi to be larger than α, and L−calibr. enforces the score of the negative xj ∈ Ni to be smaller than β < α. Lcalibr. is a standard pair-based loss [12], which we revisit in our context to "calibrate" the values of the scores between mini-batches: intuitively, the fact that the positive (resp. negative) scores are above (resp. below) a threshold in the mini-batches makes the average AP closer to the AP on the whole dataset.
Upper bound on the decomposabilty gap To formalize this idea, we provide a theoretical analysis of the impact on the global ranking of Lcalibr. in Eq. (7). Firstly, we can see that if L−calibr. = L + calibr. = 0, on each batch, the overall AP and the AP in batches is null, i.e. DGAP(θ) = 0 and we get a decomposable AP. In a more general setting, we show that minimizing Lcalibr. on each batch reduces the decomposability gap, hence improving the decomposability of the AP.
Let’s consider K batches {Bb}b∈{1:K} of batch size B divided in Pbi positive instances and N bi negative instances w.r.t. the query qi. To give some insight we assume that the AP of each batch is one (i.e. AP bi = 1), and give the following upper bound of DGAP :
0 ≤ DGAP ≤ 1− 1∑K
b=1 |Pbi |  K∑ b=1 B∑ j=1
j + |P1i |+ · · ·+ |P b−1 i |
j + |P1i |+ · · ·+ |P b−1 i |+ |N 1i |+ · · ·+ |N b−1 i |  (8) This upper bound of the decomposability gap is given in the worst case for the global AP : the global ranking is built from the juxtaposition of the batches (see supplementary Sec. A).
We can refine this upper bound by introducing the calibration lossLcalibr. and constraining the scores of positive and negative instances to be well calibrated. On each batch we define the following quantities E−b = ∑ j∈N−i
1(sj > β) which are the negative instances that do not respect the constraints and G−b = ∑ j∈N−i 1(sj ≤ β) the negative instances that do. We similarly define E+b and G + b . We then have the following upper bound on the decomposability gap :
0 ≤ DGAP ≤ 1− 1∑K
b=1 |Pbi | ( K∑ b=1 [ G+b∑ j=1
j +G+1 + · · ·+G + b−1
j +G+1 + · · ·+G + b−1 + E − 1 + . . . E − b−1
+ (9)
E+b∑ j=1
j +G+b + |P1i |+ · · ·+ |P b−1 i |
j +G+b + |P1i |+ · · ·+ |P b−1 i |+ |N 1i |+ · · ·+ |N b−1 i |
])
This refined upper bound is tighter than the upper bound of Eq. (8). Our new Lcalibr. loss directly optimizes this upper bound (by explicitly optimizing E−b , E + b , E + b , G + b ), making it tighter, hence improving the decomposability of the AP (see supplementary Sec. A).

heading: 4 Experiments
text: Experimental setup We evaluate ROADMAP on the following three image retrieval datasets: CUB-200-2011 [37] contains 11 788 images of birds classified into 200 fine-grained classes. We follow the standard protocol and use the first (resp. last) 100 classes for training (resp. evaluation). Stanford Online Product (SOP) [31] is a dataset with 120 053 images of 22 634 objects classified into 12 categories (e.g. bikes, coffee makers). We use the reference train and test splits from [31]. INaturalist-2018 [36] is a large scale dataset of 461 939 wildlife animals images classified into 8142 classes. We use the splits from [2] with 70% of the classes in the train set and the rest in the test set.
ROADMAP settings For all experiments in Section 4.1 and Section 4.2, we use λ = 0.5 for LROADMAP in Eq. (2), τ = 0.01 and ρ = 100 for LSupAP in Eq. (5), α = 0.9 and β = 0.6 for Lcalibr.
in Eq. (7). We study more in depth the impact of those parameters in Section 4.3. Deep models are trained using Adam [17] for ResNet-50 backbones and AdamW [19] for DeiT transformers [34]. Test protocol Methods are evaluated using the standard recall at k (R@k) and mean average precision at R [24] (mAP@R) metrics (see supplementary Sec. B).

heading: 4.1 ROADMAP validation
text: In this section, all models are trained in the same setting (ResNet-50 backbone, embedding size 512, batch size 64). The comparisons thus directly measures the impact of the training loss.
Comparison to AP approximations. In Table 1, we compare ROADMAP on the three datasets to recent AP loss approximations including the soft-binning approaches FastAP [3] and SoftBinAP [27], the generic solver BlackBox [28], and the smooth rank approximation [2]. We use the publicly available PyTorch implementations of all these baselines. We can see that ROADMAP outperforms all the current AP approximations by a large margin. The gain is especially pronounced on the large scale dataset INaturalist. This highlights the importance our two contributions, i.e. our robust smooth AP upper bound and our AP decomposability improvement (see supplementary Sec. B).
Comparison to memory methods.
XBM stores the embeddings of previously seen batches to alleviate complex batch sampling and better approximate AP on the whole dataset. Although XBM has a low memory overhead (a few hundreds megabytes on SOP), it is time consuming. We ran experiments storing the entire dataset for SOP (60k embeddings), but for INaturalist we could not train while storing all the dataset in tractable time. We chose to store the same amount of embeddings as for SOP : 60k embeddings which is about 17% of the training set.
We can see in Table 2 that XBM is approximately 3 times longer to train than ROADMAP. This becomes critical on INaturalist, where training while storing 60k images takes about 3 days, and reaches only a R@1 of 60. Consequently, ROADMAP outperforms XBM on both datasets; there is a ∼+2pt increase on both metrics for SOP and an especially large gap on INaturalist. In the latter, not being able to store all the embeddings affects drastically the performances of the XBM in a negative way. There is a 5pt difference in R@1 and more than 6pt in mAP@R. This demonstrates the suitability of ROADMAP on large-scale settings.
Ablation study. To study more in depth the impact of our contributions, we perform ablation studies in Table 3. We show the improvement against SmoothAP [2] when changing the sigmoid by H+ and H− for LSupAP in Eq. (5), and the use of Lcalibr. in Eq. (7). We can see that LSupAP consistently improves performances over LSmoothAP (0.9pt on CUB, 0.5pt on SOP and 1.5pt on INaturalist). LSupAP and Lcalibr. equally contribute to the overall gain in CUB and SOP, but the gain of Lcalibr. is much
more important on INaturalist. This is explained by the fact that the batch vs. dataset ratio size BN is tiny ( 1), making the decomposability gap in Eq. (6) huge. We can see that Lcalibr. is very effective for reducing this gap and brings a gain of more than 3pt.

heading: 4.2 State of the art comparison
text: We compare ROADMAP to other state of the art methods across three image retrieval datasets and report the results in Table 4. We divide competitor methods into three categories: metric learning [29, 38, 45, 16, 39, 42], classification losses for image retrieval [46, 44, 1, 33], and AP approximations [3, 28, 2]. ROADMAP falls in the latter category. We use the same setup as in Section 4.1 and follow standard practices for ResNet-50 [33, 42, 1] by using larger images (256× 256 on SOP and CUB) and using max instead of average pooling and layer normalization for CUB.
Using the popular ResNet-50 backbone, ROADMAP establishes a new state of the art across all methods for SOP and the challenging INaturalist dataset and outperforms all previous AP approximations on CUB, while being competitive with the other two top performers (ProxyNCA++ and SEC). R@k improvements are consistent on all datasets with a ∼2pts R@1 increase on INaturalist and ∼3pts increase on SOP compared to SmoothAP, the best performing AP approximation from the literature.
Switching the backbone to the more recent vision transformer architecture DeiT [5, 34], further lifts the performances of ROADMAP by several point, from 3 to 9 points depending on the dataset, with a smaller embedding size (384 vs 512). The decomposable AP approximation ROADMAP also outperforms by a significant margin IRTR, the DeiT architecture for image retrieval introduced in [7] trained with a contrastive loss. Overall ROADMAP achieves state-of-the-art performances across all three datasets by a significant margin.

heading: 4.3 Model Analysis
text: We show in Fig. 4 the impact of the main ROADMAP hyperparameters on INaturalist. The relative weighting λ from Eq. (2) controls the balance between our two training objectives LSupAP and Lcalibr.: λ = 0 reduces LROADMAP to LSupAP while λ = 1 to Lcalibr.. We can see in Fig. 4a that training with the complete LROADMAP with both Lcalibr. and LSupAP is always better than using only one of the two losses. Note that results are stable in the [0.2, 0.8] range with a consistent ∼1.5pt increase, demonstrating the robustness of ROADMAP to this hyperparameter tuning.
Fig. 4b shows the influence of the slope ρ that controls the linear regime in H− and determines the amount of gradient backpropagated for negative samples with a (wrong) high score. As shown in
Fig. 4b, the improvement is important and stable in [10, 100]. Note that ρ > 0 already improves the results compared to ρ = 0 in [2]. There is an important decrease when ρ 100 probably due to the high gradient that takes over the signal for correctly ranked samples. The impact of the margin α− β in Lcalibr. is shown in Fig. 4c. Once again, ROADMAP exhibits a robust behaviour w.r.t. the values of its hyperparameters: any margin in the [0.1, 0.6] range results in an improvement in mAP@R compared to the LSupAP baseline without the decomposability loss. Best results are achieved with smaller margins 0.1 < α− β < 0.4. Fig. 5 shows the improvement in mAP@R on the three datasets when adding Lcalibr. to LSupAP. We can see that the increase becomes larger as the batch size gets smaller. This confirms our intuition that the decomposability in Lcalibr. has a stronger effect on smaller batch sizes, for which the AP estimation is noisier and DGAP larger. This is critical on the large-scale dataset INaturalist where the batch AP on usual batch sizes is a very poor approximation of the global AP.
As a qualitative assessment, we show in Fig. 6 some results of ROADMAP on INaturalist. We show the queries (in purple) and the 4 most similar retrieved images (in green). We can appreciate the semantic quality of the retrieval. More qualitative results are provided in supplementary Sec. C.
Fig. 7 shows another qualitative assessment on INaturalist, where ROADMAP corrects some failing cases of the SmoothAP baseline.

heading: 5 Conclusion
text: This paper introduces the ROADMAP method for gradient-based optimization of average precision. ROADMAP is based on a smooth rank approximation, leading to the LSupAP being both accurate and robust. To overcome the lack of decomposability in AP, ROADMAP is equipped with a calibration lossLcalibr. which aims at reducing the decomposability gap. We provide theoretical guarantees as well as experiments to assess this behavior. Experiments show that ROADMAP can combine the strength of ranking methods with the simplicity of a batch strategy. Without bells and whistles, ROADMAP is able to outperform state-of-the-art performances on three datasets, and remains effective even with small batch sizes.
As any work on image retrieval, our contribution could be applied to critical applications in surveillance scenarios, e.g. face recognition or person re-identification. ROADMAP is neither worse nor better than previous work in this regard. Our work is also a data-driven learning method, and thus inherits the risk of perpetuating dataset biases. Future work will focus on improving fair and accurate retrieval by reducing dataset biases. We also plan to relax the need for full supervision to tackle situations more representative to in-the-wild scenarios.
Acknowledgement This work was done under a grant from the the AHEAD ANR program (ANR20-THIA-0002). It was granted access to the HPC resources of IDRIS under the allocation 2021- AD011012645 made by GENCI.

Review summaries:
This work tackles the problem of large-scale fine-grained image retrieval by proposing ROADMAP, short for ROBust And DecoMposable Average Precision which is a loss function that consists of two components 1) A smooth approximation to the non-differentiable average precision (AP) loss which provides an upper bound and better gradient flow compared to existing variants of the loss. 2) A calibration component which tackles the problem of mismatch between in-batch and true AP values commonly seen in previous methods.  The authors provided thorough theoretical proofs to support their claims on the proposed loss. Experimental results show consistent and significant improvements over existing methods in various categories, and gives state-of-the-art (SotA) performance among AP-loss based methods across three large-scale image (object) retrieval benchmarks. 

The paper focuses on the problem of learning to rank. The paper proposes a method, ROADMAP (RObust And DecoMposable Average Precision), consisting of two main contributions: - A new surrogate loss for average precision (AP). This loss is similar to recent losses that try to  provide a smooth approximation of AP / rank functions, but has some favorable design choices that lead to empirical improvements. - A "calibration" loss (essentially a classification loss), to be used together with the AP loss, that implicitly provides consistency between batches and facilitates training on small batches. Evaluation shows improvements with respect to recent AP approximations (e.g. [2, 3, 27]) on standard benchmarks.

This paper proposes a new method for deep image retrieval. The main contribution is a differentiable and decomposable loss function based on average precision loss. The method shows superior performance and the theoretical seems correct.

The paper proposes a new loss for image retrieval based on average precision.   Importantly, this paper proposes to address the problem in using AP using batches, which is not equivalent to the true AP computed in the whole dataset (which they refer to as 'non-decomposability'). It also proposes an improvement over other soft-binning approaches in which the version described in the paper is a proper upper-bound on the AP.  The paper lists as contributions: 1) a new surrogate loss for AP-loss that works by introducing a smooth approximation of the rank function with a different behavior for positive and negative examples, 2) improving the 'non-decomposability' problem associated with other AP-loss approximations, 3) experimental validation on CUB, SOP, and iNaturalist, showing state-of-the-art results.