  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.
