# Scalable Learning of Non-Decomposable Objectives

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2016.

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

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [On the Factory Floor: ML Engineering for Industrial-Scale Ads Recommendation Models](https://mlsanity.com/paper/2209.05310/) (2022)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification](https://mlsanity.com/paper/2108.10566/) (2021)
- [Net benefit, calibration, threshold selection, and training objectives for algorithmic fairness in healthcare](https://mlsanity.com/paper/2202.01906/) (2022)
- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [FORML: Learning to Reweight Data for Fairness](https://mlsanity.com/paper/2202.01719/) (2022)
- [Training Over-parameterized Models with Non-decomposable Objectives](https://mlsanity.com/paper/2107.04641/) (2021)
- [Leveraging Uncertainty for Improved Static Malware Detection Under Extreme False Positive Constraints](https://mlsanity.com/paper/2108.04081/) (2021)
- [Assessing the Sufficiency of Arguments through Conclusion Generation](https://mlsanity.com/paper/2110.13495/) (2021)
- [MetricOpt: Learning to Optimize Black-Box Evaluation Metrics](https://mlsanity.com/paper/2104.10631/) (2021)
- [Implicit Rate-Constrained Optimization of Non-decomposable Objectives](https://mlsanity.com/paper/2107.10960/) (2021)
- [Reliable Decision from Multiple Subtasks through Threshold Optimization: Content Moderation in the Wild](https://mlsanity.com/paper/2208.07522/) (2022)
- [Optimizing Black-box Metrics with Iterative Example Weighting](https://mlsanity.com/paper/2102.09492/) (2021)
- [Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities](https://mlsanity.com/paper/2111.02400/) (2021)
- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [A surrogate loss function for optimization of Fβ score in binary classification with imbalanced data](https://mlsanity.com/paper/2104.01459/) (2021)
- [A Minimax Probability Machine for Non-Decomposable Performance Measures](https://mlsanity.com/paper/2103.00396/) (2021)
- [Fine-Tuning Pretrained Language Models With Label Attention for Biomedical Text Classification](https://mlsanity.com/paper/2108.11809/) (2021)
- [Improving Out-of-Distribution Detection via Epistemic Uncertainty Adversarial Training](https://mlsanity.com/paper/2209.03148/) (2022)
- [Deep Multilabel CNN for Forensic Footwear Impression Descriptor Identification](https://mlsanity.com/paper/2102.05090/) (2021)
- [Attributing AUC-ROC to Analyze Binary Classifier Performance](https://mlsanity.com/paper/2205.11781/) (2022)
- [Selective Mixup Fine-Tuning for Optimizing Non-Decomposable Objectives](https://mlsanity.com/paper/2403.18301/) (2024)
- [Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification](https://mlsanity.com/paper/2507.15240/) (2025)
- [Eating Garlic Prevents COVID-19 Infection: Detecting Misinformation on the Arabic Content of Twitter](https://mlsanity.com/paper/2101.05626/) (2021)
- [Simple Weak Coresets for Non-Decomposable Classification Measures](https://mlsanity.com/paper/2312.09885/) (2023)
- [Counterexample-Guided Repair of Reinforcement Learning Systems Using Safety Critics](https://mlsanity.com/paper/2405.15430/) (2024)
- [Modeling and Controlling Deployment Reliability under Temporal Distribution Shift](https://mlsanity.com/paper/2604.02351/) (2026)

## Abstract (arXiv)

Modern retrieval systems are often driven by an underlying machine learning model. The goal of such systems is to identify and possibly rank the few most relevant items for a given query or context. Thus, such systems are typically evaluated using a ranking-based performance metric such as the area under the precision-recall curve, the Fβ score, precision at fixed recall, etc. Obviously, it is desirable to train such systems to optimize the metric of interest. In practice, due to the scalability limitations of existing approaches for optimizing such objectives, large-scale retrieval systems are instead trained to maximize classification accuracy, in the hope that performance as measured via the true objective will also be favorable. In this work we present a unified framework that, using straightforward building block bounds, allows for highly scalable optimization of a wide range of ranking-based objectives. We demonstrate the advantage of our approach on several real-life retrieval problems that are significantly larger than those considered in the literature, while achieving substantial improvement in performance over the accuracy-objective baseline.