# Efficient Optimization for Rank-based Loss Functions

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2016.

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

- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [AutoLoss-Zero: Searching Loss Functions from Scratch for Generic Tasks](https://mlsanity.com/paper/2103.14026/) (2021)
- [Robust and Decomposable Average Precision for Image Retrieval](https://mlsanity.com/paper/2110.01445/) (2021)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (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)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities](https://mlsanity.com/paper/2111.02400/) (2021)
- [Learning a Cross-modality Anomaly Detector for Remote Sensing Imagery](https://mlsanity.com/paper/2310.07511/) (2023)
- [Rethinking the Optimization of Average Precision: Only Penalizing Negative Instances before Positive Ones is Enough](https://mlsanity.com/paper/2102.04640/) (2021)
- [Bucketed Ranking-based Losses for Efficient Training of Object Detectors](https://mlsanity.com/paper/2407.14204/) (2024)
- [Towards Practicality of Sketch-Based Visual Understanding](https://mlsanity.com/paper/2210.15146/) (2022)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)
- [CARE: Confidence-Aware Regression Estimation of building density fine-tuning EO Foundation Models](https://mlsanity.com/paper/2502.13734/) (2025)

## Abstract (arXiv)

The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time.