# Optimizing ROC Curves with a Sort-Based Surrogate Loss Function for Binary Classification and Changepoint Detection

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 45 references that are in the map.
- First posted on arXiv 2 Jul 2021.

## Builds on (most cited first, 6 of 6)

- [An Evaluation of Change Point Detection Algorithms](https://mlsanity.com/paper/2003.06222/) (2020)
- [Survival regression with accelerated failure time model in XGBoost](https://mlsanity.com/paper/2006.04920/) (2020)
- [On Optimal Multiple Changepoint Algorithms for Large Data](https://mlsanity.com/paper/1409.1842/) (2014)
- [Maximum Margin Interval Trees](https://mlsanity.com/paper/1710.04234/) (2017)
- [Increased peak detection accuracy in over-dispersed ChIP-seq data with supervised segmentation models](https://mlsanity.com/paper/2012.06848/) (2020)
- [Linear time dynamic programming for the exact path of optimal models selected from a finite set](https://mlsanity.com/paper/2003.02808/) (2020)

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

- [Sample Efficient Experience Replay in Non-stationary Environments](https://mlsanity.com/paper/2509.15032/) (2025)

## Abstract (arXiv)

Receiver Operating Characteristic (ROC) curves are plots of true positive rate versus false positive rate which are useful for evaluating binary classification models, but difficult to use for learning since the Area Under the Curve (AUC) is non-convex. ROC curves can also be used in other problems that have false positive and true positive rates such as changepoint detection. We show that in this more general context, the ROC curve can have loops, points with highly sub-optimal error rates, and AUC greater than one. This observation motivates a new optimization objective: rather than maximizing the AUC, we would like a monotonic ROC curve with AUC=1 that avoids points with large values for Min(FP,FN). We propose a convex relaxation of this objective that results in a new surrogate loss function called the AUM, short for Area Under Min(FP, FN). Whereas previous loss functions are based on summing over all labeled examples or pairs, the AUM requires a sort and a sum over the sequence of points on the ROC curve. We show that AUM directional derivatives can be efficiently computed and used in a gradient descent learning algorithm. In our empirical study of supervised binary classification and changepoint detection problems, we show that our new AUM minimization learning algorithm results in improved AUC and comparable speed relative to previous baselines.