# Optimizing Rank-based Metrics with Blackbox Differentiation

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2019.

## Built on by (most cited first, 30 of 58)

- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [LVM-Med: Learning Large-Scale Self-Supervised Vision Models for Medical Imaging via Second-order Graph Matching](https://mlsanity.com/paper/2306.11925/) (2023)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [RankSim: Ranking Similarity Regularization for Deep Imbalanced Regression](https://mlsanity.com/paper/2205.15236/) (2022)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [Recall@k Surrogate Loss with Large Batches and Similarity Mixup](https://mlsanity.com/paper/2108.11179/) (2021)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Rank & Sort Loss for Object Detection and Instance Segmentation](https://mlsanity.com/paper/2107.11669/) (2021)
- [Learning with Algorithmic Supervision via Continuous Relaxations](https://mlsanity.com/paper/2110.05651/) (2021)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Robust and Decomposable Average Precision for Image Retrieval](https://mlsanity.com/paper/2110.01445/) (2021)
- [RankED: Addressing Imbalance and Uncertainty in Edge Detection Using Ranking-based Losses](https://mlsanity.com/paper/2403.01795/) (2024)
- [Learning Where To Look -- Generative NAS is Surprisingly Efficient](https://mlsanity.com/paper/2203.08734/) (2022)
- [LibAUC: A Deep Learning Library for X-Risk Optimization](https://mlsanity.com/paper/2306.03065/) (2023)
- [Self-Supervised Learning of Audio Representations from Permutations with Differentiable Ranking](https://mlsanity.com/paper/2103.09879/) (2021)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Long-tail Detection with Effective Class-Margins](https://mlsanity.com/paper/2301.09724/) (2023)
- [Neuro-algorithmic Policies enable Fast Combinatorial Generalization](https://mlsanity.com/paper/2102.07456/) (2021)
- [Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach](https://mlsanity.com/paper/2106.03188/) (2021)
- [Optimization of Rank Losses for Image Retrieval](https://mlsanity.com/paper/2309.08250/) (2023)
- [MetricOpt: Learning to Optimize Black-Box Evaluation Metrics](https://mlsanity.com/paper/2104.10631/) (2021)
- [IKOL: Inverse kinematics optimization layer for 3D human pose and shape estimation via Gauss-Newton differentiation](https://mlsanity.com/paper/2302.01058/) (2023)
- [Not All Pairs are Equal: Hierarchical Learning for Average-Precision-Oriented Video Retrieval](https://mlsanity.com/paper/2407.15566/) (2024)
- [Total Variation Optimization Layers for Computer Vision](https://mlsanity.com/paper/2204.03643/) (2022)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [Hierarchical Average Precision Training for Pertinent Image Retrieval](https://mlsanity.com/paper/2207.04873/) (2022)

## Abstract (arXiv)

Rank-based metrics are some of the most widely used criteria for performance evaluation of computer vision models. Despite years of effort, direct optimization for these metrics remains a challenge due to their non-differentiable and non-decomposable nature. We present an efficient, theoretically sound, and general method for differentiating rank-based metrics with mini-batch gradient descent. In addition, we address optimization instability and sparsity of the supervision signal that both arise from using rank-based metrics as optimization targets. Resulting losses based on recall and Average Precision are applied to image retrieval and object detection tasks. We obtain performance that is competitive with state-of-the-art on standard image retrieval datasets and consistently improve performance of near state-of-the-art object detectors. The code is available at https://github.com/martius-lab/blackbox-backprop