# Multi-Label Learning with Stronger Consistency Guarantees

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 66 references that are in the map.
- First posted on arXiv 18 Jul 2024.

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

- [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)
- [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)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [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)
- [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)
- [A Finer Calibration Analysis for Adversarial Robustness](https://mlsanity.com/paper/2105.01550/) (2021)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Structured Prediction Theory Based on Factor Graph Complexity](https://mlsanity.com/paper/1605.06443/) (2016)
- [Convex Calibrated Surrogates for the Multi-Label F-Measure](https://mlsanity.com/paper/2009.07801/) (2020)
- [On the Bayes-optimality of F-measure maximizers](https://mlsanity.com/paper/1310.4849/) (2013)
- [Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization](https://mlsanity.com/paper/2105.05026/) (2021)
- [Top-k Classification and Cardinality-Aware Prediction](https://mlsanity.com/paper/2403.19625/) (2024)
- [Towards Understanding Generalization of Macro-AUC in Multi-label Learning](https://mlsanity.com/paper/2305.05248/) (2023)

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

- [A Two-Stage Learning-to-Defer Approach for Multi-Task Learning](https://mlsanity.com/paper/2410.15729/) (2024)
- [Adversarial Robustness in Two-Stage Learning-to-Defer: Algorithms and Guarantees](https://mlsanity.com/paper/2502.01027/) (2025)
- [Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer](https://mlsanity.com/paper/2506.20650/) (2025)
- [Optimal Query Allocation in Extractive QA with LLMs: A Learning-to-Defer Framework with Theoretical Guarantees](https://mlsanity.com/paper/2410.15761/) (2024)
- [Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data](https://mlsanity.com/paper/2502.10381/) (2025)
- [Budgeted Multiple-Expert Deferral](https://mlsanity.com/paper/2510.26706/) (2025)
- [Improved Balanced Classification with Theoretically Grounded Loss Functions](https://mlsanity.com/paper/2512.23947/) (2025)
- [Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Experts](https://mlsanity.com/paper/2504.12988/) (2025)
- [Beyond Tsybakov: Model Margin Noise and H-Consistency Bounds](https://mlsanity.com/paper/2511.15816/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [Probably Approximately Precision and Recall Learning](https://mlsanity.com/paper/2411.13029/) (2024)
- [Adversarial Robustness in One-Stage Learning-to-Defer](https://mlsanity.com/paper/2510.10988/) (2025)
- [A Theoretical Framework for Modular Learning of Robust Generative Models](https://mlsanity.com/paper/2602.17554/) (2026)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Optimized Deferral for Imbalanced Settings](https://mlsanity.com/paper/2604.27723/) (2026)
- [Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction](https://mlsanity.com/paper/2604.27742/) (2026)
- [Online Set Learning from Precision and Recall Feedback](https://mlsanity.com/paper/2605.09565/) (2026)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [Multi-Label Scene Classification in Remote Sensing Benefits from Image Super-Resolution](https://mlsanity.com/paper/2501.06720/) (2025)
- [Any-Class Presence Likelihood for Robust Multi-Label Classification with Abundant Negative Data](https://mlsanity.com/paper/2506.05721/) (2025)
- [Some Robustness Properties of Label Cleaning](https://mlsanity.com/paper/2509.11379/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)

## Abstract (arXiv)

We present a detailed study of surrogate losses and algorithms for multi-label learning, supported by H-consistency bounds. We first show that, for the simplest form of multi-label loss (the popular Hamming loss), the well-known consistent binary relevance surrogate suffers from a sub-optimal dependency on the number of labels in terms of H-consistency bounds, when using smooth losses such as logistic losses. Furthermore, this loss function fails to account for label correlations. To address these drawbacks, we introduce a novel surrogate loss, multi-label logistic loss, that accounts for label correlations and benefits from label-independent H-consistency bounds. We then broaden our analysis to cover a more extensive family of multi-label losses, including all common ones and a new extension defined based on linear-fractional functions with respect to the confusion matrix. We also extend our multi-label logistic losses to more comprehensive multi-label comp-sum losses, adapting comp-sum losses from standard classification to the multi-label learning. We prove that this family of surrogate losses benefits from H-consistency bounds, and thus Bayes-consistency, across any general multi-label loss. Our work thus proposes a unified surrogate loss framework benefiting from strong consistency guarantees for any multi-label loss, significantly expanding upon previous work which only established Bayes-consistency and for specific loss functions. Additionally, we adapt constrained losses from standard classification to multi-label constrained losses in a similar way, which also benefit from H-consistency bounds and thus Bayes-consistency for any multi-label loss. We further describe efficient gradient computation algorithms for minimizing the multi-label logistic loss.