We summarize the results in Table 1. In ranking literature, many evaluation metrics are often stated in terms of gain functions. When relevance scores are restricted to be binary (i.e. Before we do so, we need some more notation regarding F . By Proposition C.1, this implies that In this section, we prove Theorem 4.2 which characterizes the agnostic P AC learnability of an arbitrary hypothesis class We begin with Lemma C.2 which asserts that if for all ERM is an agnostic P AC learner for H w.r.t ` The proof of Lemma C.2 is similar to the proof of Lemma 4.3 and involves bounding the empirical Proposition C.1, this will imply that By Proposition C.1, this implies that Next, Lemma C.3 extends the learnability of The proof of Lemma C.3 follows the same the exact same strategy used in proving Lemma 4.4.

We summarize the results in Table 1. In ranking literature, many evaluation metrics are often stated in terms of gain functions. When relevance scores are restricted to be binary (i.e. Before we do so, we need some more notation regarding F . By Proposition C.1, this implies that In this section, we prove Theorem 4.2 which characterizes the agnostic P AC learnability of an arbitrary hypothesis class We begin with Lemma C.2 which asserts that if for all ERM is an agnostic P AC learner for H w.r.t ` The proof of Lemma C.2 is similar to the proof of Lemma 4.3 and involves bounding the empirical Proposition C.1, this will imply that By Proposition C.1, this implies that Next, Lemma C.3 extends the learnability of The proof of Lemma C.3 follows the same the exact same strategy used in proving Lemma 4.4.

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.