# Surrogate regret bounds for generalized classification performance metrics

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

## Key facts

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

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

- [Fair learning with Wasserstein barycenters for non-decomposable performance measures](https://mlsanity.com/paper/2209.00427/) (2022)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [A Minimax Probability Machine for Non-Decomposable Performance Measures](https://mlsanity.com/paper/2103.00396/) (2021)
- [Consistent algorithms for multi-label classification with macro-at-k metrics](https://mlsanity.com/paper/2401.16594/) (2024)
- [Curiosity Meets Cooperation: A Game-Theoretic Approach to Long-Tail Multi-Label Learning](https://mlsanity.com/paper/2510.17520/) (2025)
- [Proper losses regret at least 1/2-order](https://mlsanity.com/paper/2407.10417/) (2024)
- [A General Online Algorithm for Optimizing Complex Performance Metrics](https://mlsanity.com/paper/2406.14743/) (2024)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Skeptical binary inferences in multi-label problems with sets of probabilities](https://mlsanity.com/paper/2205.00662/) (2022)
- [A Scalable Curiosity-Driven Game-Theoretic Framework for Long-Tail Multi-Label Learning in Data Mining](https://mlsanity.com/paper/2602.15330/) (2026)
- [Beyond Surrogates: A Quantitative Analysis for Inter-Metric Relationships](https://mlsanity.com/paper/2603.07671/) (2026)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)
- [Weighted Score-Oriented Losses for Temporally Localized Event Prediction](https://mlsanity.com/paper/2606.23145/) (2026)

## Abstract (arXiv)

We consider optimization of generalized performance metrics for binary classification by means of surrogate losses. We focus on a class of metrics, which are linear-fractional functions of the false positive and false negative rates (examples of which include Fβ-measure, Jaccard similarity coefficient, AM measure, and many others). Our analysis concerns the following two-step procedure. First, a real-valued function f is learned by minimizing a surrogate loss for binary classification on the training sample. It is assumed that the surrogate loss is a strongly proper composite loss function (examples of which include logistic loss, squared-error loss, exponential loss, etc.). Then, given f, a threshold widehatθ is tuned on a separate validation sample, by direct optimization of the target performance metric. We show that the regret of the resulting classifier (obtained from thresholding f on widehatθ) measured with respect to the target metric is upperbounded by the regret of f measured with respect to the surrogate loss. We also extend our results to cover multilabel classification and provide regret bounds for micro- and macro-averaging measures. Our findings are further analyzed in a computational study on both synthetic and real data sets.