# Robust and Decomposable Average Precision for Image Retrieval

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 53 references that are in the map.
- First posted on arXiv 1 Oct 2021.

## Builds on (most cited first, 30 of 36)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Deep Metric Learning via Lifted Structured Feature Embedding](https://mlsanity.com/paper/1511.06452/) (2015)
- [Multi-Similarity Loss with General Pair Weighting for Deep Metric Learning](https://mlsanity.com/paper/1904.06627/) (2019)
- [A Metric Learning Reality Check](https://mlsanity.com/paper/2003.08505/) (2020)
- [Sampling Matters in Deep Embedding Learning](https://mlsanity.com/paper/1706.07567/) (2017)
- [No Fuss Distance Metric Learning using Proxies](https://mlsanity.com/paper/1703.07464/) (2017)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Revisiting Oxford and Paris: Large-Scale Image Retrieval Benchmarking](https://mlsanity.com/paper/1803.11285/) (2018)
- [Learning with Average Precision: Training Image Retrieval with a Listwise Loss](https://mlsanity.com/paper/1906.07589/) (2019)
- [Cross-Batch Memory for Embedding Learning](https://mlsanity.com/paper/1912.06798/) (2019)
- [End-to-end Learning of Deep Visual Representations for Image Retrieval](https://mlsanity.com/paper/1610.07940/) (2016)
- [Deep Metric Learning with Hierarchical Triplet Loss](https://mlsanity.com/paper/1810.06951/) (2018)
- [ProxyNCA++: Revisiting and Revitalizing Proxy Neighborhood Component Analysis](https://mlsanity.com/paper/2004.01113/) (2020)
- [A unifying mutual information view of metric learning: cross-entropy vs. pairwise losses](https://mlsanity.com/paper/2003.08983/) (2020)
- [Smooth-AP: Smoothing the Path Towards Large-Scale Image Retrieval](https://mlsanity.com/paper/2007.12163/) (2020)
- [Smart Mining for Deep Metric Learning](https://mlsanity.com/paper/1704.01285/) (2017)
- [Training Vision Transformers for Image Retrieval](https://mlsanity.com/paper/2102.05644/) (2021)
- [Hard negative examples are hard, but useful](https://mlsanity.com/paper/2007.12749/) (2020)
- [CNN Image Retrieval Learns from BoW: Unsupervised Fine-Tuning with Hard Examples](https://mlsanity.com/paper/1604.02426/) (2016)
- [Optimizing Rank-based Metrics with Blackbox Differentiation](https://mlsanity.com/paper/1912.03500/) (2019)
- [Learning Deep Embeddings with Histogram Loss](https://mlsanity.com/paper/1611.00822/) (2016)
- [Local Descriptors Optimized for Average Precision](https://mlsanity.com/paper/1804.05312/) (2018)
- [MIC: Mining Interclass Characteristics for Improved Metric Learning](https://mlsanity.com/paper/1909.11574/) (2019)
- [Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies](https://mlsanity.com/paper/2010.13636/) (2020)
- [Cross-Modal Retrieval in the Cooking Context: Learning Semantic Text-Image Embeddings](https://mlsanity.com/paper/1804.11146/) (2018)

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

- [Optimization of Rank Losses for Image Retrieval](https://mlsanity.com/paper/2309.08250/) (2023)
- [Hierarchical Average Precision Training for Pertinent Image Retrieval](https://mlsanity.com/paper/2207.04873/) (2022)
- [UDON: Universal Dynamic Online distillatioN for generic image representations](https://mlsanity.com/paper/2406.08332/) (2024)
- [Threshold-Consistent Margin Loss for Open-World Deep Metric Learning](https://mlsanity.com/paper/2307.04047/) (2023)
- [Learning Semantic Proxies from Visual Prompts for Parameter-Efficient Fine-Tuning in Deep Metric Learning](https://mlsanity.com/paper/2402.02340/) (2024)
- [Supervised Metric Learning to Rank for Retrieval via Contextual Similarity Optimization](https://mlsanity.com/paper/2210.01908/) (2022)
- [Center Contrastive Loss for Metric Learning](https://mlsanity.com/paper/2308.00458/) (2023)
- [A Unified Deep Semantic Expansion Framework for Domain-Generalized Person Re-identification](https://mlsanity.com/paper/2410.08456/) (2024)
- [STIR: Siamese Transformer for Image Retrieval Postprocessing](https://mlsanity.com/paper/2304.13393/) (2023)
- [Retail-786k: a Large-Scale Dataset for Visual Entity Matching](https://mlsanity.com/paper/2309.17164/) (2023)
- [Single-shot Star-convex Polygon-based Instance Segmentation for Spatially-correlated Biomedical Objects](https://mlsanity.com/paper/2504.12078/) (2025)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)
- [ITEM: Improving Training and Evaluation of Message-Passing based GNNs for top-k recommendation](https://mlsanity.com/paper/2407.07912/) (2024)
- [Enhancing Sample Utilization in Noise-Robust Deep Metric Learning With Subgroup-Based Positive-Pair Selection](https://mlsanity.com/paper/2501.11063/) (2025)
- [Instance-Level Generation for Representation Learning](https://mlsanity.com/paper/2510.09171/) (2025)
- [Realigned Softmax Warping for Deep Metric Learning](https://mlsanity.com/paper/2408.15656/) (2024)
- [Three Things to Know about Deep Metric Learning](https://mlsanity.com/paper/2412.12432/) (2024)
- [Partial VOROS: A Cost-aware Performance Metric for Binary Classifiers with Precision and Capacity Constraints](https://mlsanity.com/paper/2510.18520/) (2025)
- [Online Data Curation for Object Detection via Marginal Contributions to Dataset-level Average Precision](https://mlsanity.com/paper/2511.14197/) (2025)

## Abstract (arXiv)

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.