Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization
Year: 2021

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( √ 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( √ c) for promising performance as well as the computational efficiency of univariate losses. Finally, experimental results confirm our theoretical findings.

text: √ 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( √ c) for promising performance as well as the computational efficiency of univariate losses. Finally, experimental results confirm our theoretical findings.

heading: 1 Introduction
text: Multi-Label Classification (MLC) [1] is an important task, in which each instance is associated with multiple labels simultaneously. It has been widely applied to text categorization [2], bioinformatics [3], multimedia annotation [4], information retrieval [5]. Various measures [6, 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) [2, 8] is a commonly used measure in practice (or in theory). Formally, the RL calculates the fraction of pairs that a positive label does not precede a negative label according to the rank given by a score function (or predictor). Minimizing such a 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 in terms of computational costs, theory and empirical performance.
∗Equal contribution. G. Wu is now at School of Software, Shandong University and C. Li is now at Gaoling School of AI, Renmin University of China. The work was done when they were at Tsinghua University. †Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Computationally, the pairwise losses, defined over pairs of positive and negative labels, have a complexity depending on O(c2) (c is the number of labels), while the univariate ones enjoy a complexity depending on O(c). The superiority of the latter is significant when c is large. Theoretically, the pairwise losses are not (Fisher) consistent w.r.t. the RL or the PRL [8], while, remarkably, certain univariate ones are consistent w.r.t. the PRL [9, 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-perform the latter on 10 MLR benchmarks (see results in Table 3). 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 to improve the univariate loss, which is preferable due to its computational efficiency? A natural explanation of this gap is that although the (Fisher) consistency [10, 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 a 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-wise class imbalance and the label number c. Given extremely imbalanced data (i.e., the worst case), we prove that the consistent univariate losses based algorithms lead to an error bound ofO(c) while the pairwise losses based ones enjoy an error bound depending on O( √ c) [13], which explains the empirical behaviour better on real datasets which are usually highly imbalanced (see Table 3). 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 O( √ c) 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 c 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 [14, 12, 15] which hold for all distributions (i.e. the worst case). Our main theoretical results are summarized in Table 1. Experimental results also confirm our theoretical findings.

heading: 2 Preliminaries
text: 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, ai, aj and aij denote its i-th row, j-th column, and (i, j)-th element respectively. For a vector a, ai denote its i-th element. For a set, | · | denotes the cardinality. [[π]] denotes the indicator function, i.e., [[π]] = 1 if the proposition π holds and 0 otherwise.

heading: 2.1 Problem Setting
text: Let x ∈ X ⊂ Rd and y ∈ Y ⊂ {−1,+1}c denote the input and output respectively, where d is the feature dimension, c is the label size. yj = 1 (or−1) indicates that the associated j-th label is relevant (or irrelevant). Given a training set S = {(xi,yi)}ni=1 of n samples i.i.d. drawn from a distribution P over X × Y , the original goal of MLC is to learn a multi-label classifier H : Rd → {−1,+1}c. To solve MLC, a common approach is to first learn a vector-based score function (or predictor) f = [f1, ..., fc] : Rd → Rc and then get the classifier H by a 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.

heading: 2.2 Evaluation Measures
text: 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.3
Ranking Loss (RL):
L0/1r (f(x),y) = 1 |S+y ||S−y | ∑
(p,q)∈S+y ×S−y
[[fp(x) ≤ fq(x)]], (1)
where S+y (or S − y ) denotes the relevant (or irrelevant) label index set induced by y.
Partial Ranking Loss (PRL):4
L0/1pr (f(x),y) = 1 |S+y ||S−y | ∑
(p,q)∈S+y ×S−y
[ [[fp(x) < fq(x)]] + 1
2 [[fp(x) = fq(x)]]
] . (2)
Note that the only difference between these two measures is the penalty when fp(x) = fq(x) holds. Besides, it is easy to verify that RL upper bounds PRL, i.e. L0/1pr (f(x),y) ≤ L0/1r (f(x),y). 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].

heading: 2.3 Risk and Regret
text: Since RL is non-convex and discontinuous, often leading to NP-hard problems [16], it is optimized with convex surrogates in practice for computational efficiency. Define a surrogate loss Lφ : Rc × {−1,+1}c → R+, where φ indicates the specific surrogate loss and will be detailed in the next section. Besides, define a vector-based predictor class F = {f : X → Rc}. For a predictor f ∈ F , its true (0/1) expected risk, surrogate expected risk, and surrogate empirical risk are defined as:
R0/1(f) = E (x,y)∼P [L0/1(f(x),y)], Rφ(f) = E (x,y)∼P
[Lφ(f(x),y)], R̂S(f) = 1
n n∑ i=1 Lφ(f(xi),yi).
Besides, we use a superscript (i.e., pr or 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∼P (y|x) [L(f(x),y)|x] = ∑ y L(f(x),y)P (y|x), (3)
where L denotes the true or surrogate loss. Thus, the expected risk of f is R(f) = Ex∼P (x)[R(f |x)].
For each x, given the conditional distribution P (y|x), we can get its optimal predictions as follows:5
f∗(x) = arg min a∈Rc ∑ y L(a,y)P (y|x), (4)
where f∗ is called the Bayes predictor w.r.t. the loss L. Besides, the expected risk of f∗ (i.e., R(f∗)) is called the Bayes risk, which is the minimal expected risk w.r.t. the loss L and denoted by R∗ for
3Our definition is over one sample and can be averaged over multiple samples. 4Minimizing the PRL is equivalent to maximize the instance-AUC. 5Notably, the optimal predictions can be not just one value but a set with many elements that share the same
minimal conditional risk.
convenience. Then, we can define the regret (a.k.a. excess risk) of a predictor f w.r.t. the true and surrogate loss as follows.
Reg0/1(f) = R0/1(f)−R∗0/1, Regφ(f) = Rφ(f)−R ∗ φ. (5)
Besides, we also use a superscript (i.e., pr or r) to distinguish the regrets for specific measures. Moreover, let f̂n denote the learned predictor from finite training data S. Note that our goal is to find a predictor f̂n that achieves the minimal true regret (i.e. Reg0/1(f̂n)) as possible as it can.

heading: 3 Methods
text: In this section, we first introduce several specific surrogate losses. Then, we present their associated learning algorithms.

heading: 3.1 Surrogate Losses
text: To optimize the RL, it is natural to employ the convex surrogate pairwise loss [2, 3, 17, 18] as:
Lpa(f(x),y) = 1 |S+y ||S−y | ∑
(p,q)∈S+y ×S−y
`(fp(x)− fq(x)). (6)
where the base (margin-based) convex loss `(z) can be defined in various popular forms, such as the exponential loss `(z) = e−z , the logistic loss `(z) = ln(1 + e−z), the hinge loss `(z) = max{0, 1 − z}, and squared hinge loss `(z) = (max{0, 1 − z})2. A common property is that the base convex surrogate loss upper bounds the original 0/1 loss,6 i.e., [[z ≤ 0]] ≤ `(z). Besides, the surrogate univariate loss, which primarily aims to optimize Hamming loss [19, 13], can also be viewed as a surrogate loss for the RL, which is defined as follows:
Lu1(f(x),y) = 1
c c∑ j=1 `(yjfj(x)). (7)
Notably, Lu1 cannot strictly upper bound the RL, i.e. L 0/1 r (f(x),y) Lu1(f(x),y). Previous work presents the consistent surrogate univariate loss [9, 8] w.r.t. PRL, which is defined as follows:
Lu2(f(x),y) = 1
|S+y ||S−y | c∑ j=1 `(yjfj(x)). (8)
Again, the consistent surrogate loss Lu2 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 as below.
Lu3(f(x),y) =
∑ p∈S+y `(ypfp(x))
|S+y | +
∑ q∈S−y `(yqfq(x))
|S−y | , (9)
Lu4(f(x),y) = 1
min{|S+y |, |S−y |} c∑ j=1 `(yjfj(x)). (10)
For a clear presentation, we will formally discuss their relationships in the next section.

heading: 3.2 Learning Algorithms
text: In the following, we consider the kernel-based learning algorithms which have been widely used in practice [3, 19, 20, 21, 22] 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 κ, where κ : X × X → R is a Positive Definite Symmetric (PDS) kernel. Let Φ : X → H be a feature mapping associated with κ. The kernel-based hypothesis class can be defined as follows.
F = { x 7→W>Φ(x) : W = (w1, . . . ,wc)>, ‖W‖ ≤ Λ } , (11)
6The original logistic loss can be easily changed to `(z) = log2(1 + 2 −z) to satisfy this condition.
where ‖W‖ denotes ‖W‖H,2 = ( ∑c j=1 ‖wj‖2H)1/2 for convenience.
Here we consider the following five learning algorithms with the corresponding aforementioned surrogate losses. They can be formulated as follows with λ denoting a trade-off hyper-parameter:
Apa : min W
1
n n∑ i=1 Lpa(f(xi),yi) + λ‖W‖2, (12)
Auk : min W
1
n n∑ i=1 Luk(f(xi),yi) + λ‖W‖2, k = 1, 2, 3, 4. (13)

heading: 4 Theoretical Analyses
text: 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 to the Bayes risk [11, 8] when samples goes to infinity. It 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 a constrained hypothesis class. It is possible to analyze the finite sample case in the perspective of consistency if a regret bound holds. However, we argue that it typically results in a looser bound w.r.t. c (i.e. O(c √ c)) compared to the generalization bound as detailed in Appendix A.

heading: 4.1 Generalization Analyses
text: Technically, we mainly utilize the Rademacher complexity [24] and the vector-contraction inequality [25], following the recent work [13]. Note that, advanced techniques [26], such as local Rademacher complexity [27] can be utilized to get tighter bound w.r.t. n (i.e. O( 1n )) 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 1 (Instance-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+y | = |S−y | holds; it is said to be instance-wise class extremely imbalanced if for any (x,y) sampled from P , |S+y | = 1 or |S−y | = 1 holds.7
Then, we introduce the common mild assumptions for the subsequent analyses. Assumption 1 (The common assumptions).
(1) The hypothesis class is defined in Eq.(11). (2) The training dataset S = {(xi,yi)}ni=1 is sampled i.i.d. from the distribution P , where ∃ r > 0,
it satisfies κ(x,x) ≤ r2 for all x ∈ X . (3) The base (convex) loss `(z) is ρ-Lipschitz continuous and bounded by B. 8
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-contraction inequality [25], which plays a central role in the generalization analysis. Next, we analyze the relationship between true and surrogate losses as follows, which to prove learning guarantees of algorithms. Lemma 1 (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 ∈ F and any sample (x,y): L0/1r (f(x),y) ≤ Lpa(f(x),y) ≤ Lu3(f(x),y) ≤ Lu4(f(x),y) ≤ (c− 1)Lu2(f(x),y), (14) min{|S+y |, |S−y |}Lu2(f(x),y) ≤ Lu3(f(x),y) ≤ max{|S+y |, |S−y |}Lu2(f(x),y). (15) 7In this paper we call them balanced or extremely imbalanced distribution (or dataset) for short. 8Note that, the widely-used hinge and logistic loss are both 1-Lipschitz continuous. Although the exponential, and squared hinge losses are not globally Lipschitz continuous, they are locally Lipschitz continuous.
Besides, note that Lu2 cannot strictly upper bound L 0/1 r and Lpa, i.e.,
L0/1r (f(x),y) Lu2(f(x),y), Lpa(f(x),y) Lu2(f(x),y).
From this lemma, we can observe that when an algorithm minimizes Lu2 , it also optimizes an upper bound of L0/1r (or Lpa) which depends on O(c). Besides, Lu3 and Lu4 strictly upper bound L 0/1 r (or Lpa). These upper bounds of L 0/1 r (or Lpa) 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 f ∈ F and any distribution P , the following inequalities hold:
Rpr0/1(f) ≤ R r 0/1(f) ≤ Rpa(f) ≤ Ru3(f) ≤ Ru4(f) ≤ (c− 1)Ru2(f), (16)
Rr0/1(f) Ru2(f), Rpa(f) Ru2(f). (17)
Remark 1. From this lemma, we can see that, among the surrogate expected risks, the pairwise surrogate expected risk Rpa provides the tightest upper bound of the true expected risk for the same hypothesis. Thus, to study the learning guarantees of algorithms w.r.t. L0/1r (or L 0/1 pr ), we can first analyze their counterparts w.r.t. Lpa. 9
From above analyses, we find the instance-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, we consider two extremely cases w.r.t. the imbalance in the following.

heading: 4.1.1 The extremely imbalanced distribution (worst case)
text: 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.1 in Appendix B.1) 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 Au2 , as follows. Theorem 1 (Learning guarantee of Au2 for extremely imbalanced distribution (worst case)). Assume the loss Lφ = (c− 1)Lu2 , where Lu2 is defined in Eq.(8). Besides, Assumption 1 holds and suppose P is extremely imbalanced. Then, for any δ > 0, with probability at least 1− δ over S, the following generalization bound holds for all f ∈ F:
Rr0/1(f) ≤ Rpa(f) ≤ (c− 1)Ru2(f) ≤ (c− 1)R̂ u2 S (f) + 2
√ 2ρc
√ Λ2r2
n + 3Bc √ log 2δ 2n . (18)
The full proof is in Appendix B.3.1. From this theorem, we can see that Au2 has a learning guarantee w.r.t. Lpa (or L 0/1 r ) which depends on O(c).
Then, we provide the learning guarantee of Au3 in the following theorem. Theorem 2 (Learning guarantee of Au3 for extremely imbalanced distribution (worst case)). Assume the loss Lφ = Lu3 , where Lu3 is defined in Eq.(9). Besides, Assumption 1 holds and suppose P is extremely imbalanced. Then, for any δ > 0, with probability at least 1 − δ over S, the following generalization bound holds for all f ∈ F:
Rr0/1(f) ≤ Rpa(f) ≤ Ru3(f) ≤ R̂ u3 S (f) + 4
√ 2ρ
√ cΛ2r2
n + 6B √ log 2δ 2n . (19)
The full proof is in Appendix B.3.2. From this theorem, remarkably, we can see that Au3 has a learning guarantee w.r.t. Lpa (or L 0/1 r ) which depends on O( √ c), which enjoys the same order as the algorithm Apa [13]. Moreover, we find that the learning guarantee of Au4 w.r.t. Lpa (or L0/1r ) depends on O(c) (See Appendix B.3.3).
9Note that, instead of directly bounding the 0/1 risk, we can treat our results as the upper bounds of the pairwise risk, allowing it greater than 1.

heading: 4.1.2 The balanced distribution (best case)
text: 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 ofAuk , k = 1, 2, 3, 4 for balanced distribution (best case); full proof in Appendix B.4.1). Assume the loss Lφ = 2Lu1 = c2Lu2 = Lu3 = Lu4 , where they are defined in Section 3.1. Besides, Assumption 1 holds and suppose P is balanced. Then, for any δ > 0, with probability at least 1− δ over S, the following generalization bound holds for all f ∈ F:
Rr0/1(f) ≤ Rpa(f) ≤ Ru3(f) = c
2 Ru2(f) ≤
c 2 R̂u2S (f) + 4
√ 2ρ
√ Λ2r2
n + 6B √ log 2δ 2n , (20)
where 2R̂u1S (f) = c 2 R̂ u2 S (f) = R̂ u3 S (f) = R̂ u4 S (f).
From Theorem 3, we can observe that the model complexity term in this bound has no dependence on c. Notably, the same learning guarantee for these learning algorithms also confirms the validity of our analyses and the tightness of these bounds. Moreover, Apa also has an error bound independent of c for balanced distribution (see Appendix B.4.2).

heading: 4.1.3 Comparison
text: For generalization analyses, a tighter upper bound usually suggests probably better performance [12]10. In this paper, all algorithms are 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.
We now compare the algorithms considering the cases with (approximately) imbalanced distributions.
• Apa vs Au2 . Apa usually has a tighter bound than Au2 . In particular, given the same hypothesis space, it is usually easier to train R̂paS than other univariate losses, making R̂ pa S
smaller than others including R̂u2S . 11 Besides, for the model complexity terms (i.e. the last
two terms), Apa has an error bound of O( √ c) while Au2 depends on O(c).
• Au3 vs Au2 . Similarly, we argue that Au3 usually has a tighter bound than Au2 . For the first risk term, (c− 1)R̂u2S is usually comparable or even larger than R̂ u3 S .
12 For the model complexity term, Au3 has an error bound of O( √ c) while Au2 depends on O(c).
Overall, the tighter bound of Apa (and Au3 ) than Au2 indicates that Apa (and Au3 ) would probably perform better than Au2 , especially for a 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, Au2 and Au3 share the same learning guarantee. Thus, in approximately balanced cases, Au2 perform probably similarly to Au3 . 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 we set cmin = min{cp, c− cp} for the clarity of following discussions. cminc directly reflects the imbalance level of the distribution.
10When comparing bounds, it is usually more reasonable to compare the order of dependent variables rather than comparing the absolute values.
11Although we can not formally express the claim, we empirically observed it in experiments. 12In some cases, the first risk term may be bigger than 1 but we can still take insights from the error bound
through the dependent variables of the model complexity.
Note that the extremely imbalanced case (cp = 1 or cp = c − 1) and the balanced one (cp = c/2) are included. According to these results, we can observe that Apa has an error bound of O( √ c
cmin )
that is the same as Au3 , while Au2 depends on O( ccmin ). Therefore, in an imbalanced case (not necessarily the extremely imbalanced ones), Apa and Au2 usually have better bounds than Au3 , which probably indicates their better performance over Au3 in practice. Besides, when c 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 is not the focus of this paper, our theoretical results indeed indicate that the univariate loss Lu3 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.

heading: 4.2 Consistency Analyses
text: Following [9, 8], we consider the general partial ranking loss as follows: L0/1gpr(f(x),y) = αy ∑
(p,q)∈S+y ×S−y
[ [[fp(x) < fq(x)]] + 1
2 [[fp(x) = fq(x)]]
] , (21)
where αy is a positive penalty. Note that the losses in Eq. (2) is a special case of Eq. (21) with αy =
1 |S+y ||S−y | respectively. The general ranking loss can be defined in a similar way as Eq. (21). For clarity and generality, we define the general reweighted univariate surrogate loss as follows:
Lu(f(x),y) = c∑ j=1 ([[yj = +1]]β + y + [[yj = −1]]β−y )`(yjfj(x)), (22)
where β+y and β − y are penalties for the positive and negative labels respectively. We assume β + y β − y > 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 BL(x, P (y|x)) denote the set of the Bayes predictors of a loss L given a sample x and a conditional distribution P (y|x). Remarkably, [8] provided a sufficient and necessary condition for determining whether a 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 3 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 1 in Appendix C for the results of the Hinge loss): Theorem 4 (Necessary condition for the consistency of Eq. (22) w.r.t. Eq. (21) with exponential, logistic or squared hinge loss). A general reweighted univariate surrogate loss in Eq. (22) with `(z) = e−z , `(z) = ln(1 + e−z) or `(z) = (max{0, 1− z})2 is consistent w.r.t. the general partial ranking loss in Eq. (21) only if ∃τ > 0, β+y β−y = τα2y for all y such that 1−c ≤ ∑ 1≤j≤c yj ≤ c−1.
For clarity, see full proof in Appendix C. When c ≤ 3, the penalties ofLu1 , Lu3 andLu4 may coincide with that of Lu2 up to a multiplicative constant. When c ≥ 4, it is straightforward to construct counter examples that violate the necessary condition in Theorem 4 and obtain the Corollary 1 as follows. Corollary 1 (Inconsistency of Lu1 , Lu3 and Lu4 w.r.t. Eq. (2) with exponential, logistic or squared hinge loss). If c ≥ 4, Lu1 , Lu3 and Lu4 with `(z) = e−z or `(z) = ln(1 + e−z) or `(z) = (max{0, 1− z})2 are inconsistent w.r.t. the partial ranking loss in Eq. (2).
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 Lu1 , Lu3 and Lu4 w.r.t. Eq. (2).
An immediate conclusion from Corollary 1 is that Lu1 , Lu3 and Lu4 are inconsistent w.r.t. the RL in Eq. (1) because B L 0/1 r (x, P (y|x)) ⊂ B L 0/1 pr (x, P (y|x)) [8].
Compared to existing work [9, 8], although Theorem 4 is negative, it considers surrogate losses in a more general reweighted form, i.e. Eq. (22), which may be of independent interest.

heading: 5 Related Work
text: Here we mainly review the theoretical work relevant to this paper in MLC and MLR.
Consistency. [8] 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 Lu2 . 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 decision-theoretic 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.13 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). [32] devoted to the study of consistent multi-label classifiers w.r.t. various measures under the EUM framework. [33] investigated the multi-label consistency of various reduction methods w.r.t. precision@k and recall@k measures.
Generalization analysis. [13] studied the generalization bounds of the algorithms based on Lpa and Lu1 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 [13] and [8], respectively.
We mention that a specific form of Eq. (9) with base hinge loss has been used as a part of prior work [34], which achieves excellent empirical results in MLC. In comparison, this paper considers a 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.

heading: 6 Experiments
text: As a 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 3 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, we utilize linear models with the base logistic loss for simplicity and fair comparison. Besides, we use the same efficient stochastic algorithm (i.e. SVRG-BB [35]) to solve these convex optimization problems. Moreover, we search the hyper-parameter λ for all algorithms from a wide range of {10−8, 10−7, · · · , 102} using 3-fold cross validation on each dataset.14
The experimental results are summarized in Table 3 (see Appendix E for complete results with standard deviations). First, we observe that Apa and Au3 outperform the others especially Au2 on almost all benchmarks. It verifies our generalization analyses: in extremely imbalanced distributions case, Apa and Au3 usually have tighter bound than others, especially Au2 , where benchmarks are usually highly imbalanced as shown in Appendix E (Fig. 2). Besides, such results do not contradict with the consistency results since two assumptions in consistency analyses are violated in 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 Au2 . To further study the effect of c, we evaluate Au2 and Au3 on highly imbalanced semi-synthetic datasets with randomly selected c based on the delicious dataset (See Fig. 3 in Appendix E for details).
13Note that, our generalization and consistency analyses are both under the EUM framework. 14Our code is available at https://github.com/GuoqiangWoodrowWu/MLR-theory.
We find that Au3 would probably perform better than Au2 with larger c, which also confirms our theoretical findings: in the extremely imbalanced case, Au3 has tighter bound than Au2 w.r.t. c. 15
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 E (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).

heading: 7 Conclusion and Discussion
text: This paper presents a systematic study from two complementary perspectives of consistency and generalization bounds of algorithms in multi-label ranking. Theoretically, we find that the instance-wise 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 O(c) while the ones with inconsistent pairwise losses depend on O( √ c) [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 O(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 our 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].

heading: Acknowledgements
text: This work was supported by NSFC Projects (Nos. 61620106010, 62061136001, 61621136008, U1811461, U19B2034, U19A2081), Beijing NSF Project (No. JQ19016), Tsinghua-Bosch 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.
15Notably, it is nontrivial to directly plot the complexity rate of c on semi-synthetic 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.

Review summaries:
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.  Overall I think the paper is clear and well executed.

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.

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.   The 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}$).   Since, 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.  Based 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.