Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization
Authors: Guoqiang Wu
Chongxuan Li
Kun Xu
Jun Zhu
Venue: NeurIPS 2021 Poster (2021)
Keywords: statistical learning theory
multi-label ranking
generalization
consistency

Abstract: The (partial) ranking loss is a commonly used evaluation measure for multi-label classification, which is usually optimized with convex surrogates for computational efficiency. Prior theoretical efforts on multi-label ranking mainly focus on (Fisher) consistency analyses. However, there is a gap between existing theory and practice --- some inconsistent pairwise losses can lead to promising performance, while some consistent univariate losses usually have no clear superiority in practice. To take a step towards filling up this gap, this paper presents a systematic study from two complementary perspectives of consistency and generalization error bounds of learning algorithms. We theoretically find two key factors of the distribution (or dataset) that affect the learning guarantees of algorithms: the instance-wise class imbalance and the label size $c$. Specifically, in an extremely imbalanced case, the algorithm with the consistent univariate loss has an error bound of $O(c)$, while the one with the inconsistent pairwise loss depends on $O(\sqrt{c})$ as shown in prior work. This may shed light on the superior performance of pairwise methods in practice, where real datasets are usually highly imbalanced. Moreover, we present an inconsistent reweighted univariate loss-based algorithm that enjoys an error bound of $O(\sqrt{c})$ for promising performance as well as the computational efficiency of univariate losses. Finally, experimental results confirm our theoretical findings.

Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization
Guoqiang Wu'; Chongxuan Li', Kun Xu, Jun Zhut
Dept. of Comp. Sci. & Tech., Institute for AI, State Key Lab for Intell. Tech. & Sys., Banghua--Bosch Bosch Joint Center for ML, BNRist Center, Tsinghua University, Beijing, 100084 China {guoqiangwu90, chongruanli 19911, kunxu. tanrauuuth)u@gmaiii com. dcszj@tsinghua.edi edu. edu.cn
Tsinghua-
Abstract
The (partial) ranking loss is a commonly used evaluation measure for multi-label classification, which usually optimized with convex surrogates for computational efficiency. Prior theoretical efforts on multi-label ranking mainly focus on (Fisher) consistency analyses. However, there is gap between existing theory and practice some inconsistent pairwise losses can lead to promising performance, while some consistent univariate losses usually have no clear superiority practice. To take a step towards filling this gap, this paper presents a systematic study from two complementary perspectives of consistency and generalization error bounds of learning algorithms. We theoretically find two key factors of the distribution (or dataset) that affect the learning guarantees of algorithms: the instance-wis -wie class imbalance and the label size Specifically, in an extremely imbalanced case, the algorithm with the consistent univariate loss has an error bound of O(e), while the one with the inconsistent pairwise loss depends on O(yc) shown in prior work. This may shed light on the superior performance of pairwise methods practice, where real datasets usually highly imbalanced. Moreover, present an inconsistent reweighted univariate loss-based algorithm that enjoys an error bound of Ol (CC) for promising performance well as the computational efficiency univariate losses. Finally, experimental results confirm our theoretical findings.
Introduction
Multi-Label Classification (MLC) [1 is an important task, in which each instance is associated with multiple labels simultancously. It has been widely applied text categorization (2], bioinformatics (3]. multimedia annotation [4) information retrieval [5] Various measures 7 have been developed to
evaluate MLC's performance from diverse aspects owing to its complexity. Among them, the ranking loss (RL) (or partial ranking loss, PRL) 22 8 is commonly used measure in practice (or in theory). Formally, the RL calculates the fraction pairs that positive label does not precede a negative label according to the rank given by score function (or predictor). Minimizing such loss is usually referred to as Multi-Label Ranking (MLR) [9), which is the consideration in this paper.
Since RL is non-convex and discontinuous, existing methods 6 seek to optimize certain convex surrogate losses for computational efficiency. These surrogate losses can be divided into two main categories; pairwise ones 8 and univariate ones (9]. which have their own advantages and limitations terms of computational costs, theory and empirical performance.
"Equal contribution. G. Wu is now School of Software, Shandong University and C. Li is now Gaoling School of AI, Reamin University of China. The work done when they were at Tsinghua University. "Correpoonding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Summary of the main theoretical results. Contributions of this paper are highlighted in red.
Generalization bound extremely imbalanced
Algorithm
Surrogate loss
Consisteney F Computation
balanced
An
pairwise (Leia)
+()
R (
O(e*)
A
univariate (Iuz)
(f) (f)
( :
O(c)
A
univariate (Lvz)
(c 1) 1) (f)+(())+ (0)++)((
() - 0 4
((c)
AA
reweighted univariate (Lug)
Rg (f) +0(
(f)
O(c)
A44
reweighted univariate (Trua)
Rg (f) +V)
+
O(c)
"This is in terms of the PRL. Besides, these surrogate losses are all inconsistent w.r.t the RL. This for the cases where the base loss the exponential, logistic, least squared or squared hinge loss.
Computationally, the pairwise losses, defined over pairs of positive and negative labels, have a com- plexity depending on (c²²) (c the number of labels), while the univariate ones enjoy a complexity depending on O(c). The superiority of the latter significant when e large. Theoretically, the pairwise losses are not (Fisher) consistent w.r.t. the RL or the PRL g while, remarkably, certain univariate ones are consistent w.r.t. the PRL 19]8) Empirically, however, the consistent univariate losses usually have no significant superiority compared to the inconsistent pairwise losses [9] In fact, we observed that the former under-perte mnder-perform the latter on 10 MLR benchmarks (see results in Table B). Towards filling the gap between the existing theory and practice, this paper attempts to rigorously answer the following questions: Why inconsistent pairwise losses usually achieve better performance than consistent univariate losses in practice? How improve the univariate loss, which is preferable due to its computational efficiency? A natural explanation of this gap is that although the (Fisher) consistency 110 11 provides valuable insights in the asymptotic cases, it cannot fully characterize the behaviour of a surrogate loss when the number of training samples is not sufficiently large and the hypothesis space is not realizable.
Therefore, this paper presents systematic study in a complementary perspective of generalization error bounds [12] besides the consistency. We theoretically find two key factors of the distribution (or dataset) that affect the learning guarantees of algorithms: the instance-wis wise class imbalance and the label number c. Given extremely imbalanced data (i.e., the worst case), prove that the consistent univariate losses based algorithms lead to an error bound of Occ) while the pairwise losses based ones enjoy an error bound depending on ((vc) [3] which explains the empirical behaviour better on real datasets which are usually highly imbalanced (see Tjble Further, we present two reweighted surrogate univariate losses that employ carefully designed penalties for positive and negative labels. Then, we analyze their consistency and generalization bounds of the corresponding algorithms. Surprisingly, though not consistent, one of them enjoys an error bound depending on ((vc) in the worst case, which is nearly the same as the pairwise losses, and retains the computational efficiency. For balanced data (i.e., the best case), we also find that all these surrogate univariate losses share the same learning guarantees, with no dependence on which is the same as the surrogate pairwise ones. Notably, in this case, these bounds are different from the classical probably approximately correct (PAC) ones [2 [5] which hold for all distributions (i.e. the worst case). Our main theoretical results are summarized in Table Experimental results also confirm our theoretical findings.
2 Preliminaries
In this section, we first introduce the problem setting of MLC and MLR. Then, we present the evaluation measures, risk, and regret of MLR.
Notations. Let boldface lower and capital case letters denote vectors (e.g., a) and matrices (e.g., A) respectively. For a matrix A, a,, al and ai denote its i-th row, j-th column, and (i, j-th element respectively. For a vector a, a; denote its i-th element. For a set, denotes the cardinality. [m] denotes the indicator function, i.c., [T]] 1 if the proposition x holds and 0 otherwise.

---

2.1 Problem Setting
L X X Ie and y E (-1,,1,++1) denote the input and output respectively, where d the feature dimension, c the label size. yj (or -1) indicates that the associated j-th label is relevant (or irrelevant). Given a training set S {x),) y.)] of n samples i..d. drawn from a distribution P over X' x y, the original goal of MLC is learn multi-label classifier
Rdd (-1,+1)
To solve MLC, common approach is to first learn a vector-based score function (or predictor) [f se] R + I and then get the classifier H by thresholding function. Multi-Label Ranking (MLR) aims to learn the best predictor from the finite training data in terms of some ranking-based measures, which is our consideration in this paper.
2.2 Evaluation Measures
To evaluate the performance of different approaches for MLR, many measures have been developed. Here we focus on two widely-used measures in practice (or theory), which are defined below
Ranking Loss (RL): LO ()(),,)
Σ
[n(x) S fx)]
(I)
St 1
(p-))E x
where St (or Sÿ) denotes the relevant (or irrelevant) label index set induced by Partial Ranking Loss (PRL)
(f()),)) 1 Sy
Σ
[f(()) x f + -f
(2)
(R.))ST 85
Note that the only difference between these two measures is the penalty when fx(x) = fx(x)
holds. Besides, it is easy to verify that RL upper bounds PRL, i.e. (f(x), < 1. (f(x.
Although these two measures are almost the same in practice for the evaluation of one algorithm, they have different consistency properties for some surrogate losses theoretically (8)
2.3 Risk and Regret
Since RL non-convex and discontinuous, often leading to NP-hard problems [6], it optimized with convex surrogates in practice for computational efficiency. Define surrogate loss Ls R x [-1,+13e + R4, where á indicates the specific surrogate loss and will be detailed the next section. Besides, define vector- rester-based predictor class F = {f X - R.). For predictor F. its true (0/1) expected risk, surrogate expected risk, and surrogate empirical risk are defined as:
1. |T (f(x), R$( = E P [L,((x))))) Rs( = Σ (f y:). (x,y)>
Ro)1(S) = E (x,y)~P
Besides, we use superscript (i.e., pr r) to distinguish the risks for specific measures. Further, for convenience, we denote the expected risk conditioned on an instance x (i.e., the conditional risk) as:
R(f(x)
E y~PPly x) [LI( = Σ x((yx))))
where L denotes the true or surrogate loss. Thus, the expected risk of f is R(f) = Ex- [R(f
For each x, given the conditional distribution P(y(x), we can get its optimal predictions as follows [*(x = arg min
Σ T. y()l)))
agRe
where 1* is called the Bayes predictor w.r.t. the loss L. Besides, the expected risk of f" (i.e., R(S*) is called the Bayes risk, which is the minimal expected risk w.r.t. the loss L and denoted by R for
Our definition is over one sample and can be averaged over multiple samples. MMinimizing the PRL equivalent to maximize instance- AUC. 'Notably, the optimal predictions can be not just one value but set with many elements that share the same minimal conditional risk.
3

---

convenience. Then, we can define the regret (a.k.a. excess risk) of predictor f w.r.t. the true and surrogate loss as follows.
( = Ra/1(f) RoyD Reg = Ro(f) R
(5)
Besides, also use a superscript (i.e., pr or to distinguish the regrets for specific measures. Moreover, let fn denote the learned predictor from finite training data S. Note that our goal is find a predictor fn that achieves the minimal true regret (i.e. Rego/1 (fn) possible can.
Methods
In this section, we first introduce several specific surrogate losses. Then, we present their associated learning algorithms.
3.1 Surrogate Losses
To optimize the RL, it is natural employ the convex surrogate pairwise loss
2 17 18 as:
Lpa (x)))(x),))
Σ ((f(x)) - (x)).
[Sy Syy
(n-a)eSt x
where the base (margin-based) convex loss E(2) be defined in various popular forms, such as the exponential loss {(2) = e= the logistic loss {(2) = In + e *)",, the hinge loss {(z) = ma 1 - 2}. and squared hinge loss {(z) (max(0, 1 2 A common property is that the base convex surrogate loss upper bounds the original 0/1 loss i.e., [ I 0] S ((z).
Besides, the surrogate univariate loss, which primarily aims to optimize Hamming loss 19 also be viewed surrogate loss for the RL, which is defined as follows:
13 can
1 Σ f())f((x))
Lus (f(x).
Notably, Lu, cannot strictly upper bound the RL, i.c. L (f(x), y) & Lo, (f(x). y). Previous work presents the consistent surrogate univariate loss [9] 8 w.r.t. PRL. which is defined as follows:
Lug (f(x), st J=1
Σ (())f(())).
(8)
Again, the consistent surrogate loss Lug cannot strictly upper bound the RL either. Notably, when the surrogate loss strictly upper bounds the 0/1 loss. the true (0/1) risk can be upper bounded by the surrogate risk too, which is crucial for its generalization analysis. Thus, we present two reweighted convex surrogate univariate losses, which strictly upper bound RL and PRL, defined below.
Epest (()nf(()))
+ Evesy ((),f(())
Lug (xx,))))
|Sy
|S7
(fx)))))))) min 1.1St..1555 1.55
(x),
(10)
For a clear presentation, we will formally discuss their relationships in the next section.
3.2 Learning Algorithms
In the following, consider the kernel-based learning algorithms which have been widely used in practice 3 19 20
21 (2) and in theory [13] for MLC. Besides, our following analyses can be extended to other forms of hypothesis class, such as neural networks 23 Let H be a reproducing
kernel Hilbert space (RKHS) induced by the kernel function x, where k : X' x X + R is Positive Definite Symmetric (PDS) kernel. Let 4 : X - H be a feature mapping associated with k. The kernel-based hypothesis class can be defined as follows.
W (x)) W (WI...., Wo) W| < A
(11)
'The original logistic loss can be easily changed to {(2) log, (1 + 2 satisfy this condition.

