Robust and Decomposable Average Precision for Image Retrieval
Authors: Elias Ramzi
Nicolas THOME
Clément Rambour
Nicolas Audebert
Xavier Bitot
Venue: NeurIPS 2021 Poster (2021)
Keywords: Image Retrieval
Deep Learning
Average Precision
Ranking
Differentiability
Decomposability

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.

clement rrambour@cna fr Robust and Decomposable Average Precision for Image Retrieval
Elias Ramzi 1.2 elias ramzi @cnam. fr xavier. bitot@coezya.eu
Nicolas Thome' nicolas. thome@cnam. fr
Clément Rambour!
Nicolas Audebert nicolas soddebertecnane fr
Xavier Bitot
'CDRIC, Conservatoire National des Arts et Métiers, Paris, France =Coexya, Paris, France
Abstract
In image retrieval, standard evaluation metrics rely score ranking, e.g. av- erage precision (AP). In this paper, we introduce a method for robust and de- composable average precision (ROADMAP) addressing two major challenges for end-to-end training of deep neural networks with AP: con-differentiabiliyy 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 simple yet effective loss function to reduce the de- composability gap between AP the whole training set and averaged batch approximation, for which 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 htttps://gitani http://gttttbb.. www. www.eccaaaaaaeeeeeoooe elias wwaaii/ROAaaa
Introduction
The task of "query by example' is major prediction problem, which consists in learning a similarity function able to properly rank all the instances in 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. basten image retrieval, face recognition or person re-identification.
Such tasks are usually evaluated with bank- 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 AP differentiable and thus not directly amenable gradient- based optimization. There has been a rich literature for providing smooth and upper bound surrogate
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Car
CAP >
0.76 0.77
6.9
B
Dogas - 0.66
LAP
Lealtbr. 2
V=d
+
Caamtaa 6:35
V
(a) LsupA 2 LAP and V SupAP > O in this example, in contrast to SmoothAP 2 This training and comes from new approximation of rank function.
(b) Lap non-decomposability CAp = On all batches B' despite LAP * 0 the whole U, B' Calibe controls the absolute scores between batches, such that LROADMAP + 0 in each batch.
robust
Our robust and decomposable Average Precision training (ROADMAP) includes (a) smooth loss LuppA upper-bounding CAP, and (b) a calibration loss Lealibr. supporting decomposability.
Figure 1:
losses for LAP 43 35 14
22
25
More recently, smooth differentiable rank approximations have 2]. but generally lose the important CAP upper bound property.
been proposed
15
27
The second important issue of AP optimization relates to its non-decomposabilit:: L averaged over batches underestimates AP 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 [T0,32] 20 32 30), or storing all training representatioons/cores leading to complex models with large computation and memory overhead.
33 25).
In this paper, we introduce a method for RObust And DecoMpoaable Average Precision (ROADMAP), which explicitly addresses the aforementioned challenges of AP optimization.
Our first contribution is to propose a smooth approximation of the rank function, with different behaviour for positive and negative examples. By this design, LSupAP provides upper bound of LAP. and always hack-propagates gradients when the correct ranking is not satisfied. These two features illustrated in the the toy example Figure Ta are not fulfilled by binning approaches
surrogate loss LsapAP for CAP. In particular, introduce
by SmoothAP 2
As a second contribution, we propose to improve the non-decomposability in AP training. To this end, we introduce simple yet effective training objective Cealibr. which calibrates the scores among different batches by controlling the absolute value of positive and negative samples. We provide theoretical analysis showing that Lealibe. decreases the decomposability gap. Figure iilluttaate how Cealibr. can be leveraged to improve the overall ranking.
We provide thorough experimental validation including three standard image retrieval datasets and show that ROADMAP outperforms state-of-the-ar 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.
Related work
We discuss here the literature in image retrieval dedicated to AP optimization, and compare to other
approaches based on optimizing representations [23 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 26). triplets M. quadruplets [8] or n-uplets [30] to enforce partial ranking. These metric learning methods optimize 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-auu inference" 22 or adapt to weak supervision 6 Recently, 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
27 by using a smoothed discretization of similarity scores. Other approaches rely on explicitly approximating the non-eifferentiabl rank functions using neural networks [8) or with 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 an AP loss upper bound. The Lsupar introduced in this work is based on smooth approximation of the rank function leading to an upper bound on the AP loss, making our approach both accurate and robust.
3
Decomposability in AP optimization Batch training is mandatory in deep learning. However, the non-decomposability of AP is 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 the whole training set is prohibitive. This has been addressed by efficient batch sampling [33 IC 32 or selecting informative constraints within mini-batches (30 4 32) In cross-batch memory technique (39], the authors assume slow drift in learned representations to store them and compute global mining in pair- based deep metric learning.
In AP optimization, the non con-dccoomosabilityy has essentially been addressed by a brute force increase of the batch size 27 25 This includes an important overhead in computation and memory, gen- erally involving a two-step approach for first computing the AP loss and subsequently re-computing activations and back proppppgggg gradients. In contrast, our loss Lealibe. does not add any overhead and enables good performances for AP optimization even with small batches.
3 Robust and decomposable AP training
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 retrieval set Ω = je: composed of N elements, and a set of M queries included in Ω2, i.e. Q {q:) (qi)ee []] S Ω. For each query qi each element in f assigned label y(ær; 4:) E [+1:-] -1]. such that y( qi) = 1 (resp. y( qe) = 11) if æ is relevant (resp. irrelevant) with respect to Qz. This defines query-dependent partitioning of Ω such that S2 = WG, where P, == {xz- E S2 q:) = +1} and N₁ == {ar E (z) q:) -1..
For each æÿ E Ωt we define a prediction model parametrized by parameters 0, e.g. deep neural network, which provides vectorial embedding Vq E dRd of each element, i.e.: Vg: = fo()). In the embedded space R we compute a similarity score between each query qi and each element in Ω, e.g. by using the cosine similarity: s(q;, m.)) = I I|v
Va. 'vy
During training, our goal is to optimize, for each query qt, the model parameters O such that positive elements are ranked before negatives. More precisely, we aim at minimizing the AP loss LAP, for each query qi in the retrieval set Q. Our overall AP loss LAP is averaged over all queries:
Σ OP), AP. CAp( = M 1=1
1
Σ kEP.
Pre(k: 0)
1
rank* + (k, 0) rank(k; 0)
(1)
IP:
Pi
KEP.
where Pre(k: 8) is the precision for the hh positive example Tk rank* + (ks, 8) its rank among positives Pt. and the rank(k: 8) its rank over l P. U..
As previously mentioned, there are two main challenges with SGD optimization of AP in Eq. Q i) AP(0) is not differentiable with respect to 0, and ii) AP does not linearly decompose into batches. ROADMAP addresses both issues: we introduce the robust differenniable LupAA surrogate (Section 3.1 and add the Lealibe. loss (Section 3.2) to improve AP decomposability. Our final loss CROADMAP i8 a linear combination of LSpAAP and Lealibr. weighted by the hyperparameter A:
CROADMAP( (0) = (1 - A) LsupAP()) + A Lealibe (0)
(2)
3

---

Images encoding
Smooth rank (see 3.1)
Vg: Rd
SupAr oq. (5)
SuupAl 2 LAP
H
rank, (A) E, H (8y - mpe
rank (k)
V1
VN
fo
rank+ (ank++()-00 (6)= H| (8, 8k)
Decomposability (see 3.2)
Ω
DGAP +
-
2
88 - st]t
Cashbrr eq. (
LAP, = PP. ΣXEP
rank (k.0) TA
CROADMAP (0) (1 A) LsupAr + Cealibr. (0)
Figure 2: ROADMAP training: we optimize parameters 0 of deep neural networks to minimize a smooth surrogate of CAP, (0) between the query qi and the retrieval set Ω. Our smooth rank approximations H and H enables LSpAAP be both accurate and robust (sec 3.1), and Cealibe. enables an implicit batch scores comparison for better decomposability without addıtional storing (sec 3.2
3.1 Robustness in smooth rank approximation
The non-differentiablity in Eq ① 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 !.
{
if t 1 0
rank ((k)++()---))))())) = 1+
Σ
H(s; (8)), where H(I)
otherwise
jEPi(K)
rank(k) = rank + (k) +
Σ
H(s;- - 5R) = rank + (k) + rank (A)
(3)
JEN.
From Eq. (3) it becomes clear that the con-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 d& E Pj: the score 9y in Eq. (3) is always the score of positive, whereas 9j can either be negative's positive's score.
Smooth loss LSupAP To provide smooth approximation of LAP in Eq. I we introduce smooth approximation of the rank function. particular, we propose different behaviour between rank" (k) and rank (k)) in Eq. (3) by defining two functions H+ and H-
(kk)
For rank (k). we choose to keep the Heaviside (step) function, i.e. H H (see Fig. Bap. which consists in ignoring rank (k) in gradient-basee AP optimization. This is done purpose rank (R)
since Trank [R] (k) (R))² 2 O: the gradient would tend to increase rank (k) and to
BAP
decrease the score of sk. Reminding 24 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
(+)) ift s O, where is the sigmoid function (Fig. 3c
H- = + if 80 with 2 (o 0.5 ift 8
(4)
where 7 and p 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
For the sake of readability we drop in the following the dependence on 0 for the rank, i.e. rank(k) = rank(k, 0) and on the query for the similarity, i.e. 85 == 2[g;,

---

1.75
bou: seto gradieut
gradieni
correcsly rar.kod
130
1.2
<<
de << $g
segatiivs
4/
1.30
sigmoid
077
6.73
wrosglyy Hegataves
zanagan
0.2
1.5
1.0
0.5
0.0
6.
10
15
-15
5%
8kk
(a) H (x) = (x) in Eq.
(b) (x) in Eq.
(c) Sigmoid used in
Figure 3: Proposed surrogate losses for the Heaviside (step): with H (x)) in Fig. 3a and H (x) in
Fig. 3b Supar in Eq. (5) is an upper bound of LAP. In addition, H (x)
gradients
until the correct ranking is satisfied, in contrast to the sigmoid used in (Fig. 3c
the H smooth approximation defined in Eq. (4). we obtain the following smooth approximation rank, (k)) Σ H (sj Sk), leading to the following smooth AP loss approximation: jEN;
rank* (ak=*(()) (k)
(0) =
Σ
(5)
P
rank (k) + rank, (k:)
kEP,
CSuPAP in Eq. (5) fulfills two main features for AP optimization:
LupAA is upper bound of CAP in Eq. (1). Since I/ in Eq. 4 is upper bound of step function (Fig 3b). it is easy to see that L 2 LAP. This a very important property, since it ensures that the model keeps training until the correct ranking is obtained. It is worth noting that do not fulfill this property.
existing smoooh rank approximations in the literature [35 3 27 2
2 LSupAP brings training gradients until the correct ranking plus margin is fulfilled. When the ranking is incorrect, the negative æj ranked before the positive 24 thus 8, > Sk and Hx, 81.) in Eq. (4) has a non-null derivative. We use sigmoid to have a large gradient when 8j 82 is small. To overcome vanishing gradients of the sigmoid for large values 8,- 8k,, we use a linear function ensuring constant derivative. When the ranking is correct (s, < &g), we enforce robustness by imposing a margin parametrized by (sigmoid Eq. (4) This margin overcomes the brittleness of rank losses, which vanish as soon the ranking is correct [1 25).
Comparison SmoothAP [2] LupAA differs from LSmoothAP in by providing an upper bound on CAP, ii) improving the gradient flow (Fig. 3b vs Fig. 3c). and iii) overcoming adverse effects of the sigmoid for rank* as shown in Fig. la (and in supplementary see. A). We experimentally verify
the consistent gain brought out by LsppAP over LSmoothP.
3.2 Decomposable Average Precision
In Eq. T AP decomposes linearly between queries Jt. but AP, 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, consider 1 (I:(::)) batches of size B, such that N/B K E N. Let AP (0) the AP batch for query qı. we define the "decomposability gap" DG as follows:
DG
Σ
AP! (P)
K
DG in Eq. 6 is direct measure of the non-decomposability of AP (see supplementary Sec. A). Our motivation here decrease DG iee. to have the average AP over the batches as close as possible to the AP computed over the whole training set. To this aim, introduce the following loss
5

---

during training:
Cealibr. (0)
aa
syl+
[s, 8]+ EE
Σ
P
calie.
Cdiite.
where [xr]+ max(0, The loss Lallibe enforces the score of the positive ai E P; to be larger than a, and Lilirr enforces the score the negative žj E N to be smaller than B < a. Cealibr. is a standard pair-based loss [12], which we revisit in our context "calibrate" the values of the scores between mini-batches: intuitively, the fact that the positive (resp. negative) scores are above (resp. below) threshold in the mini-batches makes the average AP closer the AP on the whole dataset.
Upper bound on the decomposabilty gap To formalize this idea, we provide a theoretical analysis of the impact the global ranking of Lealibr. in Eq. 7). Firstly, on each batch, the overall AP and the AP in batches is null, i.e. AP) = 0 and we get a decomposable AP. In more general setting, show that minimizing Lealibr. each batch reduces the decomposability gap, hence improving the decomposability of the AP.
that if & caality C O,
Let's consider K batches JbE(1:K) of batch size B divided in P positive instances and A² negative instances w.r.t. the query qi. To give some insight we assume that the AP each batch is one (i.e. AP, = 1), and give the following upper bound of DG
j+ P!
IPA-11 1 WVH + |N
SS AG 1
ΣΣ j+ + 1
(8)
Σ b=
IPPI
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 the batches (see supplementary Sec. A).
We can refine this upper bound by introducing the calibration loss Cealibr. and constraining the scores of positive and negative instances to well calibrated. On each batch we define the following quantities ET EyeN, (s; 3) which are the negative instances that do not respect the constraints and GT = ===EjeN; EjeN 1 (s, - () the negative instances that do. We similarly define Fg and G We then have the following upper bound the decomposability gap:
K
G
G+ +... GG.
0 DGAP S
Σ
E
|Pb]
j+ GT + .... + G + Ej + ....ET.. EØ
F
G + IP| .... |P|-11
Σ
j + GO + PH + .... Ip | [N + IN
This refined upper bound is tighter than the upper bound of Eq. (8) Our new Lealibe. loss directly optimizes this upper bound (by explicitly optimizing F, F5. E, GT making it tighter, hence improving the decomposability of the AP (see supplementary Sec. A).
Experiments
Experimental setup We evaluate ROADMAP the following three image retrieval datasets: CUB-200-2011 37 contains 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 dataset with 120 images of 22 634 objects classified into 12 categories (e.g. bikes, coffee makers). We the reference train and test splits from BI). INaturalist-200 [36] is large scale dataset of 461 939 wildlife animals images classified into 8142 classes. We the splits from 22 with 70% of the classes in the train set and the rest in the set.
ROADMAP settings For all experiments Section 4.1 and Section we use 0.5 for CROADMAP in Eq. 0.01 and p 100 for LupAA Eq. 5
0.9 and 3 0.6 for Cealibe.

---

in Eq. 77. We study more in depth the impact of those parameters in Section 4.3 Deep models are trained using Adam [77] for ResNet-50 backbones and AdamW [9 for DeiT transformers [3]]
Test protocol Methods are evaluated using the standard recall at k (R @k) and mean average precision 24 (mAP@R) metries (see supplementary Sec. B).
4.1
ROADMAP validation
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 AP approximations. In [ we compare ROADMAP on the three datasets to recent AP loss approximations including the soft- 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 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 contributions, Lee. robust smooth AP upper bound and our AP decomposability improvement (see supplementary Sec. B).
Table I: Comparison between ROADMAP and state-of-the-ard AP ranking based methods.
CUB
SOP
INaturalist
Method
R@D
mAP@R
R@D
mAP@R
R@D
mAP@E
FastAP
3
58.9
22.9
78.2
51.3
53.5
19.6
SoftBin
27
61.2
24.0
80.1
53.5
56.6
20.1
BlackBox
28
62.6
23.9
80.0
53.1
52.3
15.2
SmoothAP 62.1
23.9
80.9
54.6
59.8
20.7
ROADMAP
64.2
25.3
82.0
56.5
64.5
25.1
Comparison to memory methods.
XBM stores the embeddings of previously seen batches 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), is time consuming, We ran experiments storing the entire dataset for SOP (60k embeddings), but for INtuuallitt we could not train while storing all the dataset in tractable time. We chose to store the same amount of embeddings for SOP 60k embeddings which about 17% of the training set.
We see in Table 2 that XBM is approximately 3 times longer train than ROADMAP. This becomes critical on INaturalist, where training while storing 60k images takes about 3 days, and reaches only R @1 of 60. Consequently, ROADMAP outperforms XBM on both datasets; there is a +2t increase on both metrics for SOP and an especially large gap on INaturalist. In the latter, not being able store all the embeddings affects drastically the performances of the XBM in negative way. There is 5pt difference in R@ and more than 6pt in mAP@R. This demonstrates the suitability of ROADMAP on large-scale scale settings.
Table Our method compared to cross batch memory minutes per epoch.
39 The unit of time is m/e which stands for
SOP
INaturalist
Method
R 1
mAP@R
time
R@
mAP@R
time.
XBM 39
80.6
54.9
6
59.3
18.5
34
ROADMAP (ours)
82.0
56.5
2
64.5
25.1
12
Ablation study. To study more in depth the impact of our contributions, we perform ablation studies Table 3 We show the improvement against SmoothAP 2 when changing the sigmoid by H+ and H for LSupAP in Eq. (). and the use of Lealihr. in Eq. 7 We can see that LSupAP consistently improves performances over SS (0.9pt on CUB, 0.5pt on SOP and 1.5pt on INaturalist). S and Lealite equally contribute to the overall gain in CUB and SOP, but the gain of Cealibe. is much
7

---

more important on INaturalist. This is explained by the fact that the batch vs. dataset ratio size N. tiny (< 1). making the decomposability gap in Eq. (6) huge. We can see that Cealibe. is very effective for reducing this gap and brings a gain of more than 3pt.
& is
Table 3: Ablation study for the impact of our two contribution on and the SmoothAP baseline.
CUB
SOP
INaturalist
Method
Cealibr.
R
mAP@R R
R@1
mAP@R
R@ 1
mAP@R
AmoothAP 2
X
62.1
23.9
80.9
54.6
59.7
20.7
SupAP ROADMAP
X
62.9
24.6
81.4
55.3
61.2
21.3
64.2
25.3
82.0
56.5
64.5
25.1
4.2
State of the art comparison
compare ROADMAP 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 229 38 16 42), classification losses for image retrieval [46 | 33), and AP approximations 2 2 ROADMAP falls in the latter category. We use the same setup in Section 4.1 and follow
standard practices for ResNet-50 33 1 by using larger images (256 x 256 on SOP and CUB) and using instead of average pooling and layer normalization for CUB.
Using the popular ResNet-50 backbone, ROADMAP establishes a new state of the across all meth- ods 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 all datasets with a 2pts R @ 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 [ 34], further lifts the performances of ROADMAP by several point, from points depending on the dataset, with smaller embedding size (384 512). The decomposable AP approximation ROADMAP also outperforms by significant margin IRTR, the DeiT architecture for image retrieval introduced in trained with a contrastive loss. Overall ROADMAP achieves state-of of of-the-art performances across all three datasets by significant margin.
4.3 Model Analysis
We show in Fig. the impact of the main ROADMAP hyperparameters on INaturalist. The relative weighting À from Eq. (2) controls the balance between two training objectives LS and Cealitn: = reduces CROADMAP to LSupAP while À to Lealibe. We can see in Fig. 4a that training with the complete CROADMAP with both Leatibe. and SsupAP is always better than using only of the two losses. Note that results are stable in the [0.2, 0.8] range with a consistent 1=55pt increase, demonstrating the robustness of ROADMAP this hyperparameter tuning.
28
25.5
28
27
26
26
mAP@R
26
25.5
24
22
25
25
20
24
24.5
18
* CROADMAP
23
16
CSIAP
24
0.2
10P
10
10a
10a
10
0.6
0.8
(a) mAP@R À for CROADMAP
(b) mAP@R p for LSMAA
mAP@R
B for Lestihe.
Figure 4: Analysis of ROADMAP hyperparameters on INaturalist (batch size 224).
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 (wrong) high score. As shown in

---

Table 4: Comparison of state of the art performances from the literature on SOP, CUB and INaturalist with the proposed ROADMAP (recall@k) k). Except for the DeiT category, all methods rely on standard convolutional backbone (generally ResNet-50).
SOP
CUB
INaturalist
Method
dim
10
100
2
4
8
16
32
Triplet SH 40
512
72.7
86.2
93.8
63.6
74.4
83.1
90.0
58.1
75.5
86.8
90.7
Metric learning
LiftedStruct
31
62.1
79.8
91.3
47.2
58.9
70.2
80.2
MIC 29
512
77.2
89.4
95.6
66.1
76.8
85.6
MS 38
78.2
90.5
96.0
65.7
77.0
86.3
91.2
SEC
45
512
78.7
90.8
96.6
68.8
79.4
87.2
92.5
HORDE [6
512
80.1
91.3
96.2
66.8
77.4
85.1
91.0
XBM [39
128
80.6
91.6
96.2
65.8
75.9
84.0
89.9
Triplet SCT
42
512/64
81.9
92.6
96.8
57.7
69.8
79.6
87.0
ProxyNCA
23
512
73.7
49.2
61.9
67.9
72.4
61.6
77.4
87.0 90.6
Classification
ProxyGML
78.0
90.6
96.2
66.6
77.6
86.4
NSoftmax
44
512
78.2
90.6 96.2
61.3
73.9
83.5
90.0
NSoftmax
2048
79.5
91.5 96.7
65.3
76.7
85.4
91.8
Cross-Entropy
2048
81.1
91.7 96.3
69.2
79.2
86.9
91.6
ProxyNCA++
80.7
92.0 96.7
69.0
79.8
87.3
92.7
ProxyNCA++
33
2048
81.4
92.4 96.9
72.2
82.0
89.2
93.5
FastAP B
512
76.4
89.0
95.1
60.6
77.0
87.2
90.6
BlackBox
28
512
78.6
90.5 96.0
64.0
75.3
84.1 90.6
62.9
79.4
88.7
91.7
AP loss
SmoothAP 2
512
80.1
91.5 96.6
67.2
81.8
90.3
93.1
SoftBin 27
512
80.6
91.3 96.1
61.2
73.14
83.0
89.5
64.2
77.1
82.7
91.7
ROADMAP (ours)
83.1
92.7
96.3
68.5
78.7
86.6
91.9
69.1
83.1
91.3
93.9
DeiT
IRTR
384
84.2
93.7
97.3
76.6
85.0
91.1
94.3
ROADMAP (ours)
384
86.0
94.4
97.6
77.4
85.5
91.4
95.0
73.6
86.2
93.1
95.2
Fig. 4b the improvement is important and stable in [10, 100). Note that >>> 0) already improves the results compared to p in 2 There an important decrease when p >>>>>>>>>>>/ 100 probably due the high gradient that takes over the signal for correctly ranked samples. The impact the margin 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@ compared to the LapAA baseline without the decomposability loss. Best results are achieved with smaller margins 0.1 < 3 < 0.4.
Cealibr. shown in Fig- 4cc Once again, ROADMAP exhibits
Fig. shows the improvement in mAP@E on the three datasets when adding Cealibe. CSpAAP. We can see that the increase becomes larger as the batch size gets smaller. This confirms our intuition that the decomposability in Cealibr. has 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 very poor approximation of the global AP.
2.5
2.4
2.1.
2.2
16.3
2.6
15
2.3
1.7
1.5
10.3
5,8
0.5
5
3.2
384
224
128
64
32
384
224
128
64
32
384
224
128
64
32
(a) CUB
(b)
(c) INaturalist
Figure 5: Relative increase of the mAP@R @R vs batch size when adding Cealibe. to LSpAA..

---

As qualitative assessment, we show in Fig. 6 some results of ROADMAP on INaturalist. We show the queries (in purple) and the 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 INaturalist, where ROADMAP corrects some failing cases of the SmoothAP baseline.
Figure 6: Results INaturalist: query (purple) with the 4 most similar retrieved images (green).
Figure 7: Results INaturalist: query (purple) with the 9 most similar retrieved images, green for relevant images, red otherwise. Top line results with ROADMAP. Bottom line results with SmoothAP.
Conclusion
This paper introduces the ROADMAP method for gradient- based optimization of average precision. ROADMAP is based smooth rank approximation. leading to the LupAA being both accurate and robust. To overcome the lack of decomposability in AP, ROADMAP is equipped with a calibration loss Lealihr. 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 strength of ranking methods with the simplicity of batch strategy. Without bells and whistles, ROADMAP is able to outperform state-of-the-ee performances on three datasets, and remains effective even with small batch sizes.
As any work on image retrieval, our contribution could be applied critical applications in surveil- lance 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 need for full supervision to tackle situations more representative to in-the-wild scenarios.
This work was done under a grant from the the AHEAD ANR program (ANR- 20-THIA-0002). was granted access to the HPC resources of IDRIS under the allocation 2021- ADO 1012645 made by GENCI.
Acknowledgement
10

---

References
[1] Malik Boudiaf, Jérôme Rony, Imtiaz Masud Ziko, Eric Granger, Marco Pedersoli, Pablo Piantanida, and Ismail Ben Ayed. A unifying mutual information view of metric learning: cross-entropy vs. pairwise losses, In European Conference on Computer Vision, pages 548-564. Springer, 2020.
[2] Andrew Brown, Weidi Xie, Vicky Kalogeiton, and Andrew Zisserman. Smooth-ap: Smoothing the path towards large-scale image retrieval. In European Conference on Computer Vision, pages 677-694. Springer, 2020.
[3] Fatih Cakir, Kun He, Xide Xia, Brian Kulis, and Stan Sclaroff. Deep metric learning to rank. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1861-1870, 2019.
[4] Micael Carvalho, Rémi Cadène, David Picard, Laure Soulier, Nicolas Thome, and Matthieu Cord. Cross-modes retrieval in the cooking context: Learning semantic text-image embeddings. In Kevyn Dollins-Thompsonn Qiaozhu Mei, Brian D. Davison, Yiqun Liu, and Emine Yilmaz, editors, The 4 International ACM SIGIR Conference on Research & Development Infor- mation Retrieval, SIGIR 2018, Ann Arbor, MI, USA, July 08- 12, 2018, pages 35-44. ACM, 2018.
[5] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbom, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
[6] Thibaut Durand, Nicolas Thome, and Matthieu Cord. Exploiting negative evidence for deep latent structured models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(2):337-351, 2019.
[7] Alaaeldin El-Nouby, Natalia Neverova, Ivan Laptev, and Hervé Jégou. Training vision trans- formers for image retrieval. arXiv preprint wwxiv:2102.056444 2021.
[8] Martin Engilberge, Louis Chevallier, Patrick Perez, and Matthieu Cord. Sodeep: A sorting deep net to learn ranking loss surrogates. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), June 2019.
[9] Fartash Faghri, David J. Fleet, Jamie Ryan Kiros, and Sanja Fidler. VSE++: improving visual- semantic embeddings with hard negatives. In Brilish Machine Vision Conference 2018, BMVC 2018, Newcastle, UK, September 3-6, 2018, page 12. BMVA Press, 2018
[10] Weifeng Ge. Deep metric learning with hierarchical triplet loss. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018
[11] Albert Gordo, Jon Almazán, Jérôme Revaud, and Diane Larlus. End-to-end learning of deep visual representations for image retrieval. Int. J. Comput. Vis., 124(2):23-2254, 2017.
[12] Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR (CVPR'06), volume 2, pages 1735-1742. IEEE, 2006.
[13] Ben Harwood, Vijay Kumar G, Gustavo Carneiro, Ian Reid, and Tom Drummond. Smart mining for deep metric learning. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
[14] Kun He, Fatih Cakir, Sarah Adel Bargal, and Stan Sclaroff. Hashing as tie-aware learning to rank. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018
[15] Kun He, Yan Lu, and Stan Sclaroff. Local descriptors optimized for average precision. IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2018.
11

---

[16] Pierre Jacob, David Picard, Aymeric Histace, and Edouard Klein. Metric learning with horde: High-order regularizer for deep embeddings. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 6539-6548, 2019.
[17] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980 2014.
[18] Marc T. Law, Nicolas Thome, and Matthieu Cord. Learning a distance metric from relative comparisons between quadruplets of images. Int. Comput. Vis., 121(():65-94, 2017.
[19] Iya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101 2017.
[20] R. Manmatha, Chao- Yuan Wu, Alexander J. Smola, and Philipp Krähenbühl. Sampling matters in deep embedding learning. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 2859-2861 IEEE Computer Society, 2017.
[21] Brian Mcfee and Gert Lanckriet. Metric learning to rank. In In Proceedings of the 27th annual International Conference on Machine Learning (ICML, 2010.
[22] Pritish Mohapatra, Michal Rolínek, C.V. Jawahar, Vladimir Kolmogorov, and M. Pawan Kumar. Elficient optimization for rank-based loss functions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
[23] Yair Movshovitz-Attia Alexander Toshev, Thomas K Leung, Sergey loffe, and Saurabh Singh. No fuss distance metric learning using proxies. In Proceedings of the IEEE International Conference Computer Vision, pages 360-368, 2017.
[24] Kevin Musgrave, Serge Belongie, and Ser-Nam Lim. A metric learning reality check. In European Conference on Computer Vision, pages 681-699. Springer, 2020.
[25] Marin Vlastelica P., Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolínek. Differenti- ation of blackbox combinatorial solvers. In ICLR, 2020.
[26] Filip Radenovic, Giorgos Tolias, and Ondrej Chum. CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision ECCV 2016 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part I, volume 9905 of Lecture Notes in Computer Science, pages 3-20. Springer, 2016.
[27] Jerome Revaud, Jon Almazán, Rafacl Rezende, and Cesar Roberto de Souza. Learning with average precision: Training image retrieval with a listwise loss. In Proceedings the IEEE/CVF International Conference on Computer Vision, pages 5107-5116, 2019.
[28] Michal Rolínek, Vít Musil, Anselm Paulus, Marin Vlastelica, Claudio Michaelis, and Georg Martius. Optimizing rank-based metrics with blackbox differentiation. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7620-7630, 2020.
[29] Karsten Roth, Biagio Brattoli, and Bjorn Ommer. Mic: Mining interclass characteristics for improved metric learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8000-8009, 2019.
[30] Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In D. Lee, M. Sugiyama. U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016
[31] Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
[32] Yumin Suh, Bohyung Han, Wonsik Kim, and Kyoung Mu Lee. Stochastic class-based hard example mining for deep metric learning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
12

---

[33] Eu Wern Tch, Terrance DeVries, and Graham W Taylor. Proxynca++: Revisiting and revitalizing proxy neighborhood component analysis. In European Conference on Computer Vision (ECCV). Springer, 2020.
[34] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. arXiv preprint arXiv:2012.12877, 2020.
[35] Evgeniya Ustinova and Victor Lempitsky. Learning deep embeddings with histogram loss. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[36] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection dataset. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 17798877, 2018.
[37] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie. The Caltech-UCSD Birds-200-2011 Dataset. Technical Report CNS-TR-201 1-001, California Institute of Technology. 2011.
[38] Xun Wang, Xintong Han, Weilin Huang, Dengke Dong, and Matthew R Scott. Multi-similarity loss with general pair weighting for deep metric learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5022-5030, 2019.
[39] Xun Wang, Haozhi Zhang, Weilin Huang, and Matthew R Scott. Cross-batch memory for embedding learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6388-6397, 2020.
[40] Chao- Wu, R Manmatha, Alexander J Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. Proceedings of the IEFE International Conference on Computer Vision, pages 2840-2848, 2017.
[41] Eric Xing, Michael Jordan, Stuart Russell, and Andrew Ng. Distance metric learning with application to clustering with side-information. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems, volume 15. MIT Press, 2003.
[42] Hong Xuan, Abby Stylianou, Xiaotong Liu, and Robert Pless. Hard negative examples are hard, but useful. In European Conference on Computer Vision, pages 126-142. Springer, 2020.
[43] Yisong Yue, Thomas Finley, Filip Radlinski, and Thorsten Joachims. A support vector method for optimizing average precision. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '07, pages 27 271-278, New York, NY, USA, 2007. ACM.
[44] Andrew Zhai and Hao-Yo Wu. Making classification competitive for deep metric learning. CoRR, abs/18 11188.1166499 2018.
[45] Dingyi Zhang, Yingming Li, and Zhongfei Zhang. Deep metric learning with spherical embed- ding. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18772-18783. Curran Associates, Inc., 2020.
[46] Yuehua Zhu, Muli Yang, Cheng Deng, and Wei Liu. Fewer is more: A deep graph metric learning perspective using fewer proxies. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17792-17800 Curran Associates, Inc., 2020
13


Reviews:
[{"review_id": "vtJEZUr8mPj", "reviewer": "Reviewer_ea3h", "summary": "The paper proposes a new loss for image retrieval based on average precision. \n\nImportantly, 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.\n\nThe paper lists as contributions:\n1) 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,\n2) improving the 'non-decomposability' problem associated with other AP-loss approximations,\n3) experimental validation on CUB, SOP, and iNaturalist, showing state-of-the-art results.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n\nThe paper reads very well and has no typos. The motivations (the shortcomings of the current AP-l approximations) are well described. The approach is described well and is easy to understand. The authors report state-of-the-art results on the three datasets considered. \n\n# Weaknesses\n\nMy main concern with the contents of the paper during the review has been the exposition of the calibration loss used to address the 'non-decomposability' problem. IIUC, the size of the non-decomposability gap is both dataset and batch-size dependent and hence proper values for \\alpha \\beta would also always be dataset-dependent. The paper is lacking some more information about how the values for those hyper-parameters have been selected in L.181, since, albeit referring the reader to section 4.3, section 4.3 only shows the profile of those parameters for iNaturalist. In addition, given the significant number of extra hyperparameters (\\sigma, \\alpha, \\beta, \\lambda, \\tau, \\rho), it would have been better if the paper evaluated the method in more datasets, e.g., RParis and ROxford, which are more standardized datasets for image retrieval. This would enable a better comparison against other works, including the AP-loss of Revaud et al, which is cited in the paper but not compared against in Table 3.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "YEl87yc63hu", "reviewer": "Reviewer_9iMr", "summary": "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\n1) 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.\n2) A calibration component which tackles the problem of mismatch between in-batch and true AP values commonly seen in previous methods.\n\nThe 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality\nThe idea of smoothening the indicator function in the AP-loss is a well-studied one as pointed out by the authors, with recent works showing success [2, 27]. The proposed smooth AP loss is very similar to the one in [2]. However, I believe the authors have given enough justification theoretically to support their differences with existing AP losses, and the analysis on the upper bounds and gradient flow is very convincing.\n\nThe idea of bridging the decomposability gap is novel, as to my best knowledge previous works tackle this with a brute-force manner, which results in either requiring huge amounts of memory or much slower training due to the need for accumulating gradients over multiple batches. I believe the contribution of this novelty is the main selling point of this work.\n\n## Quality\nThis work is technically very polished, as mentioned earlier it provides highly thoughtful theoretical analysis to support the main ideas brought forward in the work. With reference to the smooth AP loss in **Originality** above, even though the improvement in this loss is incremental, the mathematical working, *e.g.* derivations of gradients in Supp.  helps a lot in the understanding of the motivation behind such proposals. One nitpick I have though: The illustrations of Fig. 1, Supp Fig. 2 & 4 are a nice addition but could be a bit not straightforward to understand. For example in Figure 1(a), why is the negative example at 0.9 and the positives at 0.76 & 0.77? Are those the $\\ell_2$ distances or cosine similarities with the query? I suppose it would be the cosine similarities as the gradient direction suggests the positive (resp. negative) samples to increase (resp. decrease)? Anyway, this could cause some confusion so maybe having a small section either in the caption or the main text to explain what each component of the illustration represents, or directly annotating over the figures would help clarify this better. However, as I mentioned earlier the mathematical working more than covers for this. Especially for the upper bound of the decomposability gap in Eqs (8) & (9) which provides solid support to the addition of the proposed calibration loss term.\n\n## Clarity\nThis paper is very well-written and organized, especially with the theoretical part. It also includes adequate illustrations to visualize the ideas and experimental results.\n\n## Significance\nI do not have much doubt about the significance of ROADMAP for the image retrieval community, as reflected by the SotA performance across all three datasets as presented in Tables 1 & 3. Like I mentioned earlier, the proposed variant of smooth AP loss SupAP seems to be a much more incremental step compared to the decomposability GAP loss term, as is evident in the ablation study in Table 2 the effect of adding $\\mathcal{L}_\\text{calibr.}$ seems to be much more pronounced than SupAP *v.s.* Smooth AP. This is especially true on INaturallist, which is by far the largest and most fine-grained (8000+ classes v.s. 200 & 12 in the other two) dataset amongst the 3 presented, which is probably the case that $\\mathcal{L}_\\text{calibr.}$ tackles the best due to the extra noise within batches, hence increasing $DG_\\text{AP}$. One critique would be that the authors could expand on this even more, *e.g.* by gradually reducing the number of classes, do we see $\\mathcal{L}_\\text{calibr.}$ bring less performance boost compared to without it? Also, in the ablation study, it would also be great to see how adding $\\mathcal{L}_\\text{calibr.}$ alone compares with SmoothAP [2] for completeness of the analysis.\n\nHowever, overall I’m still convinced by the results and adding to the thorough theoretical contributions of this work, it will definitely be a solid reference point for future works.\n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "TRYgyHJYdrA", "reviewer": "Reviewer_mYow", "summary": "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:\n- 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.\n- 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.\nEvaluation shows improvements with respect to recent AP approximations (e.g. [2, 3, 27]) on standard benchmarks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Novelty / Originality: the paper builds on recent AP approximation methods, particularly SmoothAP[2] (as seen clearly in Table 2). From that perspective, the paper is somewhat incremental. However, the modifications proposed are non-trivial and lead to improved results. I think the paper reaches the minimum level of novelty and originality required to be considered for acceptance.\n\nClarity: Mostly well written and easy to follow, although section 3.2 (Decomposable Average Precision) was, comparatively, not as clear as the rest of the paper. Perhaps the authors would like to revise that section if the paper gets accepted.\n\nMethod: The SupAP loss is well motivated, both from an intuitive and a theoretical point of view. The calibration loss is not so clear, and, although I see the main idea behind it (L_AP over batches underestimates L_AP, so a loss to reduce this gap is introduced. This is achieved by introducing a separation between positives and negatives), I have a some questions for the authors.\n\nEvaluation: The method is tested on standard benchmarks (CUB, SOP, iNaturalist) and compared against recent AP approximations ([2, 3, 27, ...]) using recent architectures (ResNet, DeiT). Results show the superiority of the proposed approach on these benchmarks. Ablation studies are also shown.\n\nReproducibility: Code is not provided yet (authors mention that they plan to release it but don't have clearance yet). Hyperparameters and other technical details are provided. A domain expert should be able to reimplement the method with a reasonable chance of success.\n\nSignificance: this method follows a series of approaches that are becoming more and more popular in recent years. Given that, and given the strong empirical results, I'd say the paper's contribution is significant, although, as I mentioned before, I see it as somewhat incremental wrt [2].\n\nQuestions for authors: \n\nRegarding the calibration loss: my understanding is that, ideally, one should reduce the gap between the AP on the whole dataset and the AP on a batch, and the proposed loss implicitly reduces that gap. However, doesn't this mean that the loss could actually reduce that gap by hurting both the global AP and the batch AP? is there any mechanism to prevent this (beyond the L_supap loss)?\n[In general, I can't keep but think that the authors found that separating the positives and negatives within a batch (a very reasonable thing to try) had a positive impact, and built the calibration loss around this idea, hence the reason it feels convoluted.]\n\n- From Table 2, could we see the results of using L_calib without using L_supap? I think this is important to disentangle the impact of each contribution.I've seen Figure 4a, but I think this information should be available in table 2 on all datasets. Also, why is map@R lower in table 2 than in figure 4a? Is the model in table 2 weaker? If that's the case I think we should see the ablation study on a strong model as well.\n\n- There seems to be a divide in the ranking community between groups that report results in datasets like CUB or SOP, and groups that  report results in datasets such as Oxford and Paris. I am not requesting additional experiments during the review period. However, if the authors wished to add results on these datasets following standard training practices (see e.g. https://github.com/filipradenovic/cnnimageretrieval-pytorch for a codebase that allows training) either on an appendix of the final paper or a future technical report, I think this would considerably benefit the community.\n\nNit: What does the asterisk (*) denote by SoftBin in Table 3? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Paper describes societal impact in a reasonable manner in the conclusions of the paper.\nPaper does not discuss technical limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "CF-L6o2ddrM", "reviewer": "Reviewer_PwyW", "summary": "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.\nThe method shows superior performance and the theoretical seems correct.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although the idea of differentiable AP loss is not a new concept, the solution given by the paper is novel. Especially the decomposable ap loss.\n\nBoth theoretical analysis and experimental justifications are given for the proposed method. Overall, the quality of the paper reaches the bar of the NeurIPS conference.\n\nThe paper is well written and the idea is clearly expressed. But the organization can be improved.\n\nThe smooth step function in Eq.(4)  weights the gradients better, however, this seems to be a trivial modification of the sigmoid function. Also, in Table 1, the comparison is unfair, since ROADMAP  also gains performance from the decomposable AP loss.\n\nThe comparison to other memory methods is an important experiment. The results should be included in the main text, rather than in the supplementary. (Also, typo in line 200, it should be Table 2). I suggest removing the qualitative results of Figure 6  to squeeze some space since it is not that indicative. It would be interesting to show how ROADMAP corrects some failing cases of other methods. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on the problem of learning to rank and introduces a method, ROADMAP (RObust And DecoMposable Average Precision), consisting of a new surrogate loss for average precision (AP) and a "calibration" loss to be used together with the AP loss.

All reviewers recommended to accept.

Accept.
Decision: Accept (Poster)