# Convex Calibrated Surrogates for the Multi-Label F-Measure

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2020.

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Ranking with Abstention](https://mlsanity.com/paper/2307.02035/) (2023)
- [In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer](https://mlsanity.com/paper/2311.01106/) (2023)
- [sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification](https://mlsanity.com/paper/2108.10566/) (2021)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Neural Collapse in Multi-label Learning with Pick-all-label Loss](https://mlsanity.com/paper/2310.15903/) (2023)
- [Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization](https://mlsanity.com/paper/2105.05026/) (2021)
- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [Towards Understanding Generalization of Macro-AUC in Multi-label Learning](https://mlsanity.com/paper/2305.05248/) (2023)
- [Multiclass Learning from Noisy Labels for Non-decomposable Performance Measures](https://mlsanity.com/paper/2402.01055/) (2024)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss](https://mlsanity.com/paper/2608.08399/) (2026)
- [Aligning Multiclass Neural Network Classifier Criterion with Task Performance Metrics](https://mlsanity.com/paper/2405.20954/) (2024)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)
- [Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure](https://mlsanity.com/paper/2608.13549/) (2026)

## Abstract (arXiv)

The F-measure is a widely used performance measure for multi-label classification, where multiple labels can be active in an instance simultaneously (e.g. in image tagging, multiple tags can be active in any image). In particular, the F-measure explicitly balances recall (fraction of active labels predicted to be active) and precision (fraction of labels predicted to be active that are actually so), both of which are important in evaluating the overall performance of a multi-label classifier. As with most discrete prediction problems, however, directly optimizing the F-measure is computationally hard. In this paper, we explore the question of designing convex surrogate losses that are calibrated for the F-measure -- specifically, that have the property that minimizing the surrogate loss yields (in the limit of sufficient data) a Bayes optimal multi-label classifier for the F-measure. We show that the F-measure for an s-label problem, when viewed as a 2s × 2s loss matrix, has rank at most s2+1, and apply a result of Ramaswamy et al. (2014) to design a family of convex calibrated surrogates for the F-measure. The resulting surrogate risk minimization algorithms can be viewed as decomposing the multi-label F-measure learning problem into s2+1 binary class probability estimation problems. We also provide a quantitative regret transfer bound for our surrogates, which allows any regret guarantees for the binary problems to be transferred to regret guarantees for the overall F-measure problem, and discuss a connection with the algorithm of Dembczynski et al. (2013). Our experiments confirm our theoretical findings.