---

where
Wil denotes | BB. = (j== wy w/ for convenience.
Here we consider the following five learning algorithms with the corresponding aforementioned surrogate losses. They can be formulated follows with À denoting a trade-off hyper-parametter:
A
min
Lp (f(x), W/|,
(12)
M
min W
Lu (1x)) + 1,2,,3
(13)
4 Theoretical Analyses
In this section, we present generalization error bounds of the learning algorithms presented before and consistency analyses of the corresponding surrogate losses.
Consistency analyses aim to answer the question of whether the (0/1) expected risk of the learned function converges the Bayes risk [1] [ when samples goes infinity. can provide valuable insights for learning from infinite (or relatively large) data with an unconstrained hypothesis class. In comparison, generalization bounds may offer more insights for learning from finite data with constrained hypothesis class. It is possible to analyze the finite sample case in the perspective of consistency if regret bound holds. However, we argue that typically results in a looser bound w.r.t. c. (i.e. (ceve) ( compared to the generalization bound as detailed in Appendix A.
4.1 Generalization Analyses
Technically, we mainly utilize the Rademacher complexity [2] and the vector-contraction in- equality [25). following the recent work [I3]. Note that, advanced techniques (26), such as local Rademacher complexity (27) can be utilized to get tighter bound w.r.t. (i.e. nz by modifying
the algorithm. But this is not our focus and we aim to analyze learning guarantees of these algorithms in the same framework and compare them fairly. Besides, we find that their learning guarantees are much dependent on the distribution imbalance. Thus, we first give the following definition.
Definition (Instance-wit wise class balanced and extremely imbalanced distribution). For a distribution P for MLC, it is said to be instance-wise class balanced if for any (x, y) sampled from P, |S |sy1 holds; it is said to be instance-wise class extremely imbalanced if for any (x. y) sampled from P. |st1 1 or [Sy]
holds
Then, we introduce the common mild assumptions for the subsequent analyses. Assumption (The common assumptions).
(1) The hypothesis class is defined in Eq. 11p.
(2) The training dataset S = {(x; y sampled i.i.d. from the distribution P, where 3 r it satisfies k(x, x) S 12 for all x E X.
(3) The base (convex) loss {(z) is p-Lipschitz continuous and bounded by B.
Then we provide the properties (including the Lipschitz constants) of surrogate losses (See Appendix B.1). The Lipschitz constants of surrogates characterize the relationship between the Rademacher complexities (24) of the loss class and the hypothesis class based on the vector-contractio inequal- ity (25). which plays central role in the generalization analysis. Next, we analyze the relationship between true and surrogate losses as follows, which to prove learning guarantees algorithms.
Lemma (The relationship between true and surrogate losses; full proof in Appendix B.2). For the RL and its surrogate losses, the following inequalities hold for any f E F and any sample (x:
1 (f()), S (x), S Tnn (f(x), I T.n, (x), S (c - 1) (f(),,)) (14) m |sy (f(x))))) < Lu, (f(x) 2 ma 1, 1,15 1, (f)
(15)
In this paper we call them balanced or extremely imbalanced distribution (or dataset) for short. 'Note that, the widely-used hinge and logistic loss are both 1-Lipschitz continuous. Although the exponential, and squared hinge losses not globally Lipschitz continuous, they are locally Lipschitz continuous.
5

---

Besides, note that laug cannot strictly upper bound Lr 1/ and Lepa i.e. L ()(), & Lua ()), (x),
$ Luz (f))
From this lemma, we can observe that when an algorithm minimizes Lug- also optimizes an upper bound of / (or Lipa) which depends on O(c). Besides, Lug and L. strictly upper bound L (or pa)) These upper bounds of I (or Epa) would help to give learning guarantees of corresponding learning algorithms w.r.t. the (partial) ranking loss in the subsequent analyses. Furthermore, we can get the relationship between true and surrogate expected risks as follows.
Lemma 2 (The relationship between true and surrogate expected risks; full proof in Appendix B.3). For any J E F and any distribution P. the following inequalities hold;
(0/((() (f) S (f) S Rpa(f) & (f)(f) S (f) S (c (cc-1) R) (f) (f) $ Rf) (f) & (f)
(16)
(17)
Remark 1. From this lemma, we can see that, among the surrogate expected risks, the pairwise surrogate expected risk Rga. provides the lightest upper bound of the true expected risk for the same
hypothesis. Thus, to study the learning guarantees of algorithms w.E.t. Lr (or Lpp ), we can first analyze their counterparts w.r.t Lpa
From above analyses, find the instance-wis wise class imbalance affects the Lipschitz constants of the surrogates and the relationship between these surrogates. Besides, it is hard to fully characterize the imbalance in real data. Thus, consider two extremely cases w.r.t. the imbalance in the following.
4.1.1 The extremely imbalanced distribution (worst case)
In this section, we analyze the learning guarantees of these algorithms for the extremely imbalanced distribution. In this case, the Lipschitz constants (See Lemma B. in Appendix B. of the surrogates are largest. Therefore, these error bounds can be viewed as the worst cases and thus hold for all the distributions just like the classical probably approximately correct (PAC) bounds [14 12 15
First, we analyze the learning guarantee of A as follows.
Theorem 1 (Learning guarantee of A for extremely imbalanced distribution (worst case)). Assume the loss Le = (c Lyz where Luz is defined in (8) Besides, Assumption I holds and suppose P is extremely imbalanced. Then, for any > O, with probability at least 5 over S, the following generalization bound holds for all f E F:
A2,² (f) S Rf) S (c-1)R Ruz (f) S (c- Rc (f) 2/2ppy
log 2 a
+ 3Be
(18)
n
2n
The full proof is in Appendix B. From this theorem, we can see that A has learning guarantee w.r.t. Lpa (or L 0/1) which depends on Oc))
Then, we provide the learning guarantee of A4 in the following theorem.
Theorem 2 (Learning guarantee of A for extremely imbalanced distribution (worst case)). Assume the loss Ls = Lug- where Lug is defined in Eq. (9. Besides, Assumption I holds and suppose P is extremely imbalanced. Then, for any 8 > with probubility at least 1 5 over S, the following generalization bound holds for all f E F:F
2
log
Ri S S S (f)(f)) Rg (f)
+ 6B
(19)
2n
The full proof is in Appendix B.3.2. From this theorem, remarkably, we can see that A has learning guarantee w.r.t. Lpa (or LD/1) which depends on O(vo), which enjoys the same order as the algorithm Ard 13 Moreover, we find that the learning guarantee of Au4 w.r.t. Lpn (or L 0/1) depends on (c) (See Appendix B.3.3).
NNte that, instead of directly bounding the 0/1 risk, we can treat our results as the upper bounds of the pairwise risk. allowing greater than 1.

---

4.1.2
The balanced distribution (best case)
Here we analyze the learning guarantees of algorithms for balanced distributions. In this case, the Lipschitz constants (See Lemma B.1 in Appendix B.1) of the surrogates are smallest. Thus, these error bounds can be viewed as the best case over all distributions, which is different from the classical PAC bounds that hold for all distributions. First, we can find that all algorithms with the univariate losses are exactly the same, which should share the same learning guarantee, and it is confirmed by the following theorem.
Theorem 3 (Learning guarantee of A 1, 1, 4 for balanced distribution (best case); full proof in Appendix B. Assume the loss LP 2Lu, EL Lug Luw where they are defined in Section 3.7 Besides, Assumption [ holds and suppose P is balanced. Then, for any 8 > 0, with
probability at least - 8 over S. the following generalization bound holds for all f E F:
Ro/1 (f) S (f) S Ruz = Rug (f) C Ruaa ( where 202 (f) = 2 fgga (f) = R2 (f) = (f).
A2,2 + +6B1
log
(20)
2
n
2n
From Theorem 3 we can observe that the model complexity term in this bound has no dependence on e. Notably, the same learning guarantee for these learning algorithms also confirms the validity of our analyses and the tightness of these bounds. Moreover, Ar also has error bound independent of e for balanced distribution (see Appendix B.4.2).
4.1.3 Comparison
For generalization analyses, a tighter upper bound usually suggests probably better performance 12 In this paper, all algorithms analyzed in the same framework and we also consider the extremely imbalanced case where the upper bounds of the Lipschitz constants in different surrogates are tight. Given that the MLC distributions (or datasets) are usually highly imbalanced, it is relatively safe to evaluate the performance of the algorithms in theory by comparing their upper bounds.
1D
We now compare the algorithms considering the cases with (approximately) imbalanced distributions.
Apa vs A A usually has a tighter bound than A² In particular, given the same hypothesis space, it is usually easier to train RS than other univariate losses, making fig smaller than others including R 11 Besides, for the model complexity terms (i.e. the last two terms), _ has an error bound of ((vc) while 4A depends on O(c).
Aua vs A22 Similarly, first risk term, (c R) is usually comparable or even larger than R 12 For the model complexity term, A has an error bound of ((vc) while A depends on O(c).
argue that A usually has tighter bound than A², For the
Overall, the tighter bound of Are (and A²a) than A indicates that A (and A²2) would probably perform better than A especially for large label space (See Fig. 3 in Appendix E). Experimental results on imbalanced benchmark datasets in Table 3 confirm our analyses.
In contrast, given balanced distributions. 2 and A share the same learning guarantee. Thus, in approximately balanced cases, " perform probably similarly to A4"..
Note that our aforementioned formal generalization analyses are mainly for two extreme cases about the distribution imbalance. As for the in-between cases of the imbalance, it is indeed highly nontrivial to consider a continuous changing imbalance level of the distribution when instances may have different numbers of positive labels, and we leave it as an important future direction.
Nevertheless, our framework can be applied to the cases where each instance has the same number of positive labels, denoted as Cp (See Appendix B.5 for details). Here set Cmán min(cp, cp} for the clarity of following discussions. Smin directly reflects the imbalance level of the distribution.
When comparing bounds, it is usually more reasonable to compare the order of dependent variables rather than comparing the absolute values.
Although we can not formally express claim, we empirically observed it experiments. In some cases, the first risk term may be bigger than but we can still take insights from the error bound through the dependent variables of the model complexity.
7

---

Note that the extremely imbalanced case (cp = 1 or Cp c - 1) and the balanced one (cp = c/ are included. According to these results, we can observe that APa has an error bound of O c that is the same as A while A depends on O Giman Therefore, in an imbalanced case (not necessarily the extremely imbalanced ones), A and A usually have better bounds than A which probably indicates their better performance over A in practice.
Besides, when с is in an extreme scale, such as millions or more, the O(c) computational time complexity for loss functions is prohibitive, and practitioners often resort to various negative sampling methods. While this not the focus of this paper, our theoretical results indeed indicate that the univariate loss Lus would probably enjoy better performance than other univariate ones w.r.t. (partial) ranking loss, thus its estimator by use of negative sampling methods may be preferred in practice.
4.2 Consistency Analyses
Following 9 8 we consider the general partial ranking loss as follows:
1 (f(x)))))))) at Σ
[1,(()) < fx(x)] + 1
= f((x)]
(21)
(P-g)es) xSy
where ay is a positive penalty. Note that the losses in Eq. (2) is a special case of Eq. 21 with
Qy 1157 respectively. The general ranking loss can be defined in a similar way as Eq. (2I)
For clarity and generality, we define the general reweighted univariate surrogate loss as follows:
Lu(f(x),))
(22)
j=1
where Stt and By are penalties for the positive and negative labels respectively. We assume 8 By > 0 for convenience in our analyses. Note that the penalties can be different and all univariate surrogate losses presented in Section 3.1 are special cases of Eq. (22 (See Table 2 for details.)
Let (x, P(y[x)) denote the set of the Bayes predictors of a loss L given a sample x and a conditional distribution P(ylx). Remarkably, [8] provided sufficient and necessary condition for determining whether surrogate loss to be (Fisher) consistent w.r.t. the (partial) ranking loss or not (See Lemma 3 in Appendix C). Checking the consistency of a new surrogate loss using Lemma takes additional efforts, because one has to enumerate all conditional distributions. For the loss in Eq. (22), we present more intuitive characterization that only involves the penalties in Theorem 4 considering various base losses (See Proposition in Appendix C for the results of the Hinge loss):
Theorem 4 (Necessary condition for the consistency of Eq. (2) w.r.t. Eq. (2I with exponential, logistic or squared hinge loss). A general reweighted univariate surrogate loss in Eq. (22) with {(z) e e {(2) In(1 + e =) or E(2) (max(0, 2}}² 2-)²2x2 is consistent w.r.t. the general partial
ranking loss in Eq. 21 only Er > 0, 9 By = ra for all such that 1 - - Eisise Vj c-
For clarity, see full proof in Appendix C. When c S 3, the penalties of Lu,, Lus and La, may coincide with that of Luz up multiplicative constant. When e > 4. it is straightforward to construct counter examples that violate the necessary condition in Theorem 4 and obtain the Corollary [ as follows.
Corollary (Inconsistency of Tru Trug and Tay w.r.t. Eq. with exponential, logistic or squared hinge loss). If e 2 4, Lay. Lus and Lus with f(z) = or E(z) In(1 + e e=$) 3) or E(z) =
(ma 1 ² are inconsistent w.r.t the partial ranking loss in Eq.
We further show the inconsistency of the general reweighted univariate loss in Eq. (22) w.r.t. the general partial ranking loss in Eq. 21 with hinge loss. Note that this includes the inconsistency of Lug Lua
Table 2: The penalties of the specific univariate losses w.r.t. the general reweighted form in Eq. (22).
and L., w.r.t. Eq. (2).
Loss
Lun
Lug
Lug
L.s
An immediate conclusion from Corollary I is that Luy, Luy and Ly, are inconsis- tent w.r.t the RL in Eq. (T) because B, on (x, P(ylx)) C B,o o/ (x, P(y[x)) g
1/85 1/87
c
| |
min(1551.1s5)
c
[Syl
min
18
8

---

Compared to existing work (9 1 although Theorem is negative, it considers surrogate losses in more general reweighted form, i.c Eq. (22). which may be of independent interest.
Related Work
Here we mainly review the theoretical work relevant to this paper in MLC and MLR.
Consistency. | studied the consistency of various surrogate losses w.r.t. Hamming and (partial) ranking loss. Remarkably, [9] presented an explicit regret bound w.r.t. partial ranking loss for Tug-- Extensive work investigated the consistency w.r.t. other measures, especially the F-measure. For instance, [28] provided justifications and connections w.r.t. the F-measure using the empirical utility maximization (EUM) framework and the pecision-thhoretic approach (DTA) in binary classification, which were applied to the optimization of the macro-F measure in MLC. Further, [29] studied connections and differences between these two frameworks and clarified the notions of consistency w.r.t many complex measures (e.g., the Jaccard measure) in binary classification/
[3 Besides, prior
work 30 31 studied the consistency of the F-measure in MLC from the DTA perspective via different approaches to estimate the conditional distribution P(y x). [22 devoted to the study of consistent multi-label classifiers w.r.f. various measures under the EUM framework.
33 investigated the multi-label consistency of various reduction methods w.r.t. precision l: and @ecall@k: measures.
Generalization analysis. [3] studied the generalization bounds of the algorithms based Lpa and Lu, w.r.t. the ranking loss besides the Hamming loss and Subset Accuracy.
Technically, our generalization and consistency analyses for MLC mainly follow the prior work L and ( respectively.
We mention that a specific form of Eq. with base hinge loss has been used as part of prior work 34), which achieves excellent empirical results MIC. comparison, this paper considers more general form of such reweighted surrogate losses and provides formal consistency and generalization analyses, which have not been investigated in the literature to our knowledge.
Experiments
As theoretical work, the primary goal of experiments is to corroborate our theoretical findings rather than showing the empirical superiority of the proposed algorithm. Therefore, we evaluate all algorithms in Section w.r.t the ranking loss on 10 widely-used benchmark datasets with various domains and sizes of label and data. The detailed statistics and access of these datasets are given in Appendix D. For all algorithms, fair comparison. Besides, we use the same efficient stochastic algorithm (i.e. SVRG-BB [35] to solve these convex optimization problems. Moreover, search the typer-paramedd from a wide range of {10 10 ,.... ,,,,,........,. ) using 3-fold cross validation on each dataset
utilize linear models with the base logistic loss for simplicity and
À for all algorithms
...
The experimental results are summarized in Table (see Appendix E for complete results with standard deviations). First, we observe that A and A lss outperform the others especially 4 on almost all benchmarks. It verifies our generalization analyses: in extremely imbalanced distributions case, Araa and ns usually have tighter bound than others, especially A where benchmarks are usually highly imbalanced shown in Appendix E (Fig. 2). Besides, such results do not contradict with the consistency results since two assumptions in consistency analyses are violated the real settings. The first one is that the Bayes predictor may not be linear and the second one is that the number of samples may not be sufficient to achieve the Bayes predictor, which explains the relatively weaker results of _
To further study the effect of e, we evaluate 4n and 4 on highly imbalanced semi-synthetic datasets with randomly selected e based on the delicious dataset (See Fig. 3 in Appendix E for details).
13 Note that, our generalization and consistency analyses are both under FUM framework. 'Our code is available at uttttps://github www. hwtp////ooogogggggoooooooo//.... theory

---

Table 3: Ranking loss of all five algorithms on benchmark datasets. On each dataset, the top two algorithms are highlighted in bold and the top one is labelled with 1. The number in the parentheses denotes the label size of the corresponding dataset. Besides, "_" means that A takes more than a week using 48-core CPU server on the delicious dataset (see Fig. 1 in Appendix E for quantitative results).
Dataset
AP
AM
A
A
A
emotions(6)
0.1511
0.1538
0.1587
0.1530
0.1616
image(5)
0.1625
0.1642
0.1653
0.1645
0.1678
scene(6)
0.0696
0.0809
0.0821
0.0768
0.0806
yeast(14)
0.1766
0.1768
0.1785
0.1767
0.1816
enron(53)
0.0682
0.0724
0.0696
0.0698
0.0715
(1V1-subset((001)
0.0361
0.0418
0.0392
0.0368
0.0391
bibtex(1.59)
0.0516
0.0545
0.0551
0.0401
0.0538
core15k(374)
0.1081
0.1091
0.1099
0.1063
0.1096
mediamill(101)
0.0395
0.0402
0.0412
0.0389
0.0405
delicious(983)
0.0960
0.0974
0.0946*
0.0978
Time complexity
(ce²)
((c)
((c)
O(c)
O(c)
We find that A would probably perform better than A with larger c, which also confirms our theoretical findings: in the extremely imbalanced case, A has tighter bound than A w.r.t. c. [
Furthermore, to study whether the upper bound for the generalization error can reflect on the true generalization error reasonably well, we conduct experiments on the semi-synthetic delicious datasets, where the result is shown in Appendix (Table 3). We find that despite the absolute values of probabilistic upper bounds (PUB) might not reflect on the true generalization error reasonably well, the PUB (and expected surrogate pairwise risk) can still offer valuable insights into these learning algorithms under the same analysis framework (See Appendix E for details).
7 Conclusion and Discussion
This paper presents systematic study from two complementary perspectives of consistency and gen- eralization bounds of algorithms in multi-label ranking. Theoretically, we find that the instance-wist class imbalance and the label size of the datasets play an important role in their learning guarantees. In particular, for the extremely imbalanced case, existing algorithms with consistent univariate losses have an error bound of (cc) while the ones with inconsistent pairwise losses depend on O O(ve) [13] which can explain the superior performance of pairwise methods on highly imbalanced datasets in practice. Moreover, we present one inconsistent reweighted surrogate univariate loss-based algorithm which enjoys an error bound (c) which is nearly the same as the pairwise ones. For the balanced case, all the algorithms with the univariate losses share the same error bound with no dependence on c, which is the same as the pairwise ones. Finally, empirical results corroborate theoretical findings.
For generalization analyses, we consider two extreme cases about the instance- wise class imbalance of the data distribution, and it may be better for fine-grained analyses through integrating other properties of the distribution. Besides, how to make these bounds tighter will inspire new learning algorithms. For the consistency analyses, we only consider classical Fisher consistency, and it may be better to take the hypothesis set into account, such as H-consistency [36).
Acknowledgements
This work was supported by NSFC Projects (Nos. 61620106010, 62061136001, 616211 U1811461, U19B2034, U19A2081), Beijing NSF Project (No. JQ19016), Tsinghua-Bosse -oochh Joint Center for Machine Learning, Beijing Academy of Artificial Intelligence (BAAI), a grant from Tsinghua Institute for Guo Qiang, Tiangong Institute for Intelligent Computing, and the NVIDIA NVAIL Program with GPU/DGX Acceleration.
15 NNotabyy, it is nontrivial to directly plot the complexity rate of c on synthyyntettic data. This is because when we change c, we also change the data distribution, while the generalization errors among different data distributions are not directly comparable.
10

---

References
[1] Andrew Kachites McCallum. Multi-label text classification with mixture model trained by EM. In AAAI 99 workshop Text Learning. Citeseer, 1999.
[2] Robert E Schapire and Yoram Singer. Boostexter: A boosting-based system for text categoriza- tion. Machine Learning, 39(2):335-168, 2000.
[3] André Elisseeff, Jason Weston, et al. kernel method for multi-labelled classification. In Advances in Neural Information Processing Systems, volume 14, pages 681-687, 2001.
[4] Gustavo Carneiro, Antoni B Chan, Pedro J Moreno, and Nuno Vasconcelos. Supervised learning of semantic classes for image annotation and retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(3):394 410, 2007.
[5] Kai Yu, Shipeng Yu, and Volker Tresp. Multi-label informed latent semantic indexing. In ACM SIGIR Conference on Research and Development in Information Retrieval, pages 258-265, 2005.
[6] Min-Ling Zhang and Zhi-Hua Zhou. A review on multi-label learning algorithms. IEEE Transactions on Knowledge and Data Engineering, 26(8):1819-183) 2014.
[7] Xi-Zhu Wu and Zhi-Hua Zhou. A unified view of multi-label performance measures. In International Conference on Machine Learning, pages 3780-3788. PMLR, 2017.
[8] Wei Gao and Zhi-Hua Zhou. On the consistency multi-label learning. Artificial Intelligence, 199(1):22-44 2013.
[9] Krzysztof Dembezynski, Wojciech Kotlowski, and Eyke Hüllermeier. Consistent multilabel ranking through univariate loss minimization. In International Conference on Machine Learning. pages 1347-1354, 2012.
[10] Tong Zhang. Statistical behavior and consistency of classification methods based convex risk minimization. The Annals of Statistics, 32(1):56-85, 2004.
[11] Peter I. Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, (318473) 2006.
[12] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
[13] Guoqiang Wu and Jun Zhu. Multi-label classification: do hamming loss and subset accuracy really conflict with each other? In Advances in Neural Information Processing Systems, 2020.
[14] Leslic G Valiant. A theory of the learnable. Communications of the ACM, 17411::11441114 1984.
[15] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[16] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
[17] Ofer Dekel, Yoram Singer, and Christopher D Manning. Log- linear models for label ranking. In Advances in Neural Information Processing Systems, pages 497-504, 2003.
[18] Min-Ling Zhang and Zhi-Hua Zhou. Multilabel neural networks with applications to functional genomics and text categorization. IEEE Transactions Knowledge and Data Engineering, 18(10):1388113 1351, 2006.
[19] Matthew R Boutell, Jiebo Luo, Xipeng Shen, and Christopher M Brown. Learning multi-label scene classification. Pattern Recognition, 1757-1777,, 2004.
[20] Bharath Hariharan, Lihi Zelnik-Manor, Manik Varma, and Svn Vishwanathan. Large scale max-margin multi-label classification with priors. In International Conference on Machine Learning, pages 423-430. Citescer, 2010.

---

[21] Zhi-Har Tan, Peng Tan, Yuan Jiang, and Zhi-Hua Zhou. Multi-label optimal margin distribution machine. Machine Learning, 109(3):623 642, 2020.
[22] Guoqiang Wu, Ruobing Zheng, Yingjie Tian, and Dalian Liu. Joint ranking svm and binary relevance with robust low-rank learning for multi-label classification. Neural Networks, 122:24- 39, 2020.
[23] Martin Anthony and Peter I. Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009.
[24] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463448, 2002.
[25] Andreas Maurer. A vector-contraction inequality for rademacher complexities. International Conference Algorithmic Learning Theory, pages 3-17. Springer, 2016.
[26] Yunwen Lei, Ürün Dogan, Ding-Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classificatton.. IEEE Transactions on Information Theory, 65(5):2995- 3021, 2019.
[27] Peter L Bartlett, Olivier Bousquet, Shahar Mendelson, et al. Local rademacher complexities. The Annals of Statistics, 3374)1149711537, 2005.
[28] Nan Ye, Kian Ming Chai, Wee Sun Lee, and Hai Leong Chicu. Optimizing f-measures: a tale of two approaches. In International Conference on Machine Learning, pages 289-296. Omnipress, 2012.
[29] Krzysztof Dembezyíski, Wojciech Kotlowski, Oluwasanmi Koyejo, and Nagarajan Natarajan. Consistency analysis for binary classification revisited. In International Conference on Machine Learning, pages 961-969. PMLR, 2017.
[30] Willem Waegeman, Krzysztof Dembezyáski, Arkadiusz Jachnik, Weiwei Cheng, and Eyke Hüllermeier. On the bayes-optimality of f-measure maximizers. Journal of Machine Learning Research, 15:3333-333 3388,, 2014.
[31] Mingyuan Zhang, Harish Guruprasad Ramaswamy, and Shivani Agarwal. Convex calibrated surrogates for the multi-label f-measure. In International Conference on Machine Learning. pages 11246-111 11255. PMLR, 2020.
[32] Oluwasanmi Koyejo, Nagarajan Natarajan, Pradeep Ravikumar, and Inderjit S Dhillon. Consis- tent multilabel classification. In Advances in Neural Information Processing Systems, volume 29, pages 3321-3329, 2015.
[33] Aditya K Menon, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Multilabel reductions: what is my loss optimising? In Advances in Neural Information Processing Systems, pages 10599-10610, 2019.
[34] Miao Xu, Yu-Feng Li, and Zhi-Hua Zhou. Robust multi-label learning with pro loss. IEEE Transactions on Knowledge and Data Engineering, 3200):16101162, 2019.
[35] Conghui Tan, Shiqian Ma, Yu-Hong Dai, and Yuqiu Qian. Barzilai-borwein step size for stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 685-693, 2016.
[36] Mingyuan Zhang and Shivani Agarwal. Bayes consistency vs. h-consistency: The interplay between surrogate loss functions and the scoring function class, Advances in Neural Information Processing Systems, 33, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [No] We are not aware of potential negative societal impacts currently since this is theoretical work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B and Appendix C
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See https://github: www.
Guoggianggooddrroo///LLRRR-- theory
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] can always achieve the global optima since our learning algorithms are all convex optimization problems.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See the supplemental material.
(b) Did you mention the license of the assets? [Yes] See the supplemental material.
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "vVath7EWsDv", "reviewer": "Reviewer_z9MC", "summary": "This paper attempts to fill the gap between existing theory and practice for Multi-Label Ranking (MLR) problems: why inconsistent pairwise losses often achieve better performance in practice than consistent univariate losses? The authors try to answer this question from the prospective of generalization error bounds, besides the consistency.  Two factors of the distribution (from which the data is drawn) are identified that affect the learning guarantee. Motivated by the observation, the authors propose two new surrogate losses, one of which not only enjoys nearly the similar performance as the popular pairwise surrogate loss, but is also computationally more efficient. The results are well-supported with theoretical results and empirical studies.\n\nOverall I think the paper is clear and well executed.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Thanks for this interesting and well-written paper. Below are comments for each dimension.\n\nOriginality.\nThis paper tries to rigorously study this question in MLR: why inconsistent pairwise losses often achieve better performance in practice than consistent univariate losses? The authors answer the question from the angle of generalization error bounds and consistency analyses. Overall this work is original, though the techniques are standard. Although the relevant papers are cited, the related work section (Section 5) is somewhat inadequate. It would be better if the authors can explain more how this paper is related to the papers discussed in Section 5.\n\nQuality.\nThe method and the claims are overall correct, though I did not verify the proofs line by line. The empirical study is valid and supports the theoretical claims. The authors are honest about the weakness of their work (e.g. they make it clear that the proposed algorithms are not consistent). My only concern is about comparing upper bounds for the generalization errors (see comment below).\n\nClarity.\nThe paper is well-written and well-organized. \n\nSignificance.\nThis paper attempts to solve an interesting, important and practical problem in MLR from the theoretical prospective: why some inconsistent algorithms can often outperform consistent algorithms on real data sets. The question itself is important and valuable to the multi-label community. The study in this paper can potentially inspire new algorithms that not only can perform well in practice, but also enjoy some theoretical guarantees. However, I find that the main technique used (comparing upper bounds for the generalization error) is somewhat limited and may not generalize easily to other settings (e.g. distributions other than extremely imbalanced and balanced).\n\n---\n\nExtra comments:\n\nMy concern is how well the upper bound for the generalization error can reflect on the true generalization error. I know that it might be difficult (or even impossible) to directly compare generalization errors of different algorithms, so I can see why the authors choose to compare the upper bounds, and I agree this is a valid approach because a tighter upper bound usually suggests better performance. I have read the improvements the authors made since the ICML 2021 submission, and I can see that the authors have added more discussions about the upper bounds to provide more insights and justifications. I still think it might be better if the authors could show some synthetic experiments justifying the use of upper bounds. The advantage of synthetic experiments is that the generalization error can be calculated, so that one can see if the upper bound for the generalization error can reflect on the true generalization error reasonably well.\n\n---\n\nTypo:\n\nPage 9, line 343: \"two extremely cases\" -> \"two extreme cases\"\n\n---\n\nAfter rebuttal: Thank the authors for providing additional results. I keep my rating for this paper.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "gxlGs6Gij5y", "reviewer": "Reviewer_PG73", "summary": "This paper provides theoretical studies on the ranking loss in multi-label learning. For ranking loss, usually, two surrogate losses are used: pairwise and univariate. The paper is motivated by the fact that the pairwise surrogate loss is theoretically unfavored but empirically well performed. To study the surrogate losses, the paper analyzed the original loss function and some proposed reweighting of the loss function by both consistency and generalization analysis. The generalization analysis is conducted by analyzing the upper-bound relationship between different loss functions and the corresponding risks. This analysis shows that the instance-wise class imbalance affects the relationship between these surrogate losses. The paper further analyzed the generalization performance for two extreme cases: extremely imbalanced (all predictions are zero or one for one instance) and absolutely balanced (exact half of the predictions are one for an instance). The paper further analyzed the consistency of these surrogate loss functions and gave some experimental results.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is a theoretical study, analyzing commonly used surrogate losses for ranking loss in multi-label learning. The paper is motivated by the gap between existing theory and practice for the commonly used pairwise surrogate loss and univariate surrogate loss. I think this direction is novel and worth study. It can contribute to multi-label learning in both theoretical and practical aspects. \n\nThe paper proposes two reweighted versions of the univariate losses and analyzed the relationship between these surrogate loss functions, and the generalization error of the algorithms optimizing these loss functions. The most interesting part of the study is it tries to discuss the relationship between the “balance” per instance and the choice of surrogate loss functions. This part provides the most informative insight of the study: pairwise surrogate loss is favoured if data are imbalanced at the instance level. However, the study is based on two extreme cases of imbalance, and there is no study on the in-between cases, or analyze how the surrogate loss’s performance is impacted by a continuous changing imbalance level. \n\nGenerally, the paper is clearly written and easy to follow. Especially it gives a thorough intuitive explanation and insights drawn after each formal theoretical result. This may enlarge the impact of the paper to more general readers due to the efficient delivery of its idea.\n\nAfter rebuttal:\nI appreciate the authors' rebuttal in addressing one special case of imbalanced learning out of the two extreme cases in the paper. I keep my positive rate for this paper. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "YCFO78hsZF8", "reviewer": "Reviewer_95pY", "summary": "This paper analyzes theoretically the consistency and the generalization error of multilabel ranking algorithms. More specifically, some generalization error bounds are obtained for different loss functions, that are surrogates of the ranking loss or the partial ranking loss. \n\nThe analysis is restricted to two extreme cases: (1) instance-wise class balanced distribution (when the number of positive and negative classes is the same for all samples), and (2) extremely imbalanced distribution (when only one class is positive or only one class is negative, for all samples).  It turns out that, while the generalization error bounds for the balanced case are independent on the number of classes, $c$, the  bounds for the imbalanced case are $O(c)$ for some univariate losses (like $L_{u_2}$)  while it is $O(\\sqrt{c})$ for pairwise losses (like $L_{pa}$). \n\nSince, in practice, real datasets are highly imbalanced, the theoretical results might explain why $L_{pa}$ shows a better performance than $L_{pa}$ in the experiments with finite datasets, even thought only the latter is consistent.\n\nBased on these findings, the paper proposes some re-weighting versions of the univariate losses with $O(\\sqrt{c})$ generalization bounds. The consistency is lost, but some of the reweighting version of $L_{u_2}$ (in particular, $L_{u_3}$) outperform $L_{u_2}$  in the experiments.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of this paper is theoretical. The paper shows some generalization error bounds that can provide a better understanding of multi-label ranking (MLR) algorithms. In particular, the paper highlights the relevance of the class imbalance as a key factor in the behavior of MLR algorithms.\n\nUp to my knowledge, the contribution of the paper is original. Sec. 5 provides some related work. In particular, the reweighting scheme in Eq. (9) was proposed before with base hinge loss, though it is analyzed here in a more general context.\n\nThe experimental results are aimed to corroborate the theoretical results, and, in particular, to verify the influence of the re-weighting scheme on the classification performance. Although the value of the experimental work is limited for a practitioner, the paper may suggest that, using a re-weighting scheme for univariate losses is advisable for datasets with large $c$ and class imbalance.\n\nI have checked only about 30% of the proofs, but they are technically correct, under my view.\n\nSummarizing, the paper may have a small expected impact on real applications, but the theoretical contribution is valuable.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors and the reviewer are not aware of potential negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ThfkbE_wRGh", "reviewer": "Reviewer_5DsC", "summary": "This paper studies theoretical analysis such as generalization error and consistency of the pairwise and univariate (i.e., pointwise) loss functions for multi-label classification. The main contributions are two folds: (1) propose two reweighted convex surrogate pointwise losses (2) consider the number of labels and the label imbalance into the theoretical analysis.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the theoretical analysis of generalization error bound and consistency seems technically sound. The writing is clear and the presentation is comfortable to follow. I outline some detailed questions or comments below.\n\nQ1: The assumption of class imbalance in Definition 1 seems too strict. In practice, for large-scale multi-label classification datasets, we often see the number of labels following a long tail distribution and the number of labels per instance is in the order of log(L), where L is the number of labels. Are you able to extend the theoretical analysis for such a case?\n\nQ2: Following Q1, when L is in an extreme scale, such as millions or more, the O(L) computation time complexity for loss functions is prohibitive, and practitioners often resort to various negative sampling methods. While this is not the main focus of this work, perhaps it would be more informative to readers by adding one paragraph regarding this aspect.\n\nQ3: This manuscript would be more strong If there’s some simulated studies that verify the complexity rate of the generalization error as stated in Table 1. For example, we can simulate the imbalance label distribution from some P(x,y), and learn the OVA classifiers with L_{pa}, L_{u_k}, k=1,..,4 and compare their generalization error when the number of class L grows.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative social impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and I agree that this paper offers several valuable insights, both theoretically and empirically, into a class of methods for multi-label classification. I also agree with a reviewer that error bounds are not necessarily the best proxies for the actual error, and that the authors should include additional content on this point, e.g., through simulation studies as suggested by the reviewer, in the final version.
Decision: Accept (Poster)