# Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 55 of its 116 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 30 of 55)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels](https://mlsanity.com/paper/1805.07836/) (2018)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [Asymmetric Loss For Multi-Label Classification](https://mlsanity.com/paper/2009.14119/) (2020)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Large-scale Multi-label Learning with Missing Labels](https://mlsanity.com/paper/1307.5101/) (2013)
- [A no-regret generalization of hierarchical softmax to extreme multi-label classification](https://mlsanity.com/paper/1810.11671/) (2018)
- [Scalable Learning of Non-Decomposable Objectives](https://mlsanity.com/paper/1608.04802/) (2016)
- [Comprehensive Comparative Study of Multi-Label Classification Methods](https://mlsanity.com/paper/2102.07113/) (2021)
- [Principled Approaches for Learning to Defer with Multiple Experts](https://mlsanity.com/paper/2310.14774/) (2023)
- [A Unified View of Multi-Label Performance Measures](https://mlsanity.com/paper/1609.00288/) (2016)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [Learning to Reject with a Fixed Predictor: Application to Decontextualization](https://mlsanity.com/paper/2301.09044/) (2023)
- [Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention](https://mlsanity.com/paper/2310.14770/) (2023)
- [Regression with Multi-Expert Deferral](https://mlsanity.com/paper/2403.19494/) (2024)
- [Ranking with Abstention](https://mlsanity.com/paper/2307.02035/) (2023)
- [Realizable H-Consistent and Bayes-Consistent Loss Functions for Learning to Defer](https://mlsanity.com/paper/2407.13732/) (2024)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification](https://mlsanity.com/paper/2108.10566/) (2021)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [Online and Stochastic Gradient Methods for Non-decomposable Loss Functions](https://mlsanity.com/paper/1410.6776/) (2014)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Deep Learning for Multi-Label Learning: A Comprehensive Survey](https://mlsanity.com/paper/2401.16549/) (2024)
- [Optimizing Non-decomposable Performance Measures: A Tale of Two Classes](https://mlsanity.com/paper/1505.06812/) (2015)
- [Convex Calibrated Surrogates for the Multi-Label F-Measure](https://mlsanity.com/paper/2009.07801/) (2020)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [On the Bayes-optimality of F-measure maximizers](https://mlsanity.com/paper/1310.4849/) (2013)

## Abstract (arXiv)

Many real-world classification tasks require predicting multiple labels per instance, necessitating the optimization of complex evaluation metrics such as the F-measure and Jaccard index. While the Empirical Utility Maximization (EUM) framework is natural for these population-level metrics, existing theoretical results are largely limited to asymptotic Bayes-consistency. In this paper, we develop principled learning algorithms for optimizing a broad class of generalized metrics within the EUM framework, grounded in the stronger notion of H-consistency. Our key contribution is the design of novel surrogate loss functions for multi-label learning that admit provable H-consistency bounds, enabling optimization with non-asymptotic guarantees tailored to the hypothesis class and finite samples. Crucially, we prove these combinatorially formulated surrogates decompose exactly, operating in strictly O(l) time without approximations. Building on this foundation, we introduce MMO (Multi-Label Metric Optimization), a new family of algorithms for optimizing generalized linear-fractional metrics. We validate our approach through extensive experiments, demonstrating robust scalability and superior performance over state-of-the-art continuous baselines on large-scale datasets (MS-COCO, Reuters-21578) in high-sparsity, deep learning regimes. Our results offer both theoretical rigor and practical effectiveness for general multi-label metric optimization.