Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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:
- 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.
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.

Clarity: 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.

Method: 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.

Evaluation: 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.

Reproducibility: 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.

Significance: 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].

Questions for authors: 

Regarding 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)?
[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.]

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

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

Nit: What does the asterisk (*) denote by SoftBin in Table 3? 
limitations_and_societal_impact: Paper describes societal impact in a reasonable manner in the conclusions of the paper.
Paper does not discuss technical limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
The method shows superior performance and the theoretical seems correct.
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.

Both theoretical analysis and experimental justifications are given for the proposed method. Overall, the quality of the paper reaches the bar of the NeurIPS conference.

The paper is well written and the idea is clearly expressed. But the organization can be improved.

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

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



limitations_and_societal_impact: None
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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
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.

main_review: ## Originality
The 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.

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

## Quality
This 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.

## Clarity
This paper is very well-written and organized, especially with the theoretical part. It also includes adequate illustrations to visualize the ideas and experimental results.

## Significance
I 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.

However, 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.
 

limitations_and_societal_impact: The authors have addressed the limitations and potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 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.
main_review: # Strengths

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

# Weaknesses

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


limitations_and_societal_impact: Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

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)