On the Learnability of Multilabel Ranking
Authors: Vinod Raman
UNIQUE SUBEDI
Ambuj Tewari
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Multilabel Ranking
PAC Learning
Online Learning
TL;DR: We give a characterization of learnability for multilabel ranking problems.

Abstract: 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 losses used in practice.

On the Learnability of Multilabel Ranking
Vinod Raman' Department Statistics University of Michigan Ann Arbor, MI 48104 vkraman@umich. edu
Unique Subedi" Department of Statisties University of Michigan Ann Arbor, MI 48104 subedi @umi ch. edu
Ambuj Tewari
Department of Statistics University of Michigan Ann Arbor, MI 48104 tewaria@umi edu
Abstract
Multilabel ranking is 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, give equivalence classes of ranking losses based on learnability that capture most losses used in practice.
Introduction
Multilabel ranking is a supervised learning problem where a learner is presented with an instance X and is required output ranking of K different labels in decreasing order of relevance to tt. This is in contrast with multilabel classification where given an instance & E X. the learner is tasked with predicting subset of the K labels without any explicit ordering. Multilabel ranking is a canonical learning problem with a wide range of applications to text categorization, genetics,
medical imaging, social networks, and visual object recognition (Joachims 2005 [cchapire and
Singer [2000] McCallum 1999 [Clae and King 2001 Baltruschat et al. 2019 Wang and Sukthankar
2013 Bucak et al., 2009 Yang al. 2016). Recent years have seen surge in the development of multilbbll ranking methods with strong practical and theoretical guarantees [Schapire and Singer
2000 Dembezynski et al., 2012 Gong al. 2013 Bucak al.
2009 Jung and Tewari 2018 Gao
and Zhou 2011 Koyejo et al. 2015 Zhang and Zhou 2013 Korba et al. 2018]. A related line of work has studied consistency for convex surrogates of natural ranking losses [Duchi al.
2010, Buffoni et al. 2011 1 Gao and Zhou, 2011
Ravikumar et al., 2011 Calauzenes et al.) 2012
Dembezynski al. 2012). Despite this vast literature on multilabel ranking, the fundamental question of when multilabel ranking problem is learnable remains unanswered.
Understanding when hypothesis class is learnable is fundamental question in Statistical Learn- ing Theory. For binary classification, the finiteness of the Sopmik-Chervonenkis (VC) dimension both sufficient and necessary for Probably Approximately Correct (PAC) learning /Vannik and
Chervonenkis 1974 Valiant 1984). Likewise, the finiteness of the Daniely -hwirryy-S-rrzzzz (DS) dimension
characterizes multiclass PAC learnability Daniely and Shaley-Shwartz (2014). Brukhim et al. 2022].
In the online setting, the Littlestone dimension [Littlssonne| [987] characterizes the online lcarnability of a binary hypothesis class and the multiclass Littlestone dimension (Daniely et al., 2011] charac- terizes online multiclass learnability. Unlike classification, distinguishing property of multilabel ranking the mismatch between the predictions the learner makes and the feedback receives. In particular, learner required to produce permutation that ranks the relevance of the labels but only receives a relevance-score vector as feedback. This feedback model is standard in multilabel ranking since obtaining full permutation feedback is generally costly [Liu et al. 2009). As result, unlike the 0-1 loss in classification, there is no canonical loss function in ranking. Together, these two issues
Equual contributions
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

create barriers for existing techniques used to prove learnability, such as the agnostic- to- to-realizable reductions from Hopkins al. [022] and Raman al. [2023] to readily extend to ranking.
In this paper, we characterize the batch and online learnability of a ranking hypothesis class H. C S
under relevance-score feedback, where Sx is the set of all permutations over [K] {1 . K} In doing so, we make the following contributions.
We show that a ranking hypothesis class H. embeds K² different binary hypothesis classes Hi for j.j [K], where hypotheses in Hi answer whether the label should be ranked in the top j. Our main result relates the learnability of H. to the learnability of H
We define two families of ranking loss functions that capture most if not all ranking losses used in practice. We show that these families are actually equivalence classes the same characterization of batch and online learnability holds for every loss in that family.
By relating the learnability of H to the learnability of binary hypothesis classes H.. we show that existing combinatorial dimensions, like the VC and Littlestone dimension, continue to characterize learnability the multilabel ranking setting. This allows us to prove that linear ranking hypothesis classes are learnable in the batch setting.
A unifying theme throughout the paper is our ability to constructively convert a learning algorithm A for H. into learning algorithm A² for Hi for each i.j E [K] and vice versa. To do so, our proof reduction for batch and online classification, proposed by Hopkins et al. [022 and Raman et al. [2023] respectively, to ranking.
techniques involve adapting the cenootticto-realizile
Preliminaries and Notation
Let X' denote the instance space, SK the set of permutations over labels [K] := KJ. and
y (0, I,.,, BJ the target space for some K E N. We highlight that the set of labels [K] is fixed beforehand and does not depend on the instance ranking, the set of labels can change depending on the instance x E X.
X. This is to be contrasted with subset
We refer to an element y E y as relevance score vector that indicates the relevance of each of the K labels, where indicates the highest relevance and indicates the lowest relevance. Throughout the paper, we treat permutation E Sx as vector in (1...., K)K that induces ranking of the K labels decreasing order of relevance. Accordingly, for an index E [K], we let m, E [K] denote the rank of label i. Likewise, given index E [K]. we let y denote the relevance of label i. In addition, it will be useful to define a mapping from SK to {0, 1)xs. In particular, we define BinRel(-, : -) SK [K] - {0, 1 as operator that given a permutation (ranking) SK and threshold p E [K]. outputs a bit string b E {0, 1] s.t. b; = 1[ S s}.
Ranking Equivalences. Our construction of ranking loss families in Section 3 requires different notions of equivalence between permutations (rankings) in Sx. To that end, we say that = â if and only if for all i [K], n; ã. On the other hand, we say E A if and only if (i m. S p) = (i: म. S p}. That is, two rankings are p-equivalent if the set of labels they rank in the top-p are equal. Finally, we say
[p) A if and only if for all E [p). (i: n, S j} (i n S j}. That is, two rankings are -qluvvaial if not only the set but also the order of labels they rank the top-p are equal.
Ranking Hypothesis. A ranking hypothesis h E H C S maps instances in X to ranking
(permutation) in Sk. Given an instance x E X, one can think of h(x) as h's ranking of the K different labels in decreasing order of relevance. For any ranking hypothesis h, we let h, X + [K] denote its restriction to the i'th coordinate output. Accordingly, for an instance gives the rank that h assigns to label i. Given a ranking hypothesis class H. C S and any i E [K),
E X, (1)
define its binary threshold-restrrited hypothesis class H. (h₃ h E H) where 1 (x) = (h) < j). We can think of hypotheses in Hi as providing binary responses to queries of the form: "for instance v, should label ranked in the top j?" These threshold-restricteed classes are central to our characterization of learnability in both the batch and online learning settings.
2

---

Batch Learnability. In the batch setting, we are interested in characterizing the learnability of ranking hypothesis class H. under a model similar the classical PAC model Valiaat [984].
Definition (Agnostic Ranking PAC Learnability). ranking hypothesis class H. C S is agnostic PAC learnable w.r.. loss é Sk x y + Rz0. if there exists function m (0, 1). x N + N and
learning algorithm A (X' x y)* - S with the following property: for every c, E (0, 1) and for every distribution D X Y, running algorithm A on n. Z m(e, 6, K) iid samples from DD outputs a predictor A(S) such that with probability at least - å over S ~ D",
ED ((()(1(z); v)1 S inf ED (((((()))))))))) +e.
NER
If 'D is restricted to the class of distributions such that inf Ep (((())), y)] = 0. then say are in the realizable setting. Note that unlike in classification, realizability in the multilabel ranking setting is loss dependent.
Online Learnability. In the online setting, adversary plays sequential game with the learner over T rounds. In each round & E [2]. an adversary selects a labeled instance (It, Mr) E X y and reveals to the learner. The learner makes a (potentially randomized) prediction #. E Sk. Finally, the adversary reveals the true relevance-score vector yt. and the learner suffers the loss E(ft.3) ye)- where é is some pre-specified ranking loss function. Given ranking hypothesis class H C Sk the goal of the learner is to output predictions ât such that its cumulative loss is close to the best possible cumulative loss over hypotheses in H. A hypothesis class is online learnable if there exists an algorithm such that for any sequence of labeled examples (x), (01, yi)..., (IT, /r ). the difference in cumulative loss between its predictions and the predictions of the best possible function in H. is small.
Definition 2 (Agnostic Online Ranking Learnability). A ranking hypothesis class H. S S is agnostic online learnable w.r.t. loss if there exists an (potentially randomized) algorithm such that for any adaptively chosen sequence of labeled examples (I1, ve) E X Y, the algorithm outputs A(ra) E SK at every iteration t E (T) such that its expected regret,
R(T,K) := e(A(z)) vo) inf Σ (((h(z)).0))
NEH
is non-decreasing, sub-linear function Tf Here, the expectation is taken with respect to the randomness of the algorithm A.
If it is further guaranteed that there exists hypothesis h- E H. such that Σ E(h* (xz). = 0. then we say we are in the realizable setting. Again, realizability loss dependent.
Ranking Loss Families
In statistical learning theory, we often characterize learnability with respect loss function. Unlike the 0)1 loss in classification, there is no canonical loss function in multilabel ranking. Accordingly, we define general families of ranking loss functions in this section and later characterize learnability with respect to all losses in these families. In Appendix A we show that many of the ranking metrics used in practice (e.g. Pairwise Rank Loss, Discounted Cumulative Gain, Reciprocal Rank, Average Precision, Precision @ etc.) fall into one of these two families.
On high level, can classify ranking losses into two main groups: (A) those losses that care about both the order and magnitude of the relevance scores within the top-p ranked labels and (B) those losses that only goal will be to define a loss family for both groups and B. To do so, we start by identifying a canonical ranking loss that lies in each group. For group A, the normalized sum loss
about the magnitude of the relevance scores within the top-p ranked labels. Our
Ca sum (T, y)
Σ min(T;, p 1)y² z
captures both the order and magnitude of the relevance scores only for the top-p ranked labels. Here, 2 is an appropriately chosen normalization factor that only depends on and y such that
3

---

BP (x, v) O. For Group B, the normalized precision loss @p.
Gig pree n, (T,)) Zz
Σ 1(m; S ply
cares only about the magnitude of relevance scores in the top-p ranked labels. Again, Zy is an appropriately chosen normalization constant that only depends p and y such that the mini- mum loss is The form of ppece differs from eun because Σ 1( S ply gain whereas Σ min + 1)y² is loss.
Next, we build loss families around
BB Bi and prece
For
Ap sums consider the family:
C( sum = {e SKXY, : if and only if Ae = 0ffffe e RR
((T,y) = E(f,, f)}.
By definition, (((u))) contains those ranking losses that are (1) zero-matched with Cup and (2) remain unchanged for any two predicted rankings (permutations) that are [p]-equivalent. The second constraint is needed to ensure that losses in L( (())))) only depend on the order and set of labels that I
ranks in the top-p. Likewise, we can construct a similar loss family around ppcce as follows:
L(P ((P prec = (RERSS L =0 O if and only if piece = 0)fff E IR SK x : = ((T,V)) ( v))
The set [((Ree) contains those ranking losses that are (1) zero-matched with fpece and (2) remain unchanged for any two predicted rankings (permutations) that are p-equivalent. The second constraint is needed to ensure that losses in [(( only depend on the set of labels that π ranks in the top-p. A major contribution of this paper is showing that both [(eam) ) and (((pee) are actually equivalence classes the same characterization of learnability holds for every loss in that family.
4 Batch Multilabel Ranking
In this section, we characterize the agnostic PAC learnability of hypothesis classes H. C S with respect to both L (((@)) and L((pre)) Our main results, stated below as two theorems, relate the learnability of H to the learnability of the threshold-restricted classes H..
Theorem 4.1. A hypothesis class H C SK is agnostic PAC learnable w.r.t E E L(PT))) if and only if for all i E [K] j j E (p), HP is agnostic PAC learnable w.r. the 0-1 loss.
Theorem 4.2. hypothesis class H SX is agnostic PAC learnable w.nt E C(( if and only for all [], HP is agnostic PAC learnable w.rl the 0-1 loss.
Since VC dimension characterizes the learnability of binary hypothesis classes under the 0-1 loss, an important corollary of Theorems 4.1 and 4.2 that finiteness of VC(H))'s, for the appropriate i.j [K] x [p], is necessary and sufficient for agnostic ranking PAC Icarnability. Later on, we use this fact to prove that linear ranking hypothesis classes are agnostic ranking PAC learnable.
We start with the proof of Theorem 4. which follows in three steps. First, we show that if for all (i.5) E [K] x [p]. H. is agnostic PAC learnable w.r.t 0-1 loss, then Empirical Risk Minimization (ERM) is agnostic PAC learner for H w.r.t (p, Next, we show that if H. is agnostic PAC learnable w.n.t e0p then H. is agnostic PAC learnable w.n.t any loss f E L(E Our proof of the latter uses the realizable to agnostic conversion from Hopkins et al. [2022] Finally, we prove the necessity direction
if H is agnostic PAC learnable w.r.t an arbitrary E E L((s))) then for all (i..) E [K] x [p). Hi is agnostic PAC learnable w.r. 0-1 loss. The proof of necessity direction also
the realizable to
agnostic conversion from Hopkins et al. (2022). The proof of Theorem 4.2 follows exactly the same way as Theorem with some minor changes. Thus, we only focus on the proof of Theorem 4.1 in
this section and defer all discussion of Theorem 4.2 to Appendix C3
We begin with Lemma 4.3 which asserts that if 76 is agnostic PAC learnable for all (f, E [K] x [p),
then ERM is an agnostic PAC learner for H w.r.t Rpp

---

Lemma 4.3. for all E [K] and j E [p], H. is agnostic PAC learnable w.tt the 0-1 loss, then ERM is an agnostic PAC learner for H. C SK W.F.
glpp sumn
The proof of Lemma
4.3 exploits the nice structure of Ba by upperbounding the empirical Rademacher complexity of the loss class Suu H. {(x, y) Gui (u()),))))) : h 70} and showing that it vanishes as the sample size n becomes large. Then, standard uniform convergence arguments outlined in Proposition C.1 imply that ERM is an agnostic PAC learner for H. w.r.t Sum-
The full proof is in Appendix C
Since arbitrary losses in L( may have nice analytical forms, Lemma 4.4 relates the learnabil- ity of an arbitrary loss E L (((um) to the learnability of pup
Lemma 4.4. If S S is agnostic PAC learnable wan flip. then H. agnostic PAC learnable w.r. any l E [((g))
Proof. (of Lemma 4.4
Fix é E C(Gum). Let a = mina.wte(T,))) {(T, y) # 0} and =
maxx,y f(T, y). We need to show that if H. is agnostic PAC learnable w.r.t Lap then H. is agnostic PAC learnable w.r.t L. We will do so in two steps. First, we will show that if A is an agnostic PAC learner for 20p then A is also a realizable PAC learner for L. Next, we will show how to convert realizable PAC learner for l into an agnostic PAC learner for in a black-box fashion. The composition of these two pieces yields an agnostic PAC learner for H w.r.t f.
Realizable PAC learnability of H. w.r.t f. If H. is agnostic PAC learnable w.r.t Eum, then there exists learning algorithm AA with sample complexity m(e, 6, K) s.t. for any distribution over X' x V, with probability 1 -- over a sample S ~ D" of size n 2 m(e, 8, K), the output predictor g = A(S) achieves ED 2a (g()), v)) I infReH ED sa (smm((( (h(x), v)) +c. In the realizable setting, we are further guaranteed that there exists a hypothesis ht E H s.t. ED [e(h (x),, v))]
Since E E C( (aan) ), this also implies that IED eur (h* (z)) v)) = O. Therefore, under realizability and the fact that S. b Sp we have Ep (((g(x),))) S be. This completes the first part of the proof as we have shown that A is also a realizable PAC learner for H w.r. & with sample complexity m(;, 6, K).
realizable-to-agnostt conversion. Now, we show how to convert the realizable PAC learner A for é into an agnostic PAC learner for l in a black- box fashion. For this step, we will extend the agnostic- to-realizable reduction proposed by Hopkins et al.] [2022] to the ranking setting by accommodating will show that
the mismatch between the range space of H and the label space y. In particular, Algorithm below converts a realizable PAC learner for l into an agnostic PAC learner for E. Note that although input A is a realizable learner, the distribution D may not be realizable.
Algorithm Agnostic PAC learner for H w.r.t. 8
Input: Realizable PAC learner A for H, unlabeled and labeled samples Sy ~ D'7 and St ~ Dm For each h E Hisg. construct a dataset
at (=I,,)),, (In, Tm)) s.t. de Unif(Binnel((((zz)) 1), BinRel(((z:)..1)
Run A over all datasets to get C(Sp) (A(S)) h His Return ğ C(Sy) with the lowest empirical error over St w.r.t. c.
Let ht arg m ED [((h(z), y) denote the optimal predictor in H. w.r.t D. Consider the sample Sh and let A(S We can think of g as the output of A run over an i.i.d sample S drawn from a a joint distribution over X' x y' defined procedurally by first sampling x ~ Dxx, then independently sampling j ~ (nif([z)). and finally outputting the labeled sample (x, BinRel(h* (x)) Note that D* is indeed a realizable distribution (realized by h²) w.r.t both and pipp Recall that ma(5 & 5, K) is the sample complexity of A. Since A is realizable learner for H. w.n. l, we have that for mA( 2..p: 6 8/2, K), with probability at least - & 2, EE [e(((x), v)1 < 26p
5

---

Next, by Lemma E.1 we have f(g(z), y) I e(h (z), y) be (i)()))(())) [e(g(z), BinRelll"
pointwise. Taking expectations on both sides the inequality gives
hp E B (aitii((b [((g(z), BinRel(h"(x):))))
Ep [((o(z)) v)) - ID (1))(()),))
ED [e(h (z), y)] +
The last inequality follows from the definition of D namely Ep-- [e(g(z),)) U)
ER IE (ps-tmi((p))) [[((()) BinReelh" (x); This shows that C(Sv) contains a hypothesis that generalizes well with respect to D. Now want show that the predictor 9 returned in step 4 also has good generalization. Crucially, observe that C(Su) is a finite hypothesis class with cardinality most 2 By standard Chernoff and union bounds, with probability at least 5/2, the empirical risk of every hypothesis in C(Sv) on a sample size 2 2/ log 4[C(Su] is at most e/4 away from its error. So, if
log 4|C(Sc)) then with probability least 8/2, [t.. zz
((g(z) v) < ED (((g(z), v) E ED (e(h"(x), (o.))ESz
3e
St
Since 9 is the ERM St over C(S), its empirical risk can be most TD [e(h" (I)), y)] + 3. Given that the population risk of 9 can be at most c/4 away from its empirical risk, we have that
ED(((((x), v)) s ED [e(h" (w).
Applying union bounds, the entire process succeeds with probability - 8. We can upper bound the sample complexity of Algorithm D
denoted ni(e, 5, K), as
nle, K) mA
aE 8/2, 202p"
+0
log IC(Su)
KmA 26- 8/2, K) + log
aE 8/2, K
S mA
+0
2122""
where [C(Sy) < 2* Kmma (2 m 5/2,K) for H w.r.t f.
This shows that Algorithm
is agnostic PAC learner
Finally, Lemma 4.5 gives the necessity direction of Theorem
Lemma 4.5. If a hypothesis class H. S S is agnostic PAC learnable w.r.f & E (( then Hi is
agnostic PAC learnable w.r.t the 0-1 loss for all (i,j) E [K] [p].
Like the sufficiency proofs, the proof of Lemma is constructive. Given an agnostic PAC learner for w.r.t we construct an agnostic PAC learner for Hi w.r. 0-1 loss using a slight modification of Algorithm I We defer the full proof to Appendix since the analysis is similar to that of Algorithm Together, Lemmas
and 4.5 imply Theorem
We conclude this section by giving concrete application of our characterization. Consider the class of manking-hyypohher
H. {a + argsort(Wz)) W E T kxd) that compute rankings by sorting scores, in descending order, obtained from a linear function of the input features. Lemma 4.6 whose
proof is in Appendix B. computes the VC dimension of Hi for an arbitrary i.j E [K].
Lemma 4.6. Let H. = {x + argsort(Wz)) W E IR Kxdd be a linear ranking hypothesis class. Then for all i.j E [K], VC(H.) (Kd)), where Ô hides logarithmic factors of d and K.
Combining Lemma 4.6 with Theorems and 4.2 shows that linear ranking hypothesis classes are
agnostic ranking PAC learnable w.r.t to all losses in L(ERM) C( ((( More generally, in Appendix B we give a fimension-based sufficient condition under which generic score-based ranking hypothesis classes are agnostic ranking PAC learnable.

---

5 Online Multilabel Ranking
We now move to the online setting and characterize the online learnability of hypothesis classes H C S with respect to both (( and [(fpee). As in the batch setting, our characterization relates the learnability of H to the learnability of the threshold-restricted classes H.
Theorem 5.1. A hypothesis class H. S Sk agnostic online learnable w.r.t E ((( if and only for all E [K] and j E [p], H. is agnostic online learnable w.r.t the 0-1 loss.
Theorem 5.2. A hypothesis class H C SK is agnostic online learnable w.r. & E (((pec) if and only if for all E [K], HP, is agnostic online learnable w.r.1 the 0-1 loss.
Since the Littlestone dimension characterizes the online learnability of binary hypothesis classes under the 0-1 loss, important corollary of Theorems 5.1 and 5.2 is is that finiteness of Ldim (H,) ) for the appropriate j E [K] x (p), is necessary and sufficient for agnostic online ranking learnability,
We now begin the proof of Theorem 5.1 Since the proof of Theorem 5.2 follows a similar trajectory, we defer all discussion of Theorem
Appendix D.2 Unlike Theorem in the batch setting, we prove the sufficiency and necessity directions of Theorem 5.1 directly. We chose this direct path because, unlike the batch setting, sequential Rademacher analysis does not yield constructive algorithm [Rakhlin et al. 2015]. On the other hand, our proofs are constructive and use the celebrated Randomized Exponential Weights Algorithm (REWA) Dssa-Bianchi and Lugosi 2006). Moreover, key ingredient of our proof is the realizable to agnostic conversion from Raman et al. 2023
Proof. (of sufficiency in Theorem 5.10 Fix E L(( ). Let a minz (((T,)) f(T, v) # 0} and M = maxx,y f( y). Given online learners for H3 for the 0-1 loss, our goal is to construct an online learner Q for H. w.r.t & that enjoys sub-linear regret in T. Our strategy will be to construct set of experts & using the online learners for H 's and run REWA using & and appropriately scaled version of f. Our proof borrows ideas from the to-zzabsi----- online conversion from Raman et al. 2023 and so we use the same notation whenever possible.
Let (01.91),.... (ET,9T) E (X x 2) denote the stream of points be observed by the online learner. We will assume an oblivious adversary and thus the stream is fixed before the game starts. standard reduction (Chapter 4 in Cesa- Bianchi and Lugosi| (2006)) allows us to convert oblivious regret bounds to adaptive regret bounds. Since H. S {0, 1] is online learnable w.r.t. 0-1 loss, we are guaranteed the existence of online learners A² for H..
Constructing Experts. For any bitstring b E {0, 13", let (LE 11 - SK denote function mapping time points where b. = 1 to rankings (permutations). Let D / (( denote all such functions Φb For every h E H. there exists a dit E t such that for all {t: b 1}. &f (t) = Mxx)). Let |b| Iit E [T]: b, = -) For every b E 1)7 and Φ E t we will define an Expert Fa.s- Expert Fa.s. formally presented in Algorithm 2 uses A make predictions in each round. However, Es,s only updates the A on those rounds where b, = 1, using & to compute labeled instance. For every E {0, 1)"", let &, = Upeo, {Fr,o} denote the set of all Experts parameterized by functions E &r If is the bitstring with all zeros, then &, will be empty. Therefore, we will actually define E, (Eo) U Upeo, (F where Eg is the expert that never updates A 's and only uses them for predictions all t E (7). Note that S | S (K!) < K
Using these experts, Algorithm presents our agnostic online learner Q for H. w.r.t & E ((( We now show that Q enjoys sub-linear regret. We highlight that there are three sources of randomness in online learner Q. namely the randomness of sampling B, the internal randomness of A As's, and the internal randomnes of P. One may think of internal randomness as arising from the sampling step involved the randomized predictions. Let A be the random variable associated with joint internal randomness of Ai for all (i.j) E [K] x [p]. Similarly, denote to be the random variable associated with the internal randomness of P. We begin by using the guarantee of REWA.
7

---

Algorithm 2 Expert (b, ()
Input:
Independent copy of realizable learners A₃ of Hi for each (i, [K] [p)
for f = I.... do
Receive example 2t
Define binary vote matrix V2 E {0, xx such that Vi[i.s] = (((e))
Predict म, arg mes (T,, V.1p)
b; then
Let ((() and for all (i,)) [K] (p], update Ai by passing (ste =.)
end
Algorithm 3 Agnostic Online Learner Q for H w.r.t.
Input: Parameter 0 B
Let B E 1J s.t. B, ~ Bernoulli T
iid
T
2 Construct the set of experts Eg
{Eo} U UsEr {EB,s} according to Algorithm
Run REWA P using Eg and the loss function over the stream 91), .... (2r, yr
REWA Guarantee. Using Theorem 21.11 Mhalev-Shward and Ben- Ben-David [2014] and the fact that B, A and P are mutually independent, REWA guarantees almost surely that
T
B((P(a)).))BBAA
inf BEEn
Σ
((E(a)), + M M In((El)..)
Taking outer expectation gives
T
T
E
Σ ((P(I)).
IE
inf EEEB t=1
Σ
((E())),)))
+ E M 2T [n(
Noting that ((xx) = P(xx), obtain
E
((((I))
IE
inf Σ EEEB t=1
((E(z));)t)
IE M / 2T In((EBl)
S F
E(E (2t). v1)
ME v 2n
In the last step, used the fact that for all 10,1)T and h H. E E &s. Here, h" infREH Etn ((h(xe). vi) is the optimal function in hindsight. First, note that In((En)) s K K(B(In((), Using Jensen's inequality gives IE /2T V2T1+0 KIn K. Thus,
((((z))
EE
E(E (21))
+
(I)
Upperbounding (I). It now suffices to upperbound E gives pointwise
Σm E(EB,og (2t). vi) Recall that Lemma
(E (I.). S (zh" v1) + pM
E Ey (EE (z,), BinRel(h' (xx)
(2)
where M max a( y) and mink ((( ((T, v) # 03. Note that, by definition of the
constant M, we further get {(E (E (xz), (atRel((((2)))))) M 1 (xt), (2 0}
M 18 (F (xx), (haRee((("(x))))))) > 0).

---

where the equality follows from the fact that & E ((
In order upperbound the indicator above, the realizable online learner A, for (i, m) E [k] x [p], an instance x E X, and an ordered finite sequence of labeled examples I. (X x (0, 10,13) ),, let AT" [.) be the random variable denoting the prediction of ATTh on the instance after running and updating on L. For any b E {0, h H. and & E (T], let L (i. ((r,, hg" (Ix)) 8 < ( and b, = 1} denote the subsequence of the [ where be- = 1. Then, for any j E [p], we have sequence of labeled instances {(z,, h:th (z. )
need to introduce some more notations. Given
P ((A D (i. # (x:))
11 ( ap B, (zt), BinRel(h" (zx). 03
To prove the inequality above, consider the case when E Em [< L (i, m)) o hi" (2t)] 0 because the inequality is trivial otherwise. Then, we must have ATT
(x."((a) for all (i, E [K] x [p]. Let V2 {0, 1] xxxx be binary vote ma- trix that E FB constructs in round f. Then, we have Vili, m] = A T (i, = (x:) for all (i.m) E [K] [p]. Since h" (zz) is a permutation, the vote vector Vilp must contain p labels with distinct number of non-zero votes, namely p.p. - 1.p 2,...,,,, 2, votes. Similarly, there must be K p labels with exactly 0 votes. Thus, every #. arg min (T, Velp,) must rank label that obtained p votes as 1, label with p p-11 votes as 2, and so forth. In other words, we must have [p]
LE (i, m))
# h" (xxz), and thus Cum (ft, BinRel(h" (x)) = O for any j E [p] by definition of (Bp Our claim now follows because EB (xx) E arg min {,, Vi1p)) Using these two inequalities in equation we obtain
2M2
p Σ
((E B (zi). v1) ((1"((x)
BB (1, # (z))),
a
i=1
m=1
which further implies that
PM2
9
T
E
L B, (1t), vo)
((M()))) v1)+
Σ
ΣΣB.
E
Σ
1
T (i, m)) # (x=))
(
The first term above is the cumulative loss of the best-fixed hypothesis in hindsight.
Upperbounding (II). It now suffices to show that E
D (1AT L (i, m)) # h (x:)]
sub-linear for every (i, m) E [K] x [p). Note that we can write
T
E B[[[B, 1
[A4 (Fz LB (i, + h (2:)3
Σ
E
[[A
(xz
L (i, # h 12 (x:))
E B[[[ =1]
t=1
T
T
Σ
E
1[A (xt L (1, ml)) # h 1. (x:) ) - 11]
1=1
where the last equality follows because [1
_ and the prediction of ATT Lk (i, m)) on round only depends on bitstring (B,..., 1). but is independent of B,. Next, Bec
= 1
we can use the regret guarantee of algorithm AT on the rounds was updated. That is,
E
A (z.
Lb m)) (B. =1} E
Σ Lr:
A (as L (i) # h (2:)3
1=1
= E
ATT (xt LB (1, m)) + h (xx))
s E IE ((B)),
Lt:B.=1
where ((((()) the regret of Am, a sub-linear function of BB] In the last step, we use the fact that Ath is realizable algorithm for HM and the feedback that the algorithm received was (Iz, h (;""""(())))))) (xx))

---

in the rounds whenever B, = 1. Next, Lemma 5.17 from Ceccherini Silniisiibrrstten et al. 2017 guarantees that there exists a concave sub-linear function R." ( that upperbounds R Thus, by Jensen's 's inequality, En [ (IB)) < En R (IBI)
(In [[BI]) (TT)), sub-linear
function of T
Combining ()) and (II) together, we obtain
2M2
P
T
E Σ ((Q(z))
S inf
Σ t=1
e(h(x)).v.)
RT (T + MV2 K. T
KER
m=
Since R.T (T.) is sublinear function of T we have that T3 R. (T As the sum of sublinear functions is sublinear, the second term above must be sublinear function of T. The regret is sub-linear for any choice of B E (0, 1). This completes our proof as we have shown that the algorithm achieves sub-linear regret in T.
) is a sublinear function of T.
The proof of the necessity direction of Theorem also involves constructing experts and running the REWA algorithm. Since the argument is similar, we defer details to Appendix D.I
Discussion
In this paper, we characterize the learnability of multilabel ranking hypothesis class in both the batch and online setting for wide range of practical ranking losses. In all cases, we show that ranking hypothesis class learnable if and only if a sufficient number of its binary-valued threshold restrictions are learnable, Our paper studies two families of ranking loss functions and leaves it open to characterize the learnability of other natural ranking loss functions. One loss function not captured by our families is @ecall@p.
While we do establish quantitative bounds on the sample complexity and regret, our bounds are not optimal. It may be difficult to improve the sample complexity and regret bound at the highest level of generality for all losses in the families considered here. However, for natural losses such as sum loss, it is an interesting future direction to derive the optimal sample complexity and regret bounds in both the realizable and agnostic settings. addition, our bounds depend on the number of labels K. Recently, K K-free bounds have been achieved for multiclass classification problems in both batch and online settings [Brukhim al. 2022 Hanneke al. 2023 An interesting future direction is to study whether K-free bounds are possible for multilabel ranking.
Finally, the focus of this paper is characterizing learnability, and thus our algorithms computationally efficient. A natural future direction is to construct computationally efficient algo- rithms for multilabel ranking. Along this direction, since ERM is the most common algorithm used in practice, it is an important future direction to tightly quantify the sample complexity of ERM in the batch setting. Moreover, in learning theory, combinatorial dimensions play an important role in providing a tight quantitative characterization of learnability. Thus, it is an interesting future direction identify combinatorial dimensions that characterize multilabel ranking learnability for specific loss functions.
Acknowledgements
We acknowledge the support of NSF via grant IIS-2007055. VR acknowledges the support of the NSF Graduate Research Fellowship.
References
Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In Conference on Learning Theory, pages 119-152, PMLR, 2020.
Ivo M Baltruschat, Hannes Nickisch, Michael Grass, Tobias Knopp, and Axel Saalbach. Comparison of deep learning approaches for multi-label chest x-ray elassification. Scientific reports, 91)::-10, 2019.
10

---

Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities; Risk bounds and structural results. Journal of Machine Learning Research. 3(Nov):463-482 2002.
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Ychudayoff. A characterization of multiclass learnability, 2022. http::///////tiioorrrr hbtp://bbb/2..... 2200./0000000
Serhat S Bucak, Pavan Kumar Mallapragada, Rong Jin, and Anil K Jain. Efficient multi-label ranking for multi-class learning: application to object recognition. In 2009 IEEE 12th International Conference on Computer Vision, pages 2098-2105. IEEE, 2009.
David Buffoni, Clément Calauzenes, Patrick Gallinari, and Nicolas Usunier. Learning scoring functions with order-preserving losses and standardized supervision. In The 28th International Conference on Machine Learning (ICML 20/ I). pages 825-832 832, 2011.
Clément Calauzenes, Nicolas Usunier, and Patrick Gallinari. On the (non-) existence of convex, calibrated surrogate losses for ranking. Advances in Neural Information Processing Systems, 25, 2012.
T. Seccherini-Silberstee M. Salvatori, and E. Sava-Huss. Groups, Graphs and Random Walks. London Mathematical Society Lecture Note Series. Cambridge University Press, 2017. doi: 00.1017/988111657663
Nicolo
and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Amanda Clare and Ross King. Knowledge discovery in multi-label phenotype data. In Principles of Data Mining and Knowledge Discovery: 5th European Conference, PKDD 2001, Freiburg, Germany, September 3-5, 2001 Proceedings 5, pages 42-53. Springer, 2001.
Amit Daniely and Shai Shalev-Shwarte Optimal learners for multiclass problems. In Conference on Learning Theeory pages 287-316. PMLR, 2014.
Amit Daniely, Sivan Sabato, Shai Bev-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. In Sham M. Kakade and Ulrike von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 207-232, Budapest, Hungary, 09-11 Jun 2011. PMLR.
Krzysztof Dembezynski, Wojeiech Kotlowski, and Eyke Hüllermeier. Consistent multilabel ranking through univariate losses. arXiv preprint arXiv: /206 6.006, 2012.
John C Duchi, Lester Mackey, and Michael Jordan. On the consistency of ranking algorithms. In ICML, pages 327-334, 2010.
Richard M Dudley. Central limit theorems for empirical measures. The Annals of Probubility, pages 899-929, 1978.
Wei Gao and Zhi-Hua Zhou. On the consistency of multi-label learning. In Proceedings of the 24th annual conference on learning theory, pages 341-358. JMLR Workshop and Conference Proceedings, 2011.
Yunchao Gong, Yangqing Jia, Thomas Leung, Alexander Toshev, and Sergey loffe. Deep convolu- tional ranking for multilabel image annotation. arXiv preprint 1312 2013.
Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. In The Thirty Sixth Annual Conference Learning Theory, pages 5682-5696. PMLR, 2023.
Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3015-3069, PMLR, 02-05 Jul 2022.
Thorsten Joachims. Text categorization with support vector machines: Learning with many relevant features. In Machine Learning: ECMI--98: 10th European Conference on Machine Learning Chemnitz, Germany, April 21-23 1998 Proceedings, pages 137-142. Springer, 2005.
11

---

Young Hun Jung and Ambuj Tewari. Online boosting algorithms for multi-label ranking. In International Conference on Artificial Intelligence and Statistics, pages 279-287. PMLR, 2018.
Anna Korba, Alexandre Garcia, and Florence Alché Buc. structured prediction approach for label ranking. Advances in Neural Information Processing Systems, 31, 2018.
Oluwasanmi O Koyejo, Nagarajan Natarajan, Pradeep K Ravikumar, and Inderjit S Dhillon. Consis- tent multilabel classification. Advances in Neural Information Processing Systems, 28, 2015.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23, Springer Science & Business Media, 1991.
Nick Littlestone. Learning quickly when irrelevant attributes abound: new threar- algorithm. Machine Learning. 2:285-318, 1987.
Tie-Yan Liu al. Learning rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3):225-331, 2009.
Andrew Kachites McCallum. Multi-label text classification with a mixture model trained by em. In AAA/'99 workshop text learning, 1999.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161:111-153, 2015.
Vinod Raman, Unique Subedi, and Ambuj Tewari. A characterization of multioutput learnability. arXiv cs.LG, 2023. preprint 12..:::233.177116
Pradeep Ravikumar, Ambuj Tewari, and Eunho Yang. ndeg consistency of listwise ranking methods. In Proceedings of the Fourleenth International Conference Artificial Intelligence and Statistics, pages 618-626. JMLR Workshop and Conference Proceedings, 2011.
Robert E Schapire and Yoram Singer. Boostexter: A boosting- baase system for text categorization. Machine learning, 39:135-1661 168, 2000.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014.
Leslic G. Valiant. A theory of the learnable. In Symposium on the Theory of Computing. 1984.
V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition [in Russian]. 1974.
Xi Wang and Gita Sukthankar. Multi-label relational neighbor classification using social context features. Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 464 472, 2013.
Hao Yang, Joey Tianyi Zhou, Yu Zhang, Bin-Bin Gao, Jianxin Wu, and Jianfei Cai. Exploit bounding box annotations for multi-label object recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 280-288, 2016.
Min-Ling Zhang and Zhi-Hua Zhou. A review on multi-label learning algorithms. IEEE transactions on knowledge and data engineering, 26(8):1819-188)) 2013.
12


Reviews:
[{"review_id": "QpsEhkIPSo", "reviewer": "Reviewer_edyo", "summary": "The authors study the problem of learnability of label ranking for a large family of ranking losses. The paper is purely theoretical. The main results have been built on the equivalence of realizable and agnostic learnability of the PAC model for binary classification. Using the techniques from Hopkins et al. (2022) and Raman et al. (2023), the authors show the learnability of label ranking in batch and online settings. Furthermore, they prove that ranking based on linear functions is learnable in the batch setting. \n", "questions": "Learnability is an important concept, but consistency is important as well. How do the results from the submitted paper relate to the previous results concerning consistency of multi-label ranking?\n", "limitations": "The realizable-to-agnostic conversion is not computationally efficient. How does it impact the main findings of the submission? \n\nIt seems there is many other loss functions of \"ranking\" type in multi-label classification. How those results would apply to, for example, recall@p? It also seems that macro-metrics could also be interpreted as a kind of \"ordering\" functions. The abstract says that the results \"capture most, if not all, losses used in practice.\" Is the statement not too strong? What are examples of losses not included in the two families considered in the paper?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Strengths:\n- Important theoretical contribution\n- Practical learning problem\n\nThe paper is an important theoretical contribution for a practical learning problem. The result is novel and seems to be correct. Nevertheless, it is rather a straightforward extension of previous results. \n", "weaknesses": "Weak points:\n- Confusing problem setup\n- No discussion on related work \n- Structure of the paper \n\nThe problem setting seems to be a bit confusing. I would call it rather label ranking (potentially with ties) instead of multi-label ranking. The latter suggests that the feedback information is binary. Alternatively, a wider discussion on differences between learning problems should be given.\n\nThe paper lacks discussion on related work. The obtained results should be discussed in light of the previous theoretical results on multi-label ranking (e.g., Dembczynski et al., 2012, Gao and Zhou, 2011, Koyejo et al., 2015). Unfortunately, the link between those results is not given in the paper. \n\nHaving a page limit, it is always hard to properly divide the results between the main text and the appendix. I appreciate that the authors decided to give the most important proofs in the main text. Unfortunately, the price for it is that the paper lacks the context (clear definition of the problem, discussion of ranking loss functions), wider discussion on the results (examples, related work), and discussion on limitations and practical implications.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting that this work is an important theoretical contribution to a practical learning problem. \n\n**Q1**: *\"The problem setting seems to be a bit confusing. I would call it rather label ranking (potentially with ties) instead of multi-label ranking. The latter suggests that the feedback information is binary.\"*\n\nA1: We thank the reviewer for pointing this out. We note that by taking B = 1 in Line 55, our model allows for the feedback to be binary. We will also include a broader discussion on the differences between learning problems in the camera-ready version. \n\n**Q2**: *\"The paper lacks a discussion on related work.\"*\n\nA2: We thank the reviewer for pointing out these works. We will make sure to include a discussion of these works along with a comparison to our results in the camera-ready version. \n\n**Q3**: *\"Unfortunately, the price for it is that the paper lacks the context (clear definition of the problem, discussion of ranking loss functions), wider discussion on the results (examples, related work), and discussion on limitations and practical implications.\"*\n\nA3: We thank the reviewer for bringing up these concerns. We will consider moving all proofs to Appendix and expand more on the problem setup, ranking loss functions, related work, limitations, and practical implications. \n\n**Q4**: *\"Learnability is an important concept, but consistency is important as well.\"*\n\nA4: We thank the reviewer for pointing out the problem of consistency. While we do think that consistency is important, the main focus of this paper is establishing the learnability of multilabel ranking, which apriori, was not known. In the camera-ready version, we will make sure to reference and state the prior results on consistency for multi-label ranking and mention that the main focus of this work is on learnability. \n\n**Q5**: *\"The realizable-to-agnostic conversion is not computationally efficient.\"* \n\nA5: We thank the reviewer for pointing this out. Indeed, our realizable-to-agnostic conversion is not computationally efficient. However, the main focus of this work is statistical and more specifically to provide a characterization of multilabel learnability. That said, we do think that establishing learnability via efficient reductions and constructing computationally efficient learning algorithms for multilabel ranking is an interesting future direction. \n\n**Q6**: *\"It seems there is many other loss functions of \"ranking\" type in multi-label classification. How those results would apply to, for example, recall@p?\"*\n\nA6: We thank the reviewer for pointing out that there are other loss functions of ranking type in multilabel classification, like the recall@p loss (under binary relevance score feedback). Unfortunately, the recall@p loss does not fall in either the sumloss@p family or the precision@p loss family. This is because if the number of relevant items is more than p, then recall@p will never be 0 (since it is not possible to return all the relevant items). In addition, the pairwise ranking loss is a popular \"ranking\" type loss in multi-label classification which we do capture in the sumloss family.  Overall, we agree that the loss functions captured by the sumloss@p and precloss@p families are not exhaustive. However, we do still believe that they capture the most popular ranking loss functions used in practice.\n\n**Q7**: *\"The abstract says that the results \"capture most, if not all, losses used in practice.\" Is the statement not too strong? What are examples of losses not included in the two families considered in the paper?\"*\n\nA7: We will dial back this claim and instead rephrase it to \"most ranking losses used in practice\". That said, our loss families do capture most of the ranking losses used in practice. For example, all the ranking losses found in the popular MULAN library can be categorized into one of the 2 families. One example of a ranking loss that is not included in one of the two families is a thresholded version of the sum loss. That is, consider the loss function that is defined by first computing the sum loss and then setting it to zero if its value is smaller than some preselected threshold. \n\n\n\n\n\n\n"}, {"review_id": "AuFMyVcApD", "reviewer": "Reviewer_euAG", "summary": "The authors in their work focus on a single theoretical contribution - showing that the multilabel ranking hypothesis class is PAC learnable for a wide range of ranking losses in both batch and online settings.\nThe authors first define two general families of ranking losses that are equivalent to popularly used losses.\n (like Pairwise Rank Loss, Discounted Cumulative Gain, Reciprocal Rank, Average Precision, Precision@p) \nThen they show for the defined losses and both batch and online settings, the hypothesis class of multilabel ranking losses $\\mathcal{H}$ can be expressed using binary hypothesis classes $\\mathcal{H}_i^j$ for $i, j \\in [K]$, where ($K$ is a number of labels), where $\\mathcal{H}_i^j$ tels whether the label $i$ should be ranked in the top $j$ positions. The authors show that binary class $\\mathcal{H}_i^j$ is PAC learnable, and as a result of that, it's also $\\mathcal{H}$, and existing combinatorial dimensions for batch and online learning like VC and Littleston characterized learnability in the considered multilabel setting.\n\nTo be honest, I'm far from the best person to review this work, as I don't know related works that are the most important to this paper except the book of Shalev-Shwartz and Ben-David, which I read some time ago, so I cannot judge it in the context of recent works in this area. Since the proof is very slightly outlined in the main paper, I tried to check the appendix as much as time allowed me. I checked Appendix A, B, and most of C. I did not check Appendix D and E.\n\nAssuming that all the parts are correct, I believe this is a solid contribution that should be accepted.", "questions": "I don't really have questions. ", "limitations": "There are no direct negative social impacts of this work. The limitation of tightness of sample complexity and regret is mentioned in the last section. I do not see any other limitations of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper contributes to the fundamental understanding of statistical learning theory for learning multilabel ranking.\n- The presented proofs are non-trivial but, at the same time, clearly presented in the appendix.", "weaknesses": "- The main proofs are only slightly outlined in the main paper; by slightly, I mean they don't give out any idea behind the proof, only the intermediate results. Because of that, the main paper feels more like an introduction to notation, and then it basically forces the reader to switch to reading a long appendix (or the read can just stop reading and believe the authors the result is valid). The paper would definitely benefit from a longer form. Also, the appendix would benefit from including the original theorems and lemmas to reduce the need for switching between the main paper and the appendix.\n- It seems to me that two families of defined ranking losses capture \"most if not all ranking losses used in practice\" is a bit overstated. The result is not surprising as losses equivalent to these families (listed in Appendix A) are simple losses with (I think) the same form of an optimal hypothesis that predicts top $p$ or $K$ labels in descending order of expected relevance. These families may not capture more complex measures, but I agree that these are very popular.\n- This is a notation-dense paper; as a reader, I would appreciate some more comments/full-sentence explanations on notation in Sections 2 and 3 to confirm my understanding of it before jumping to the main results. For example, it was not clear to me if relevance is descending, meaning B is the most relevant and 0 is the least relevant or its opposite. I could only confirm it by reading definitions of $\\ell_{\\text{sum}}^{@p}$, and $\\ell_{\\text{prec}}^{@p}$ and figuring out which one makes sense, but that was one page later. Again this I believe is a fault of limited space.\n- NIT: The discussion section is not really a discussion, just a short summary.\n- NIT: Lack of equation numbers is inconvenient when reading the paper like this (for example, to make notes on equations, as there is no defined way to address them).\n- NIT: There are equations that go over the right margin, which is a bit unelegant when there is a strict space limit. \n- NIT: Bit string? Why not just binary vector? To me bit string is a compact implementation of a binary vector.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding that our paper contributes to the fundamental understanding of statistical learning theory for multilabel ranking.\n\n**Q1**: *\"The main proofs are only slightly outlined in the main paper; \"*\n\nA1: We thank the reviewer for pointing this out. We will make sure to add detailed proof sketches in the main text for the camera-ready version. In addition, we will include the original theorems and lemmas in the Appendix. \n\n**Q2**: *\"It seems to me that two families of defined ranking losses capture \"most if not all ranking losses used in practice\" is a bit overstated. \"*\n\nA2: We will dial back this claim and instead rephrase it to \"many popular ranking losses used in practice\".  That said, our loss families do capture most of the ranking losses used in practice. For example, all the ranking losses found in the popular MULAN library can be categorized into one of the 2 families. \n\n**Q3**: *\"This is a notation-dense paper;\"* \n\nA3: We agree with the reviewer that this is a notation-dense paper.  Will will make sure to add more explanations of the notation in Sections 2 and 3. Moreover, we will make sure to explicitly highlight that larger scores imply higher relevance.\n\n**Q4**: *\"The discussion section is not really a discussion, just a short summary.\"*\n\nA4: We will expand on the discussion section by including limitations and future directions in the camera-ready version. \n\n**Q5**: *\"NITS\"*\n\nA5: We thank the reviewer for pointing out these issues. We will address all these comments in the camera-ready version. \n\n\n\n"}, {"review_id": "2q2Ai5AySM", "reviewer": "Reviewer_ejP3", "summary": "This work study the learnability of multilabel ranking problems in both batch and online settings for different ranking losses family. They show that the multilabel ranking learnability is equivalent to the learnablities of a family of binary classification problems.", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper tackles a well-motivated problem. Besides, since the theory on the learnability of multilabel ranking is blank before this work, it seems that the novelity and originality of this paper can be promised.\n*  The paper is overall well-written. The presentation of theoretical results is rigorous.\n* The proofs are solid based my judgement.\n* The results are surprisingly concise.\n* The authors present a example stating that linear ranking hypothesis class is learnable, which shows that theri results are pratical.", "weaknesses": "As the authors confirmed, the bounds may be not optimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding that our paper tackles a well-motivated problem and presents a novel and original contribution to the theoretical foundations of multilabel ranking. "}, {"review_id": "sQq4xQ1nq9", "reviewer": "Reviewer_6zYz", "summary": "This paper is mainly about the learnability of multilabel ranking. The authors show that a ranking hypothesis class embeds $K^2$ different binary hypothesis classes and defines two families of ranking loss functions that capture most, if not all, ranking losses used in practice. The paper addresses the fundamental question of when a multilabel ranking problem is learnable, which remains unanswered despite the vast literature on multilabel ranking.", "questions": "I have no questions about this paper.", "limitations": "This paper did not contain experiments for any proposed algorithm and losses.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides a significant contribution to understanding when a multilabel ranking problem is learnable, addressing a fundamental question that has remained unanswered despite the extensive literature on multilabel ranking. The authors also provide sufficient conditions for the agnostic Probably Approximately Correct learnability of score-based ranking hypothesis classes.\n", "weaknesses": "This paper does not contain any experiments for their theories and algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting that our work provides a significant contribution to the learnability of multilabel ranking problems. \n\n**Q**: *\"This paper does not contain any experiments for their theories and algorithms\"*\n\nA: We thank the reviewer for noting this concern. We would like to emphasize that the main focus of our work is theoretical as we aim to characterize the learnability of multilabel ranking problems. No prior characterization of learnability was known for multilabel ranking.  Developing ranking algorithms with strong practical guarantees has been extensively studied, but we believe it is out of scope for this paper. \n"}]

Author rebuttal:

Meta-review: The paper focuses on the learnability of multilabel ranking problems in both batch and online settings. The reviewers gave the paper a uniformly positive evaluation and generally find it to be a significant theoretical contribution to the field, addressing an important and previously unanswered question. There were some concerns and suggestions, mainly regarding clarity, related work discussion, and minor formatting issues, but they did not affect a positive reception of the paper.
Decision: Accept (spotlight)