Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning
Not on the map. Why?
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.
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
55 of 116 references.
References · 55
- 2015Deep Residual Learning for Image Recognitioncited by 52,096
- 2014Microsoft COCO: Common Objects in Contextcited by 17,608
- 2019DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lightercited by 4,307
- 2018Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labelscited by 997
- 2017Robust Loss Functions under Label Noise for Deep Neural Networkscited by 443
- 2020Asymmetric Loss For Multi-Label Classificationcited by 381
- 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 210
- 2013Large-scale Multi-label Learning with Missing Labelscited by 58
- 2018A no-regret generalization of hierarchical softmax to extreme multi-label classificationcited by 52
- 2016Scalable Learning of Non-Decomposable Objectivescited by 41
- 2021Comprehensive Comparative Study of Multi-Label Classification Methodscited by 38
- 2023Principled Approaches for Learning to Defer with Multiple Expertscited by 38
38 more
- 2016A Unified View of Multi-Label Performance Measurescited by 36
- 2023Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithmscited by 36
- 2023Learning to Reject with a Fixed Predictor: Application to Decontextualizationcited by 32
- 2023Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstentioncited by 32
- 2024Regression with Multi-Expert Deferralcited by 29
- 2023Ranking with Abstentioncited by 27
- 2024Realizable H-Consistent and Bayes-Consistent Loss Functions for Learning to Defercited by 26
- 2024A Universal Growth Rate for Learning with Smooth Surrogate Lossescited by 24
- 2021sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classificationcited by 23
- 2024Cardinality-Aware Set Prediction and Top-k Classificationcited by 23
- 2024Multi-Label Learning with Stronger Consistency Guaranteescited by 22
- 2014Online and Stochastic Gradient Methods for Non-decomposable Loss Functionscited by 21
- 2024H-Consistency Guarantees for Regressioncited by 21
- 2024Deep Learning for Multi-Label Learning: A Comprehensive Surveycited by 19
- 2015Optimizing Non-decomposable Performance Measures: A Tale of Two Classescited by 18
- 2020Convex Calibrated Surrogates for the Multi-Label F-Measurecited by 18
- 2024Enhanced H-Consistency Boundscited by 18
- 2013On the Bayes-optimality of F-measure maximizerscited by 16
- 2025Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defercited by 16
- 2025Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Datacited by 15
- 2015Surrogate regret bounds for generalized classification performance metricscited by 14
- 2020Multi-label classification: do Hamming loss and subset accuracy really conflict with each other?cited by 14
- 2022Consistent Multiclass Algorithms for Complex Metrics and Constraintscited by 13
- 2025Budgeted Multiple-Expert Deferralcited by 13
- 2018Binary Classification with Karmic, Threshold-Quasi-Concave Metricscited by 11
- 2018Optimizing Non-decomposable Measures with Deep Networkscited by 10
- 2019Calibrated Surrogate Maximization of Linear-fractional Utility in Binary Classificationcited by 10
- 2021Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalizationcited by 9
- 2025Improved Balanced Classification with Theoretically Grounded Loss Functionscited by 9
- 2019AP-Perf: Incorporating Generic Performance Metrics in Differentiable Learningcited by 8
- 2025Theory and Algorithms for Learning with Multi-Class Abstention and Multi-Expert Deferralcited by 8
- 2025Beyond Tsybakov: Model Margin Noise and H-Consistency Boundscited by 7
- 2025Fundamental Novel Consistency Theory: H-Consistency Boundscited by 6
- 2025Principled Algorithms for Optimizing Generalized Metrics in Binary Classificationcited by 6
- 2021A Minimax Probability Machine for Non-Decomposable Performance Measurescited by 4
- 2023Towards Understanding Generalization of Macro-AUC in Multi-label Learningcited by 4
- 2024Consistent algorithms for multi-label classification with macro-at-k metricscited by 4
- 2026A Theoretical Framework for Modular Learning of Robust Generative Modelscited by 4
50 most cited of 55 All 55 (JSON)
Built on by
Not cited yet.