# Rethinking the Optimization of Average Precision: Only Penalizing Negative Instances before Positive Ones is Enough

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 48 references that are in the map.
- First posted on arXiv 9 Feb 2021.

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

- [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)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [NetVLAD: CNN architecture for weakly supervised place recognition](https://mlsanity.com/paper/1511.07247/) (2015)
- [Fine-tuning CNN Image Retrieval with No Human Annotation](https://mlsanity.com/paper/1711.02512/) (2017)
- [Deep Metric Learning via Lifted Structured Feature Embedding](https://mlsanity.com/paper/1511.06452/) (2015)
- [Circle Loss: A Unified Perspective of Pair Similarity Optimization](https://mlsanity.com/paper/2002.10857/) (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)
- [Learning Fine-grained Image Similarity with Deep Ranking](https://mlsanity.com/paper/1404.4661/) (2014)
- [Learning with Average Precision: Training Image Retrieval with a Listwise Loss](https://mlsanity.com/paper/1906.07589/) (2019)
- [SoftTriple Loss: Deep Metric Learning Without Triplet Sampling](https://mlsanity.com/paper/1909.05235/) (2019)
- [Deep Image Retrieval: Learning global representations for image search](https://mlsanity.com/paper/1604.01325/) (2016)
- [Cross-Batch Memory for Embedding Learning](https://mlsanity.com/paper/1912.06798/) (2019)
- [ProxyNCA++: Revisiting and Revitalizing Proxy Neighborhood Component Analysis](https://mlsanity.com/paper/2004.01113/) (2020)
- [Revisiting Training Strategies and Generalization Performance in Deep Metric Learning](https://mlsanity.com/paper/2002.08473/) (2020)
- [Smooth-AP: Smoothing the Path Towards Large-Scale Image Retrieval](https://mlsanity.com/paper/2007.12163/) (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 and aggregating deep local descriptors for instance-level recognition](https://mlsanity.com/paper/2007.13172/) (2020)
- [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)
- [DiVA: Diverse Visual Feature Aggregation for Deep Metric Learning](https://mlsanity.com/paper/2004.13458/) (2020)
- [Divide and Conquer the Embedding Space for Metric Learning](https://mlsanity.com/paper/1906.05990/) (2019)
- [SoDeep: a Sorting Deep net to learn ranking loss surrogates](https://mlsanity.com/paper/1904.04272/) (2019)
- [Hashing as Tie-Aware Learning to Rank](https://mlsanity.com/paper/1705.08562/) (2017)
- [Efficient Optimization for Rank-based Loss Functions](https://mlsanity.com/paper/1604.08269/) (2016)
- [Sharing Matters for Generalization in Deep Metric Learning](https://mlsanity.com/paper/2004.05582/) (2020)
- [Cross-Domain Image Retrieval with Attention Modeling](https://mlsanity.com/paper/1709.01784/) (2017)

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

- [Optimization of Rank Losses for Image Retrieval](https://mlsanity.com/paper/2309.08250/) (2023)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [X-ReID: Cross-Instance Transformer for Identity-Level Person Re-Identification](https://mlsanity.com/paper/2302.02075/) (2023)
- [MARs: Multi-view Attention Regularizations for Patch-based Feature Recognition of Space Terrain](https://mlsanity.com/paper/2410.05182/) (2024)

## Abstract (arXiv)

Optimizing the approximation of Average Precision (AP) has been widely studied for image retrieval. Limited by the definition of AP, such methods consider both negative and positive instances ranking before each positive instance. However, we claim that only penalizing negative instances before positive ones is enough, because the loss only comes from these negative instances. To this end, we propose a novel loss, namely Penalizing Negative instances before Positive ones (PNP), which can directly minimize the number of negative instances before each positive one. In addition, AP-based methods adopt a fixed and sub-optimal gradient assignment strategy. Therefore, we systematically investigate different gradient assignment solutions via constructing derivative functions of the loss, resulting in PNP-I with increasing derivative functions and PNP-D with decreasing ones. PNP-I focuses more on the hard positive instances by assigning larger gradients to them and tries to make all relevant instances closer. In contrast, PNP-D pays less attention to such instances and slowly corrects them. For most real-world data, one class usually contains several local clusters. PNP-I blindly gathers these clusters while PNP-D keeps them as they were. Therefore, PNP-D is more superior. Experiments on three standard retrieval datasets show consistent results with the above analysis. Extensive evaluations demonstrate that PNP-D achieves the state-of-the-art performance. Code is available at https://github.com/interestingzhuo/PNPloss