# On the Learnability of Multilabel Ranking

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 6 Apr 2023.

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

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Comparison of Deep Learning Approaches for Multi-Label Chest X-Ray Classification](https://mlsanity.com/paper/1803.02315/) (2018)
- [Deep Convolutional Ranking for Multilabel Image Annotation](https://mlsanity.com/paper/1312.4894/) (2013)
- [Exploit Bounding Box Annotations for Multi-label Object Recognition](https://mlsanity.com/paper/1504.05843/) (2015)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [A Structured Prediction Approach for Label Ranking](https://mlsanity.com/paper/1807.02374/) (2018)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [Online Boosting Algorithms for Multi-label Ranking](https://mlsanity.com/paper/1710.08079/) (2017)
- [Generalization error bounds for learning to rank: Does the length of document lists matter?](https://mlsanity.com/paper/1603.01860/) (2016)
- [A Characterization of Multioutput Learnability](https://mlsanity.com/paper/2301.02729/) (2023)
- [Online Ranking with Top-1 Feedback](https://mlsanity.com/paper/1410.1103/) (2014)

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

- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions](https://mlsanity.com/paper/2510.08382/) (2025)

## Abstract (arXiv)

Multilabel ranking is a central task in machine learning. However, the most fundamental question of learnability in a multilabel ranking setting with relevance-score feedback remains unanswered. In this work, we characterize the learnability of multilabel ranking problems in both batch and online settings for a large family of ranking losses. Along the way, we give two equivalence classes of ranking losses based on learnability that capture most, if not all, losses used in practice.