# Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 38 references that are in the map.
- First posted on arXiv 10 May 2021.

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

- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [A Unified View of Multi-Label Performance Measures](https://mlsanity.com/paper/1609.00288/) (2016)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (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)
- [Multi-label classification: do Hamming loss and subset accuracy really conflict with each other?](https://mlsanity.com/paper/2011.07805/) (2020)
- [Joint Ranking SVM and Binary Relevance with Robust Low-Rank Learning for Multi-Label Classification](https://mlsanity.com/paper/1911.01658/) (2019)

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

- [In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer](https://mlsanity.com/paper/2311.01106/) (2023)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [Towards Understanding Generalization of Macro-AUC in Multi-label Learning](https://mlsanity.com/paper/2305.05248/) (2023)
- [QAMRO: Quality-aware Adaptive Margin Ranking Optimization for Human-aligned Assessment of Audio Generation Systems](https://mlsanity.com/paper/2508.08957/) (2025)
- [Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation](https://mlsanity.com/paper/2504.11284/) (2025)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)
- [GaussianMLR: Learning Implicit Class Significance via Calibrated Multi-Label Ranking](https://mlsanity.com/paper/2303.03907/) (2023)
- [UniMLR: Modeling Implicit Class Significance for Multi-Label Ranking](https://mlsanity.com/paper/2508.21772/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)

## Abstract (arXiv)

(Partial) ranking loss is a commonly used evaluation measure for multi-label classification, which is usually optimized with convex surrogates for computational efficiency. Prior theoretical work on multi-label ranking mainly focuses on (Fisher) consistency analyses. However, there is a gap between existing theory and practice -- some pairwise losses can lead to promising performance but lack consistency, while some univariate losses are consistent but usually have no clear superiority in practice. In this paper, we attempt to fill this gap through a systematic study from two complementary perspectives of consistency and generalization error bounds of learning algorithms. Our results show that learning algorithms with the consistent univariate loss have an error bound of O(c) (c is the number of labels), while algorithms with the inconsistent pairwise loss depend on O(√c) as shown in prior work. This explains that the latter can achieve better performance than the former in practice. Moreover, we present an inconsistent reweighted univariate loss-based learning algorithm that enjoys an error bound of O(√c) for promising performance as well as the computational efficiency of univariate losses. Finally, experimental results validate our theoretical analyses.