# Optimizing Non-decomposable Performance Measures: A Tale of Two Classes

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2015.

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

- [Fair learning with Wasserstein barycenters for non-decomposable performance measures](https://mlsanity.com/paper/2209.00427/) (2022)
- [sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification](https://mlsanity.com/paper/2108.10566/) (2021)
- [Training Over-parameterized Models with Non-decomposable Objectives](https://mlsanity.com/paper/2107.04641/) (2021)
- [Implicit Rate-Constrained Optimization of Non-decomposable Objectives](https://mlsanity.com/paper/2107.10960/) (2021)
- [Optimizing Black-box Metrics with Iterative Example Weighting](https://mlsanity.com/paper/2102.09492/) (2021)
- [Generalized Group Data Attribution](https://mlsanity.com/paper/2410.09940/) (2024)
- [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)
- [A comprehensive theoretical framework for the optimization of neural networks classification performance with respect to weighted metrics](https://mlsanity.com/paper/2305.13472/) (2023)
- [Selective Mixup Fine-Tuning for Optimizing Non-Decomposable Objectives](https://mlsanity.com/paper/2403.18301/) (2024)
- [A General Online Algorithm for Optimizing Complex Performance Metrics](https://mlsanity.com/paper/2406.14743/) (2024)
- [Simple Weak Coresets for Non-Decomposable Classification Measures](https://mlsanity.com/paper/2312.09885/) (2023)
- [Probabilistic Consistency in Machine Learning and Its Connection to Uncertainty Quantification](https://mlsanity.com/paper/2507.21670/) (2025)
- [Inequalities for Optimization of Classification Algorithms: A Perspective Motivated by Diagnostic Testing](https://mlsanity.com/paper/2508.01065/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)
- [Bayes-Optimal BER and AUC: Estimation and Evaluation of Estimators](https://mlsanity.com/paper/2609.02304/) (2026)
- [From Sampled Evidence to Radiology Reports: Objectives, Constraints, and Realization](https://mlsanity.com/paper/2610.17318/) (2026)

## Abstract (arXiv)

Modern classification problems frequently present mild to severe label imbalance as well as specific requirements on classification characteristics, and require optimizing performance measures that are non-decomposable over the dataset, such as F-measure. Such measures have spurred much interest and pose specific challenges to learning algorithms since their non-additive nature precludes a direct application of well-studied large scale optimization methods such as stochastic gradient descent. In this paper we reveal that for two large families of performance measures that can be expressed as functions of true positive/negative rates, it is indeed possible to implement point stochastic updates. The families we consider are concave and pseudo-linear functions of TPR, TNR which cover several popularly used performance measures such as F-measure, G-mean and H-mean. Our core contribution is an adaptive linearization scheme for these families, using which we develop optimization techniques that enable truly point-based stochastic updates. For concave performance measures we propose SPADE, a stochastic primal dual solver; for pseudo-linear measures we propose STAMP, a stochastic alternate maximization procedure. Both methods have crisp convergence guarantees, demonstrate significant speedups over existing methods - often by an order of magnitude or more, and give similar or more accurate predictions on test data.