A Categorizing Popular Ranking Losses Table 1: Categorizing Popular Ranking Losses. Loss Loss Family Sum Loss@p L (`

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.