Multi-Label Learning with Stronger Consistency Guarantees
Authors: Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2024 poster (2024)
Keywords: multi-label learning
consistency
surrogate loss
hamming loss
learning theory
Primary area: learning_theory

Abstract: We present a detailed study of surrogate losses and algorithms for multi-label learning, supported by $H$-consistency bounds. We first show that, for the simplest form of multi-label loss (the popular Hamming loss), the well-known consistent binary relevance surrogate suffers from a sub-optimal dependency on the number of labels in terms of $H$-consistency bounds, when using smooth losses such as logistic losses. Furthermore, this loss function fails to account for label correlations. To address these drawbacks, we introduce a novel surrogate loss, *multi-label logistic loss*,  that accounts for label correlations and benefits from label-independent $H$-consistency bounds. We then broaden our analysis to cover a more extensive family of multi-label losses, including all common ones and a new extension defined based on linear-fractional functions with respect to the confusion matrix. We also extend our multi-label logistic losses to more comprehensive multi-label comp-sum losses, adapting comp-sum losses from standard classification to the multi-label learning. We prove that this family of surrogate losses benefits from $H$-consistency bounds, and thus Bayes-consistency, across any general multi-label loss. Our work thus proposes a unified surrogate loss framework benefiting from strong consistency guarantees for any multi-label loss, significantly expanding upon previous work which only established Bayes-consistency and for specific loss functions. Additionally, we adapt constrained losses from standard classification to multi-label constrained losses in a similar way, which also benefit from $H$-consistency bounds and thus Bayes-consistency for any multi-label loss. We further describe efficient gradient computation algorithms for minimizing the multi-label logistic loss.

Multi-Label Learning with Stronger Consistency Guarantees
Anqi Mao Courant Institute New York, NY 10012 aqmao@cims.o .nn..n..ee. edu
Mehryar Mohri Google Research & CIMS New York, NY 10011 mohri@google.com
Yutao Zhong Courant Institute New York, NY 10012 yutaoucims nyu edu
Abstract
We present a detailed study of surrogate losses and algorithms for multi-label learning, supported by H-consistency bounds. We first show that, for the simplest form of multi-label loss (the popular Hamming loss), the well-known consistent binary relevance surrogate suffers from sub-optimal dependency on the number of labels in terms of "CC-consistency bounds, when using smooth losses such as logistic losses. Furthermore, this loss function fails to account for label correlations. To address these drawbacks, we introduce novel surrogate loss, multi-label logistic loss, that accounts for label correlations and benefits from label- indepeedednn J-C consistency bounds. We then broaden our analysis to cover a more extensive family of multi-label losses, including common ones and a new extension defined based on linear-fractional functions with respect to the confusion matrix. We also extend our multi-label logistic losses to more comprehensive multi-label comp-sum losses, adapting comp-sum losses from standard classification to the multi-label learning. We prove that this family of surrogate losses benefits from H-consistency bounds, and thus Bayes-consistency, across any general multi-label loss. Our work thus proposes unified surrogate loss framework benefiting from strong consistency guarantees for any multi-label loss, significantly expanding upon previous work which only established cayess-oonsisency and for specific loss functions. Additionally, adapt constrained losses from standard classification to multi-label constrained losses in a similar way, which also benefit from H(- consistency bounds and thus Bayes-consistency for any multi-label loss. We further describe efficient gradient computation algorithms for minimizing the multi-label logistic loss.
Introduction
Supervised learning methods often assign a single label each instance. However, real-world data exhibits more complex structure, with objects belonging to multiple categories simultaneously. Consider video about sports training, which could be categorized as both 'health' and 'athletics," or culinary blog post tagged with 'cooking' and 'nutrition'. As result, multi-label learning [McCallum, 1999, Schapire and Singer, 2000] has become increasingly important, leading to the development of various interesting and effective approaches, predominantly experimental in nature, in recent years [Elisseeff and Weston, 2001, Deng et al., 2011, Petterson and Cactano, 2011, Kapoor et al., 2012].
Although there is a rich literature on multi-label learning (see [Zhang and Zhou, 2013] and [Bo- gatinovski et al., 2022] for detailed surveys), only few studies focus on the theoretical analysis of mubti-label learning, particularly the study of the Bayes-consistency of surrogate losses [Zhang, 2004a.b, Bartlett et al., 2006, Tewari and Bartlett, 2007, Steinwart, 2007].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Gao and Zhou [2011] I] initiated the study of Bayes-come coneissenss in multi-label learning with respect to Hamming loss and (partial) ranking loss. They provided negative results for ranking loss, demonstrat- ing that no convex and differentiable pairwise surrogate loss is Bayes-consistent for that multi-label loss. They also showed that the hinary relevance method, which learns an independent binary classifier for each of the 7 labels, is Bayes-consistent with respect to the Hamming loss. Dembezynski et al. [2011] further demonstrated that under the assumption of conditionally independent labels, the binary relevance method is also Bayes-consistent with respect to the F&8 measure loss. However, they noted that it can perform arbitrarily poorly when this assumption does not hold. Dembezynski et al. [2012] provided positive result for the (partial) ranking loss by showing that the simpler univariate variants of smooth surrogate losses are coyyss-onnsstent with respect to it. Additionally, Zhang et al. [2020] proposed family of Bayes- consistenn surrogate losses for the F3 measure by reducing the Fg learning problem to a set of binary class probability estimation problems. This approach was motivated by the consistent output coding scheme in [Ramaswamy al., 2014] for general multiclass problems. Other works have studied generalization bounds in multi-label learning [Yu et al., 2014, Wydmuch al., 2018, Wu and Zhu, 2020, Wu et al., 2021, 2023, Busa-Fekete et al., 2022].
Another related topic is the characterization of the Bayes classifier and corresponding Bayes-consistent plug-in algorithm in multi-label learning. This includes the characterization of the Bayes classifier for subset 0/1 loss and Hamming loss in [Cheng et al., 2010] and the characterization of the Bayes classifier for F1 measure in [Dembezynski et al., 201 1]. Dembczynski et al. [2013], Waegeman et al. [2014] further extended the results in [Dembezynkki et al., 2011] by designing a cayess-cnssistnt plug-in algorithm for the F3s measure. Koyejo et al. [2015] characterized the Bayes classifier for general linear fractional losses with respect to the confusion matrix and designed the corresponding plug-in algorithms in the empirical utility maximization (EUM) framework. In this framework, the measures are directly defined as functions of the population, in contrast to a loss function that is defined as a function over single instance in the decision theoretic analysis (DTA) framework [Ye et al., 2012]. Menon et al. [2019] studied the Bayes-consistency of various reduction methods with respect Precision @ i and Recall @ x in multi-label learning. However, all these publications only established
for specific loss functions. Can we derive unified surrogate loss framework that is consstcon for any multi-label loss?
Furthermore, as Awasthi, Mao, Mohri, and Zhong [2022a,b] pointed out, Bayes-consistency is an asymptotic guarantee and does not provide convergence guarantees. It also applies only the family of all measurable functions unlike the restricted hypothesis sets typically used in practice. Instead, they proposed stronger guarantee known H-consistency bounds, which are both non-asymptotic and account for the hypothesis set while implying Bayes-consistency. These guarantees provide upper bounds on the target estimation error in terms of the surrogate estimation error. Can we leverage this state-of-the-an consistency guarantee when designing surrogate loss functions for multi-label learnin??
Moreover, one of the main concerns in muultillbbl learning is label correlations (see [Debbzyúíski et al., 2012]). For the simplest form of multi-label loss, the popular Hamming loss, the existing Bayes-consistent binary relevance surrogate fails to account for label correlations. Can we design consistent loss functions that effectively account for label correlations well?
Our Contributions.
This paper directly addresses these key questions in multi-label learning. We present detailed study of surrogate losses and algorithms for multi-label learning, supported by H-consistency bounds.
In Section 3, we first show that for the simplest form of multi-label loss, the popular Hamming loss, the well-known consistent binary relevance surrogate, when using smooth losses such as logistic losses, suffers from sub-optimal dependency on the number of labels in terms of H-coonsitency bounds. Furthermore, this loss function fails to account for label correlations.
To address these drawbacks, we introduce a novel surrogate loss, multi-label logistic loss, that accounts for label correlations and benefits from label-independent H-consistency bounds (Section 4). We then broaden our analysis to cover a more extensive family of multi-label losses, including all common ones and new extension defined based on fnaat-fractional functions with respect the confusion matrix (Section 5).
In Section 6, we also extend our multi- logistic losses to more comprehensive multi-labe comp-sum losses, adapting comp-sum sum losses from standard classification to the multi-labe learning.
2

---

We prove that this family of surrogate losses benefits from H-consistency bounds, and thus Bayes- consistency, across any general multi- label loss. Our work thus proposes unified surrogate loss framework that is Bayes-consistent for any multi-label loss, significantly expanding upon previous work which only established consistency for specific loss functions.
Additionally, we adapt constrained losses from standard classification to multi-label constrained losses in a similar way, which also benefit from H--consistncyy bounds and thus Bayes-consistency for any multi-label loss (Section 7). We further describe efficient gradient computation algorithms for minimizing the multi-label logistic loss (Section 8).
2 Preliminaries
Multi-label learning. We consider the standard multi-label learning setting. Let X be the input space and y = [+1, the set of all possible labels or tags, where I is a finite number. For example, X can be a set of images, and can be a of I pre-given tags (such 'flowers', 'shoes', or "books") that can be associated with each image in the image tagging problem. Let n = 19]- For any instance x X E y, if y +1, we say that label is relevant æ. Otherwise, it is not relevant. Let [4]= (I.....(} ..y. Given a sample S drawn i..d. according to some distribution D) over X x y, the goal of multi-label learning is learn hypothesis h: x [4] R to minimize the generalization error defined by multi-label loss function L:H(nn x X x y + R.
and its associated label y (y1,-.... UU.--.-:91 .n)
(h)
[ 2L)),,
E
(1)
(a.,)~>
where Hall is the family of all measurable hypotheses. For convenience, we abusively denote the scoring vector by h(x)= = (h(z, (((,,))),.,,,((I Given a hypothesis set H( = Hall. we denote by ([) = best R()) the best-in-class error. We refer to the difference (h) - R[ (H) as the estimation error, which is termed the excess error when H. = Hanl Let sign: I +> 1 1so be the sign function, and let x: TR, be a threshold function. The target loss function L Lan be typically given by a function [ mapping from y x y to real numbers:
L(h, x. 2) [(h(x).)),
where h(x)) == (x), e e is the prediction for the input x e X and hx(x)) sign(h(x; i)) for any E [t]. There are many multi-label loss functions, such as Hamming loss, (partial) ranking loss, Fl and the more general F' measure loss, subset 0/1 loss, precision @ K. recall k. etc. [Zhang and Zhou, 2013]. Among these, several loss functions are defined based on the prediction of the hypothesis h(x), while others are based on the scoring vector h(x). We will specifically consider the first type of multi-label loss in the form given in (2), which is based on some 'distance" between the prediction and the true label. This includes all the loss functions previously mentioned (see Section for list of several common multi-label losses in this family) but excludes the (partial) ranking loss, which is defined based on pairwise scores. For convenience, we may alternatively refer to L or its induced L as the multi-label loss. Without loss of generality, we assume that L E [O, 1]. which can be achieved through normalization. We also denote by Lmax = maxy' by [(V/,)) Our analysis is general and adapts to any multi-label loss L. Note that adhere to the decision -heeoretcc analysis (DTA) framework, in which a loss function is defined over a single instance, and the measure is the expected loss, also known as the generalization error (the expectation of the loss function over samples). Another popular framework is empirical utility maximization (EUM), where measures are defined directly as functions of the population, that is, as function of the expectation over samples.
Surrogate risk minimization and consistency. Minimizing the multi-label loss L directly is com- putationally hard for most hypothesis sets because it is discrete and non-convex. A common method involves minimizing smooth surrogate loss function [:H.u x X x y + R. which is the main focus of this paper. Minimizing a surrogate loss directly leads to an algorithm for multi-label learning. A desirable guarantee for the surrogate loss in multi-label learning is fayes-ccossitenne [Zhang, b004a,b, Bartlett et al., 2006, Tewari and Bartlett, 2007, Steinwart, 2007, Gao and Zhou, 2011]. That is, minimizing the surrogate loss over the family of all measurable functions leads to the minimization of the multi-label loss over the same family:
Definition 2.1. surrogate loss [ is said to be Bayes-consistent with respect to multi-label loss L if the following holds for any distribution and all given sequences of hypotheses (1m) neN C Han:
lim Ry (hm)) RE (Hau) =0)
lim R (hw)) RR (H = 0).
(3)
3

---

As pointed out by Awasthi, Mao, Mohri, and Zhong [2022a,b] (see also [Long and Servedio, 2013, Zhang and Agarwal, 2020, Awasthi et al., 2021a,b, Mao et al., 2023d.c,a.b,e, Awasthi al., 2023, 2024, Mao et al., 2024a,b,c,h, h.g.f....g......f,,, Mohri et al., 2024, Cortes et al., 2024]), Bayes-consistency an asymptotic guarantee that cannot provide any guarantee for approximate minimizers; also applies only to the family of all measurable functions and does not consider the hypothesis sets typically used in practice. Instead, they propose a stronger guarantee known as JC-consistency bounds, which are both non-asymptotic and dependent on the hypothesis set, and imply Bayes-consistency when H Hall- These guarantees provide upper bounds on the target estimation error in terms of the surrogate estimation error. In the multi-label learning scenario, they can be formulated as follows:
Definition 2.2. A surrogate loss [ is said to admit an H-consistency bound with respect to multi- label loss L if the following condition holds for any distribution and for all hypotheses h e HC given a concave function T:R. R. with [(0) 0:
R (h) - RD (30) + Mr (H) -(()))))))) ()))))
The quantities MHH appearing in the bounds are called minimizability gaps, which measure the difference between the best-in-class error and the expected best pointwise error for a loss function and a hypothesis set H(:
- inf E [( v. (0....1))) 20. heeC
(5)
vlu
These are inherent quantities depending on the distribution and hypothesis set, which we cannot hope to minimize. Since I is concave and r(0) = O, I is sub-additive and an H-consistencc bound (4) implics that: Ry (h) Rt (H) + (3() $ (1) (T() + ()M(())).. Therefore, when the surrogate estimation error (R) (90) is minimized to 6, the target estimation error (R) - Re when HC = Hall or in more general realizable cases, such as when (3() = (RGa)) [Steinwart, 2007, Awasthi, Mao, Mohri, and Zhong, 2022b, Mao, Mohri, and Zhong, 2023r]. In these cases, JC-consistency bounds imply the H-consissency of surrogate loss L with respect to multi-label loss RR RR (3() s [e)) for any The minimizabilityy gap M)( is upper bounded by the approximate error AT()) R)() Eg inffeernn [Bylz[[(h, x,, v) []] and is generally a finer quantity [Mao et al., 2023f]. Thus, H--consistency bounds are more informative, more favorable, and stronger than excess error bounds, and they imply these bounds when H Hanl
(J()) is upper bounded by I(e)+ ((M)))))))))). The minimizability gaps vanish
L: ((())-R((()) Se
Next, we will study surrogate loss functions and algorithms for multi-label learning, supported by H-consistency bounds, the state-of-the-art consistency guarantee for surrogate risk minimization.
3 Existing consistent surrogates for the Hamming loss
In the section, we consider the simplest form of multi-label loss, the Hamming loss, defined as:
(h, v. y) e Hx XxxYx. Laam (h, x. y) L (h(x).)) where Inam (1/ Σ 1u E1
(6)
The existing Bayes-consistent surrogate loss function is to transform the multi-label learning into I independent binary classification tasks [Gao and Zhou, 201 I], defined as for all (h, y) H x X
Σ (v.h(a,))) 1=1
where IR. - RR, is binary margin-based loss function, such as the logistic loss u log(1 1 e e"). The algorithm that minimizes this surrogate loss is known as binary relevance [Zhang and Zhou, 2013], which learns an independent binary classifier for each the / labels. Gao and Zhou [2011, 1, Theorem 15] shows that Lnr is Bayes-consistent with respect to Lham if + is Bayes-consistent with respect to fo-1: (f, v) + ((s)) the binary zero-one loss. Here, we prove a stronger result that Lor admits an H-consistency bound with respect to Lham with a functional form IT(;) if Φ admits an H-consistency bounds with respect to 60-1 with a functional form T(.). Let be hypothesis set consisting of functions mapping from X to R.

---

Theorem 3.1. Let = F". Assume that the following F-consistency bound holds in the binary classification. for some concave function T:R R.: VSEJ, Rio if) Rio. ( (3) Mi. (3) ((Ro R2 + Ma (3)). Then, the following H-consistency bound holds in the multi-label learning: for all h H,
(8)
RR (h) R (H) Mr, (H()
Rhaam (h) Ri Jam (FC) Minan (3C) $ IT
Lbe
(9)
1
The proof is included in Appendix A. We say that a hypothesis set JJ is complete if [(z): for all X. This notion of completeness broadly applicable and holds for commonly used hypothesis sets in practice, including linear hypotheses, multi-layer feed-forward neural networks, and all measurable functions. For such complete hypothesis sets F and with smooth functions & like the logistic loss function, I' admits square root dependency in the binary classification [Awasthi al., 2022a, Mao et al., 2024h]. Thus, by Theorem 3.1, we obtain the following result.
Corollary 3.2. Let H Le = F., Assume that I is complete and (u) log(1 ()). Then, the following H-consistency bound holds in the multi-label learning: for all H,
Ri (h) - Riaam (H) + Ma (H) s ( RT,, (h) Ri (H) MI, (H))² MI,(()))
(i)-RR(nn
(10)
Since t + t is sub-additive, the right-hand side of the H-consistency bound in Corollary 3.2 can be further upper bounded by 1 (Rr.,, (h) Ri (30)² 1 (Mr,, (H)) This implies that when the estimation error of the surrogate loss Lbr reduced to e, the corresponding estimation error of the Hamming loss upper bounded by l + (Mr,,, (H)) $ ML (H). the nearly realizable cases where minimizability gaps are negligible, this upper bound approximates
Ri (h) Ri (3() < 1
(11)
Therefore, as the number of labels / increases, the bound becomes less favorable. Furthermore, the loss function Lbr clearly fails to account for the inherent correlations among labels. For instance, 'coffee' and "mug' are more likely to co-occur than 'coffee' and 'umbrella'. Additionally, Lbr is only Bayes-consistent with respect to the Hamming loss and cannot yield risk-minimizing predictions for other multi-label losses such as subset 0/1 loss or Fa-measure loss [Dembczyáski et al., 2012]. To address these drawbacks, we will introduce a new surrogate loss in the next section.
4 Multi-label logistic loss
In this section, we define new surrogate loss for Hamming loss in multi-label learning that accounts for label correlations and benefits from aatel-independent HH-consistnncy bounds. This loss function can be viewed as generalization of the (multinomial) logistic loss [Verhulst, 1838, 1845, Berkson, 1944, 1951]. used in standard classification, to multi-label learning. Thus, we will refer to it as multi-label logistic loss. It is defined as follows: for all (h,2,1) v) K X y,
Log (h, x. y)
E1 [1--nnm/// log Σ (z)(),))) Eeey
(12)
y'ey
This formulation can be interpreted as a weighted logistic loss, where (1 - Liam (-1)) serves as
weight vector. Additionally, the term Σi_, (v/² v\) h h(x, represents the difference in the scores between the label y' and any other label y", where these scores account for the correlations among the labels y, within the logarithmic function.
The next result shows that the multi-label logistic loss benefits from a favorable H-consistency bound with respect to Lham. without dependency on the number of labels 1. We assume that H = F and F is complete, conditions that typically hold in practice.
Theorem 4.1. Let H. F¹. Assume that F is complete. Then, the following K-consistency bound holds in the mulli-label learning: for all h E H,
Riya (h) Rinm (II) Me (3() s 2 R(R (h) R2 (3C) + Mr,, (30)
(13)
5

---

Since t + tà is sub-additive, the right- hand side of the H-coonsitennyy bound in Theorem 4.1 can be further upper bounded by RT (h) - R Tio (30)² + 2 MMM (90) & This implies that when the estimation error of the surrogate loss Llog is reduced up to the corresponding estimation enror of the Hamming loss is upper bounded by 2e 2MMG, (30) - ML (10). In the nearly realizable cases where minimizability gaps are negligible, this upper bound approximates to
Ri (h) Riam (H) s 2
(14)
Therefore, the bound is independent of the number of labels I. This contrasts with the bound for Lb shown in (11), where lapen-dep factor (t replaces the constant factor 2, making it significantly less favorable.
The proof of Theorem 4.1 is included in Appendix B.2. We first present general tool (Theorem B.1) in Appendix B. which shows that derive H--consistency bounds in multi-label learning with concave function I, it is only necessary to upper bound the conditional regret of the target multi-label loss by that of the surrogate loss with the same r. This generalizes [Awasthi, Mao, Mohri, and Zhong, 2022b, Theorem 2] in standard multi-class classification to multi-label learning, Next, we characterize the conditional regret of the target multi-labe, loss, such Hamming loss, Lemma B.2 found in Appendix B. under the given assumption. By using Lemma B.2, we upper bound the conditional regret of Lham by that of the surrogate loss Llog with a concave function ((t) = 2vt.
When K Hanl minimizability gaps Minnng (H)) and Mi (H) vanish, Theorem 4.1 implies excess error bound and consstecns of multi-label logistic loss with respect to the Hamming loss. Corollary 4.2. The following excess error bound holds in the multi-labe learning: for all h e Hall.
Ra (h) - Riham (Hall) $ 2 (1i) - R2 Riox (Han))
(15)
Moreover, Llog is Bayes--onsistent with respect to Lham-
Approaches like binary relevance surrogate loss treat each label independently. This overlooks crucial inherent information encoded the relationships between labels. Our new form of surrogate losses explicitly captures these label correlations. Both the binary relevance surrogate loss and our new surrogate loss are Bayes-consistent, meaning that minimizing them over the family of measurable functions approximates the Bayes-optimal solution. However, our correlation-awes surrogate losses can converge faster, which is reflected in their more favorable H-consistency bounds, independent of the number of labels.
is known that Lbr is only Bayes-consisenn with respect to the Hamming loss and Precision @ x. and can be arbitrarily bad for other multi-label losses such as -a-mesuure loss [Dembezynski et al., 2011]. Instead, we will show in the next section that our surrogate loss Llog adapts to and is Bayes-consistent with respect to an extensive family of multi-label losses, including the F3 measure loss.
Extension: general multi-label losses
In this section, we broaden our analysis to cover a more extensive family of multi-label losses, including all common ones and new extension defined based on incar-fractional functions with respect to the confusion matrix. Note that several loss functions are defined over the space 10,1)', rather than (+1,-1}'- To accommodate this difference, any pair y, y/ ε y (+1,-1)² can be projected onto {0, 1)¹ by letting y = y+1 and y' = 2
v++1 where 1 E IR! is the vector with all elements equal to 1. Several common multi-label losses are defined as follows.
Hamming loss: [(y'.v) = Ei_1 1um
Fa-mua loss: [(y'.v) .v)
(1+32)8'
Subset 0/1 loss: [(y' .y) maxx4e[]] 1
Jaccard distance: [(y',)) .)) = 1 ....v
7/

---

Precision@x: [(y')) =1 1 Ex)( 17,=1 subject to of e yx. where Vr = {y y: | x) and T(7') = fic [1]:7, 1].
Recall@k: [(y' .) = 1-
1 I EETOY 1z.11 subject to s e Ux. where yx = {y é y:
M k}
and
J(T') - {i [1] = 1}.
More generally, we can define multi-label loss based on true positives (TP), true negatives (TN), false positives (FP) and false negatives (FN), which can be written explicitly as follows:
TP
y y
TN
V T
y
FP
|1
11 D V. FN 11 1
17 17
Similar [Koyejo et al., 2014, 2015], we now define a general family of multi-label losses as linear-fractional functions in terms of these four quantities:
ag + (1 TP + FP + dol FN + 600 TN
[(y' 3)
(16)
by b1 TP + FP buz FN buo TN
can be shown that the aforementioned Hamming loss, Fa-mmasure loss, Jaccard distance, precision and recall all belong to this family. Note that the previous definitions in [Koyejo et al., 2014, 2015] are within the empirical utility maximization (EUM) framework [Ye et al., 2012], where the measures directly defined as functions of the population. We generalize their definition the decision theoretic analysis (DTA) framework, in terms of loss functions defined over and y/.
Moreover, can consider extending multi-label losses (16) non non-linear fractional functions of these four quantities, or more generally, to any other forms, as long as they are defined over the space x y.
Another important family of multi-label losses is the tree distance loss, used in cases of hierarchical classes. In many practical applications, the class labels exist within predefined hierarchy. For example, in the image tagging problem, class labels might include broad categories such as 'animals' or 'vehicles', which further subdivide into more specific classes like 'mammals' and 'birds' for animals, or 'cars' and 'trucks' for vehicles. Each of these subcategories can be divided even further, showcasing a clear hierarchical structure.
Tree distance:
Let (y, E, W) be tree over the label space y, with edge set E and positive. finite edge lengths specified by W. Suppose r e designated as the root node. Then, (r the shortest path length in T between y and y/
Despite the widespread use of hierarchical classes in practice, our knowledge, Bayes-consistent surrogate has been proposed for the tree distance loss in multi-label learning. Next, we will show that our multi-label logistic loss accommodate all these different loss functions, including the tree distance loss. For any general multi-label loss L, we define the multi-label logistic loss as follows:
(1-((1'' log Σ Einn -() (17) VyEy
(h,,,, JC Xx Liog xh,
y/E
Here, [ can be chosen all the multi-label losses mentioned above. Next, we will show that Loo benefits from H-coosistency bounds and Bayes consistency with respect to any of these loss functions.
Theorem 5.1. Let H. = Fr. Assume that F is complete. Then, the following K-consistency bound holds the multi-label learning:
R Vh E H. RL))) - R[ (90) s 2 (RR... -R) (3C) + My... (30)
(18)
The proof of Theorem 5.1 is basically the same as that of Theorem 4.1, modulo replacing the Hamming loss Lham with a general multi-label loss L. We include it in Appendix B.3 for completeness. When H Hall minimizability gaps Mr (H) and (H) vanish, Theorem 4. implies excess error bound and Cancs-con of multi-label logistic loss with respect to any multi-label loss.
Corollary 5.2. The following excess error bound holds in the multi-labe label learning: for all h Han-
Ry (h) (Hau) RT.... (h) Ri (Hau))
(19)
Moreover. Loog is Bayes-consistent with respect to L.
7

---

Corollary 5.2 is remarkable, as it demonstrates that a unified surrogate loss, Loog, is mayes-consistent for any multi-label loss, significantly expanding upon previous work which only established con- sistency for specific loss functions. Furthermore, Theorem 5.1 provides a stronger guarantee than Bayes-consistency, which both non-asymptotic and specific to the hypothesis set used.
Minimizing the multi-label logistic loss directly leads to the effective algorithm in multi-label learning. We further discuss the efficiency and practicality of this algorithm in Section 8, where we describe efficient gradient computation.
Extension: multi-label comp-sum losses
In this section, we further extend our multi-label logistic losses to more comprehensive multi- label comp-sum losses, adapting comp-sum losses [Mao, Mohri, and Zhong, 20231] from standard classification to the multi-label learning. As shown by Mao, Mohri, and Zhong [2023f], comp-sum loss is defined via a composition of the function and a sum, and includes the logistic loss (V( log(u)) [ [Verhulst, 1838, 1845, Berkson, 1944, 1951], the exponennnlt loss (V(
1)
[Weston and Watkins, 1998, Awasthi et al., 2022b], the generalized cross-entropy loss (V(u))
-1- ) E (0, 1)) [Zhang and Sabuncu, 2018], 8), and the mean absolute error loss (V(u) [Ghosh et al., 2017] as special cases.
Given any multi-label loss L, we will define our novel multi-label comp-sum losses as follows:
Σ c ) (20) vyeyy
V(h, v. E E x X y, Loomp (h, (h, x, = (1-I(1''W)
grey
This formulation can be interpreted as weighted comp-sum loss, where (1-[(- serves as weight vector. Additionally, this formulation accounts for label correlations among the y;s within the function Next, we prove that this family of surrogate losses benefits from H--consistnncy bounds, and thus Bayes-consisteng
across any general multi-label loss.
Theorem 6.1. Let H = F', Assume that I is complete. Then, the following K-consistenccy bound holds in the multi-label learning:
vh e H.
(h) (H+) -M((() s ST(R [com (1) R.oopp (H) M (H6):
(21)
where T(t)= 2/7 when Te (n) log(u) or a-ru-11 1; [(t) nt when T (u) 1 g (1 1 w).9 (0. and [tt) nt when V (u) = 1.
Corollary 6.2. The following excess error bound holds in the multi-label learning:
vh E Halls RL) - Ri (Hau) S I (R (h)
R (Hat));
(22)
Loomp
where r'(t= 2/6 when ((()) (u) or 1; l'tt 2/ when (u) }/( ) (0, 1); and l'(t)= nut when ((u) with respect to L.
Moreover: Loomp with these choices of V are Bayes-consistent
The proof of Theorem 6.1 is included in Appendix B.4. Similar to the proof of Theorem 5.1, we make use of Theorem B.1 and Lemma B.2 in Appendix B. However, upper bounding the conditional regret of L by that of the surrogate loss Lcomp for different choices of W/ requires a distinct analysis depending on the specific form of the function V, leading to various concave functions I' Our proof is inspired by the proof of FC-consistency bounds for comp-sum losses in [Mao et al., 2023f] through the introduction of a parameter μ and optimization. However, the novelty lies in the adaptation of μ with quantity s tailored to multi-label loss functions instead of the score vector h itself.
Note that, with (()) log(u) shown in Section 5, for (u)) independent of the number of labels and are favorable. However, for other choices of V, the bounds exhibit worse dependency n, which can be exponential with respect to l.
1, the bounds are also
7 Extension: multi-label constrained losses
In this section, we introduce another novel family of surrogate losses, adapting constrained losses [Lee et al., 2004, Awasthi et al., 2022b] from standard classification to multi-label constrained losses
8

---

in similar way. Given any general multi-labed loss L, we define multi-label label constrained losses as:
L( (- Euub(a.))
v(h,2, e xxxXxx y, (hstn((h, 2,, Σ 3/
(23)
where Evey Ei=1 Mih(a, = O. Next, we show that Lestnd also benefit from H-consistency bounds and thus Bayes-consistency for any multi-label loss.
Theorem 7.1. Let H = Assume that F is complete Then, the following H-consistency bound holds the multi-label learning:
Wh K., R R() (X)) (3) S T [oonn (1) (6)-R1. R Lostad (H) Mi (H)):
(24)
where r(t) 2 Lmaxt when ( () e= ; r(t) 2 when (u)) ) max (0, 1 u}², and r(t) = when 40 (()) max u} (uu)= min m [a, 1/1p
u/p). 1}. p> 0.
Corollary 7.2. The following excess error bound holds in the multi-label learning:
Vh Hal, R1 (h) (H(in) 3
ST(RT Re (h) R
(Han))
(25)
Lestnd
where T(t) m when (w)) = ; [(t) 2/ when ((u) max u}²; and r(t) when ((u) max 10-1-ul u} or @(u) min(max'( (0, u/p). 1}, ) Moreover Lestnd with
these choices of 4 are Bayes-consistent with respect to L.
The proof of Theorem 7.1 is included in Appendix B.5. As with the proof of Theorem 6.1, we use Theorem B.I and Lemma B.2 from Appendix B. and aim to upper bound the conditional regret of L by that of the surrogate losses Eeomp using various concave functions r. However, the difference lies in our introduction and optimization of a parameter tailored to a quantity z that is specific to the form of the multi-label constrained loss.
These results show that cases where minimizability gaps vanish, reducing the estimation error of Leatnd to e results in the estimation error of target multi-label loss L being upper bounded by either VE or e, modulo a constant that is independent of the number of labels.
8 Efficient Gradient Computation
In this section, we demonstrate the efficient computation of the gradient for the multi-label logistic loss Llog at any point (x', ".)))). This loss function is therefore both theoretically grounded in H- consistency bounds and computationally efficient. Consider the labeled pair (x² x²) and hypothesis h in J.. The expression for Liog (h, .y') can be reformulated as follows:
Llog (h,
(0.2.1' ,v')= = Σ (1-I('' log
E'' E (1l-- Σ yeey
yey
Σ (1 1 [iv' ( v/h(12 + (1-(((' x²)) log y'ey
El (ihee,) Σ Dey
yeey
also be invariant with respect to j and is fixed constant for many loss functions such as the Hamming loss.
Let Li) Eyey L(y, y² )) which is independent of h and can be pre-computed.
For many commonly used loss functions, the terms involving sums over all possible label combina- tions can be simplified analytically. To illustrate this, we provide explicit formulae for the Hamming loss and F3 measure loss functions:
Hamming loss: Eyey( (1 [ham (v.8)) -(1- 1)2¹ Eyey [[ ( (y,))) -(1 1)2 Eyey Elm !.==! = (1 - 1)2' + Σlm Eyey yA-h = -1 - 1)2' + 21-1 1- 12-
F9 measure: Eyey LFs (y, )) = Eyey 31 I = Σk Eyecr
(1+,8² yo''
(1+8-)
34
(1+89) (( Σl (1+7))
Σk-o
where G = {y E y: 1yll = k).
g2k+l7'11
3-k+1711

---

A similar analysis applies to many other loss functions, thus, these terms do not affect the tractability of our algorithms. Next, we will consider the hypothesis set of linear functions H {a + w (a, i): w R.). where v is feature mapping from X x [4] to R Using the shorthand w for h, we can rewrite Liog at (x), y²) as follows:
E [wV ( ( (ine w)
Nlog(w,x)) ,1,,, -w
Li)))
(26)
Keey
where Zw.j= = Eyey ew M4 (i ()), Then, we can compute the gradient of Liog at any w Rd:
w.
M. Me .0)
v[log(w)= = (1-1 Σ of (x' 1) + +i) Σ
Σ
y (x,, i)
Zwri
DEM
{ 111
(1--[(V''') y'Ey
Σ ( + +1)(i)
E go
(27)
where qw is distribution over y with probability mass function qw(y) rearranging the terms in (27), we obtain the following result. Lemma 8.1. The gradient of Liog at any w E R2 can be expressed as follows:
By
Zuii
v[log(w) Σ (2),)))2211)) L1()) Σ ()
(28)
mm1
where L2(i.) Evey (1-[(y, yy,, Li(i) Eyay (1-((y, Qw(i) Evey qw (y)y (w( xe (2) (, .)) and Zw.j = Egey ew (()()) ,)), The overall time complexity for Zwe
gradient computation is O(1).
Here, the evaluation of ()) E [(] and Li) can be computed once and for all, before any gradient computation. For evaluation of (i), note that it can be equivalently written as follows:
w. (w. .v)
(w)
(i)= = Σ
yEy Eyey e (w5. Ui, with (x", y) Σ EV 1-1
(29)
where (<r,, y) admits Markovian property of order 1 [Manning and Schutze, 1999, Cortes et al., 2016]. Thus, as shown by Cortes et al. [2016, 2018], Qw (i) can be evaluated efficiently by running two single-soure
shortest-distance algorithms over the (+, x) semiring on an appropriate weighted finite automaton (WFA). More specifically, in our case, the WFA can be described as follows: there are (1+ 1) vertices labeled O.....I. There are two transitions from k (k 1) labeled with +1 and I. -1. The weight of the transition with label +1 is exp(+w (xr),, (()),))) and exp(-w (x k)) for the other. 0 is the initial state, and / the final state. The overall time complexity of computing all quantities Qw (1), i [1], is O()..
Conclusion
We presented a comprehensive analysis of surrogate losses for multi-label learning, establishing strong consistency guarantees. We introduced a novel multi-label logistic loss that addresses the shortcomings of existing methods and enjoys label-independent consistency bounds. Our proposed family of multi-label comp-sum losses offers a unified framework with strong consistency guarantees for any general multi-label loss, significantly expanding upon previous work. Additionally, we presented efficient algorithms for their gradient computation. While empirical validation left for future work, our theoretical results demonstrate the potential of these new surrogate losses to advance multi-label learning. This unified framework shows promise for broader applications and paves the way for future research in multi-label learning and related areas.
10

---

References
Awasthi, N. Frank, A. Mao, M. Mohri, and Zhong. Calibration and consistency of adversarial surrogate losses. Advances in Neural Information Processing Systems, pages 9804-9815, 20
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint wwr.iv:2055005555 2021b.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-cconsiseneyy bounds for surrogate loss minimizers. In International Conference on Machine Learning, 2022a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H cooossstty bounds. In Advances in neural information processing systems, pages 782-795, 2022b.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statistics, pages 10077-10094, 2023.
Awasthi, A. Mao, M. Mohri, and Zhong. DC-programming for neural network optimizations. Journal Global Optimization, 2024.
L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138 156, 2006.
J. Berkson. Application of the logistic function to bio-assay. Journal of the American Staristical Association, 39:357- 1944.
Berkson. Why prefer logits to probits. Biometrics, 7(4):327-339, 1951.
Bogatinovski, L.. Todorovski, S. Džeroski, and D. Kocev. Comprehensive comparative study of multi-label classification methods. Expert Systems with Applications, 203: 17215, 2022.
R. Buse-Fekete, H. Choi, K. Dembczynski, C. Gentile, H. Reeve, and B. Szorenyi. Regret bounds for multilabel classification in sparse label regimes. In Advances Neural Information Processing Systems, pages 5404-5416, 2022.
W. Cheng. E. Hüllermeier, and K. J. Dembczynski. Bayes optimal multilabel classification via probabilistic classifier chains. In international conference on machine learning, pages 279-286, 2010.
C. Cortes, V. Kuznetsov, M. Mohri, and S. Yang. Structured prediction theory based on factor graph complexity. In Advances in Neural Information Processing Systems, 2016.
C. Cortes, V. Kuznetsov, M. Mohri, D. Storcheus, and S. Yang. Efficient gradient computation for structured output learning with rational and tropical losses. In Advances in Neural Information Processing Systems, 2018.
C. Cortes, A. Mao, C. Mohri, M. Mohri, and Zhong, Cardinality-aware set prediction and top-k classification. In Advances in neural information processing systems, 2024.
K. Dembczynski, W. Waegeman, W. Cheng, and F. Hüllermeier. An exact algorithm for f-measure maximization. In Advances in neural information processing systems, 2011.
K. Dembezynski, W. Kotlowski, and E. Hüllermeier. Consistent multilabel ranking through univariate loss minimization. In Proceedings of the 29th International Coference on International Conference Machine Learning, pages 1347-1354, 2012.
K. Dembezyíski,, W. Waegeman, W. Cheng, and E. Hüllermeier. On label dependence and loss minimization in multi-label classification. Machine Learning. 88:5 45: 2012.
K. Dembezynski, A. Jachnik, W. Kotlowski, W. Waegeman, and E. Hüllermeier. Optimizing the f-measure in multi-label classification: Plug-in rule approach versus structured loss minimization. In International conference on machine learning, pages 1130-1138, 2013.
Deng, Satheesh, Berg, and F. Li. Fast and balanced: Efficient label tree learning for large scale object recognition. In Advances in Neural Information Processing Systems, 2011.

---

A. Elisseeff and J. Weston. A kemel method for multi-labelled classification. In Advances in neural information processing systems, 2001.
W. Gao and Z.-H. Zhou. On the consistency of multi-label learning. In Conference on learning theory, pages 341-358, 2011.
A. Ghosh, H. Kumar, and S. Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference artificial intelligence, 2017.
A. Kapoor, R. Viswanathan, and P. Jain. Multilabel classification using bayesian compressed sensing. In Advances in neural information processing systems, 2012.
O. O. Koyejo, N. Natarajan, P. K. Ravikumar, and I. S. Dhillon. Consistent binary classification with generalized performance metrics. In Advances in neural information processing systems, 2014.
O. O. Koyejo, N. Natarajan, P. K. Ravikumar, and I. S. Dhillon. Consistent multilabel classification. In Advances Neural Information Processing Systems, 2015.
Y. Lee, Y. Lin, and G. Wahba. Multicategory support vector machines: Theory and application to the classification of microurray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67-81. 2004.
P. Long and R. Servedio. Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809, 2013.
C. Manning and H. Schutze. Foundations of statistical natural language processing. MIT press, 1999.
A. Mao, Mohri, M. Mohri, and Y. Zhong. Two-stage learning defer with multiple experts. In Advances in neural information processing systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023b.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for pairwise misranking loss surrogates, In International conference on Machine learning, 2023c.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In 2C23 Workshop The Many Facets of Preference- Based Learning, 2023d.
A. Mao, M. Mohri, and Zhong. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023e.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning, pages 23803-23822 2023f.
A. Mao, M. Mohri, and Y. Zhong. Principled approaches for learning defer with multiple experts. In International Symposium on Artificial Intelligence and Mathematics, 2024a.
A. Mao, M. Mohri, and Y. Zhong. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. In Algorithmic Learning Theory, 2024b.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. In International Conference Artificial Intelligence and Statistics, 2024c.
A. Mao, M. Mohri, and Y. Zhong, Enhanced H H--coniistency bounds. arXiv preprint arXiv:2407.13722. 2024d.
A. Mao, M. Mohri, and Y. Zhong. --consistency guarantees for regression. International Conference Machine Learning, pages 34712-34737, 2024e.
A. Mao, M. Mohri, and Y. Zhong. Realizable -ccossistent and Bayes-consistent loss functions for learning to defer. In Advances in neural information processing systems, 2024f.
12

---

A. Mao, M. Mohri, and Y. Zhong. Regression with multi-expert deferral. In International Conference on Machine Learning. pages 34738-34755 2024g.
A. Mao, M. Mohri, and Y. Zhong. A universal growth rate for learning with smooth surrogate losses. In Advances in neural information processing systems, 2024h.
A. K. McCallum. Multi-label text classification with mixture model trained by em. In AAA1'99 workshop on text learning, 1999.
A. K. Menon, A. S. Rawat, S. Reddi, and S. Kumar. Multilabel reductions: what is my loss optimising?
In Advances in Neural Information Processing Systems, 2019.
C. Mohri, D. Andor, E. Choi, M. Collins, A. Mao, and Y. Zhong. Learning to reject with a fixed predictor: Application to decontextuulization. In International Conference Learning Representations, 2024.
J. Petterson and T. Cactano. Submodular multi-label learning. In Advances in Neural Information Processing Systems, 2011.
H. G. Ramaswamy, B. S. Babu, S. Agarwal, and R. C. Williamson. On the consistency of output code based learning algorithms for multiclass learning problems. In Conference on Learning Theory, pages 885-902, 2014.
R. E. Schapire and Y. Singer. Boostexter: A boosting boased system for text categorization. Machine learning, 39:135-111 168, 2000.
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation. 26(2):225-277, 2007.
A. Tewari and P. L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8036):0007 2007.
P. F. Verhulst. Notice la loi que la population suit dans son accroissement. Correspondance mathématique et physique, 10:113 10:113-1211, 1838.
F. Verhulst. Recherches mathématiques sur la loi d'accroissement de la population. Nouveaux Mémoires de l'Académie Royale des Sciences Belles-Lettre. de Bruxelles, 18:1-42, 1845.
W. Waegeman, K. Dembezyáski, A. Jachnik, W. Cheng, and E. Hüllermeier. On the bayes-optimality of f-measure maximizers. Journal of Machine Learning Research, 15:3333-3388, 2014.
Weston and Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998.
G. Wu and Zhu. Multi-label classification: do hamming loss and subset accuracy really conflict with each other? In Advances in Neural Information Processing Systems, pages 3130-3140, 2020.
G. Wu, C. Li, K. Xu, and J. Zhu. Rethinking and reweighting the univariate losses for multi-label ranking: Consistency and generalization. In Advances in Neural Information Processing Systems, pages 14332-14344, 2021.
G. Wu, C. Li, and Y. Yin. Towards understanding generalization of macro-auc in multi-label learning. In International Conference on Machine Learning, pages 37540-37570, 2023.
M. Wydmuch, K. Jasinska, M. Kuznetsov, R. Busa-Fekete, and K. Dembezynski. A no-regret generalization of hierarchical softmax to extreme multi-label classification. In Advances in neural information processing systems, 2018.
N. Ye, K. M. Chai, W. S. Lee, and H. L. Chieu. Optimizing f-measures: A tale of two approaches. In International Conference on Machine Learning, pages 289-296,90 2012.
H.-F Yu, P. Jain, P. Kar, and I. Dhillon. Large-scale multi-label learning with missing labels. In International conference machine learning, pages 593-601, 2014.
M. Zhang and S. Agarwal. Bayes consistency vs. H-consistency: The interplay between surrogate loss functions and the scoring function class. In Advances Neural Information Processing Systems, 2020.
13

---

M. Zhang, H. G. Ramaswamy, and S. Agarwal. Convex calibrated surrogates for the multi-label f-measure. In International Conference on Machine Learning, pages 11246-11255, 2020.
M.-L. Zhang and Z.-H. Zhou, A review on multi-label learning algorithms. IEEE transactions on knowledge and data engineering, 26(8):1119-1837, 2013.
T. Zhang. Statistical behavior and consistency of classification methods based convex risk minimization. The Annals of Statistics, 32(1):56-83, 85, 2004a.
Zhang. Statistical analysis some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct): 1225-1251, 2004b.
Z. Zhang and M. Sabuncu. Generalized eross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, 2018.
14

---

Contents of Appendix
Proof of --consistnyyy bounds for existing surrogate losses (Theorem 3.1)
16
B Proofs of K-consistency bounds for new surrogate losses
17
B.1 Auxiliary definitions and results (Theorem B.1 and Lemma B.2)
17
B.2 Proof of Theorem 4.
18
B.3 Proof of Theorem 5.1
19
B.4 Proof of Theorem 6.1
20
B.5 Proof of Theorem 7.1
22
C Future work
23
15

---

A Proof of H-consistency bounds for existing surrogate losses (Theorem 3.1)
Theorem 3.1. Let " Ft. Assume that the following J-consistency bound holds in the binary classification, for some concave function I:R. R,: Vf (f) -Rio (3) M (3) (((o)())- Mb Then, the following H-consistency bound holds the multi-label learning: for all h H,
RI (h) R (H) MI (H)
RLaam (h) Rinam (I() MLna (3C) $ IT
Proof. Let pvy 2) P(Y = y x) be the conditional probability of Y y given X Given multi-label surrogate loss I and hypothesis set H, denote the conditional error by (hh,xx) Eyle [I(h,,,.) y) the best-in-class conditional error by (+(,, inf Ch(,, and the conditional regret by Let (h, er(h, x) xH, We can express the conditional error of the hamming loss and the surrogate loss L follows:
Cleam (11 = Σ
p(vll (
Σ (=th(2,))
yey
= Σ
Σ 1i6-+11
plu x)) (1sign((((.)) Σ p(u p
i-1
Ct (h, Σ plvl Σ ((th((x,1)
yey
Σ xlyl)) (h),,)))) p(vl=))(-h(x.))))) yo
Let qx(+1 x) Evm--1P(8 z) and all i [T]. Then, it is clear that the conditional regrets of Lham and Lbr can be expressed as the corresponding conditional regrets of fo-1 and & under this new introduced new distribution:
E x). Let fo = h(-,)) T, for
AL 3e (h) Σ AC s (f
ACT.. (h, Σ Ae..y(fin
(30)
Since have AG A (fr,z) I(AC, o (fr.)) under the assumption, obtain
AC Me (h,z) Σ AC AClan s
I(Ae
Σ AC AC (11x))
(concavity of T)
IT Aet (h,
By taking the expectation on both sides and using the Jensen's 's incquality, we have
Re (h) -R RE (II) + M. (I() = E AC sc (c(hh, x)]
<
rr
AC
de (h, x.)
Eg A ACT se (h,
< /T
(concavity of T')
1
Ri, (h) - Re (H) + Mr, (H)
/1"
This completes the proof.
16

---

B Proofs of H-consistencc bounds for new surrogate losses
B.1 Auxiliary definitions and results (Theorem B.1 and Lemma B.2)
Before proceeding with the proof, we first introduce some notation and definitions. Given a multi- label surrogate loss [ and a hypothesis set H, we denote the conditional error by (h,, [yiz[[(h, z, v) the best-in-class conditional error by (JC, = infnege e[(h, and the condi- tional regret by (C Cg(h, a)) e (H,, We then present general theorem, which shows that derive JC-consistency bounds in multi-label learning with a concave function I, is only necessary to upper bound the conditional regret of the target multi-label loss by that of the surrogate loss with the same
Theorem B.1. Let L be a multi-label loss and L be a surrogate loss. Given a concave function T:R. R.. If the following condition holds for all h E HH and E X:
xh) & ((,,
(31)
then, for any distribution for all hypotheses e H,
(h) (30) MH( (() R((()) + Mc(H)).
(32)
Proof. By the definitions, the expectation of the conditional regrets for L and [ can expressed as: E E[ (h, =)] (4) (H)) + Mr (H)
Ef (h, x)] Rh) - + M MI()..
Thus, by taking the expectation on both sides of (31) and using Jensen's 's inequality, we have ML
R((h) Ri (3C)
E[ (h.,xx(h..))
s (AAC (h,,))) s
(Eq, (31))
B S (b,
(concavity of I')
(I)((h) 36 (30) MT(H))
This completes the proof.
To derive JC-consistency bounds using Theorem B.I. we will characterize the conditional regret of multi-label loss For simplicity, we first introduce some notation. For any x X, let y(x) argminy/ey [ .v)] y, where we choose the label with the lowest index under the natural ordering of labels as the tie-breaking strategy. To simplify the notation further, we will drop the dependency on æ. Specifically, we use y to denote yz)) and h to denote hæx). Additionally, we define C y [[(. cy Eyy [[y,)]] and C E [Ts/ .w),, Vy e y.
Lemma B.2. Ler = J!. Assume that IF is complete. Then, the conditional regret of a multi-label loss L can be expressed as follows: AeL,x(h, Ch Cy-
Proof. By definition, the conditional error of L can be expressed as follows:
CL x)
[L x. []] = E [[(h(x). Ch- w/F
(33)
Since H[ = Jf and F is complete, for any æ e X, (h(z):h y. Then, the best-in-class conditional error of L can be expressed follows:
(T(, inf CL (L(h,z) hell
x) heDr yfı
inf E [L(((I),,)] [L(v(=).))
(34)
uiz
Therefore, AC (h, e (H(, cn Cy-
Next, by using Lemma B.2, we will upper bound the conditional regret of the target multi-label loss L by that of the surrogate loss [ with concave function I'.
17

---

B.2 Proof of Theorem 4.1
Theorem 4.1. Let H = Assume that 3 is complete. Then, the following K-consistency bound holds in the multi-label learning: for all h e HH,
Rhnam (h)
Ri ham (Ht) Minam (H) s RT (h) 110--jjp R (H)) + Mi (36)
(13)
Proof. We will use the following notation adapted to the Hamming loss: Cn Bult [-nam (h, y)
Cy Byta [[(, and ey (1nam Vy y. We will denote by s(h, x, y')
Fl. M(M().)) Eyney e v(nco, and simplify notation by using sy, thereby dropping the dependency on h and is clear that sy e [0, Then, the conditional error of Liog can be expressed as follows:
Ting (1,
E 2/
(1
Inam (1/ v)) log Σ e e (v.' -V.
y'ey
veey
Σ (1 C2) log(s,) y/Ey
For any h y, we define s" as follows: set si = Sy for all y/ y and y' h; define s = sy μr; and let st Sh μs. Note that s" can be realized by some hí' H due to the completeness assumption. Then, we have
A Fe (h,
log(s,))) inf - (1- (1) log($*)
MeR
y/e
sup
cn (n) [log(s, - (1) loggss))] (1 (1),,)) + p1) log(s,)]}
(sh + sy) cy) sy 112-ch-0 -cy)
(1 ch log (sh + S5) -h-
-11 log
sn Ch cy)
-(1-a)a-(1-c-)e) 2-c,-
(supremum is attained when μl
2(1-cy)
2(1-cn)
2 (1- ([1-c)loo)) log
(2 (2 + (1 - cn) ( log (2 Ch -cy)
(minimum attained when Sn = Sy since On 2 Cy and Sy 2 sy)
2 (Ch - c2
2a (a log a+b
+ blog
2b a+b
2 (a-b)² 2(atb) Va, e [0, 1]
2(2 cy)
(Ch 2
Therefore, by Lemma B.2, AC se (h, s ((C oe (1), (4, the proof.
By Theorem B.,, we complete
18

---

B.3 Proof of Theorem 5.1
Theorem 5.1. Let = 3. Assume that 3 is complete. Then, the following K-consistency bound holds in the multi-label learning:
Wh & H., R((h) - -[((H) (L)) s 2( (h) - (HC) + MI (H))
(18)
Proof. The proof is basically the same as that of Theorem 4.1, modulo replacing the Hamming loss Lham with general multi-label loss L. We adopt the following notation: Ch Byyl [L(h, y) Cy
Eyj v) and cy - ya L()/.)), Vy' e y. We will denote by s(h, (,h') Eynoy e (( and simplify notation by using Sy, thereby dropping the dependency on I and x. It is clear that Sy [0, 1]. Then, the conditional error of Llog can be expressed as follows:
Σ (1 (1) log E (E ]
Cnng (h,.2)
E 1/2
K'Ey
ynEy
Σ (1 (1- log(sy)) y'y
For any h y, we define s" as follows: set si = Sy for y' + and y' * h; define s = sy μr; and let s = Sn + μ. Note that s" can be realized by some h HL under the assumption. Then, we have
ACt A (h,z)2
(1-cc,)
cv) log(())) inf pel
Σ m.y log( log(st)
y/Ey
V/Ey
suup (1 - cn) [log(s, 11) log(sh)] }++ (1 cy [log(s + 11) log neR
(sh sy) (1-))) -y) (1 c.) log (sh + 51
= =(1 -(1-)) log
s, -4 -cy)
5n ch cy)
(supremum is attained when μr -1199)) (1-c)))))11)))) 2-
2(1 -y) (2 Ch cy)
+ (1 - (c) 2(1-ch) (2-ch Ch -cy)
2 (1- log
(minimum is attained when Sp. -sy)
(ch c,)
2a (a a+b
2b (a-b)² blog a+b 2[atb) Va, b [0, 1))
2(2 Cn - cy)
(ch G,)
2 4
Therefore, by Lemma B.2, A ACL 2) AC (h,2)) By Theorem B.1, complete the
proof.
19

---

B.4 Proof of Theorem 6.1
Theorem 6.1. Let H. = F. Assume that F is complete. Then, the following K-consistency bound holds in the multi-label learning:
vh H, R (h) (H) ML()) & ( [comp (h) - R Rcomp (H) M (H)):
(21)
Teomp
where [(t) 2/F when (u) = log u) or 1; -2/ not when vuu) 1/(1 1 20) (0,
and (tt) nt when V (u) -1 "²'
Proof. Recall that we adopt the following notation: Cp = Fyyl [(hh,)): Cy = Bll (vys[[(y))) and ofine s/h((.))
CV y [t)' v) Vy y. We will denote by s(h, (,h)) Eyrny exinn ((M(a.)) and simplify
notation by using Sy, thereby dropping the dependency h and is clear that Sy [0, 1J. Next, we will analyze case by case.
The case where Φ (u) log( u): See the proof of Theorem 5.1.
The case where ((u) 1: The conditional error of Loomp can be expressed as follows:
CT comp
(h, x)
=
E
Σ
(1 - L(2
Σ yrey
s/ey
-111
1
(1- Cyy
s/yy
Sy
For any h h y, we define s" as follows: set st = Sy for all y/ + and y' # h; define s =y μc; and
let sy = Sh + μ.. Note that s can be realized by some h e H under the assumption. Then, we have
A Fe (h1
2 Σ (1 c
inf PER
Σ (1 -1---y cy)
(
1
-11)
Vey
5y
y'ey
1
1
1
1
sup μeR
(1 ch)
+ (1 cx)
Sh
Sy 11
Sy
Sh + p
Ch
1 Cy
2
c. 2(1 on)
)1 (1
Sh
Sy
Sh + Sy
(supremum is attained when μ
VI-c,+vI-c,
2 (1- - (1- -(1-c,)
(minimum is attained when Sn =S, = }
(ch - 22
(1-c,) (1 c,) 2)
(hh 422
2
4
Therefore, by Lemma B.2, A (L,,,((h,,x) s se By Theorem B.I, we complete the proof.
The case where ((u) { 1. ),) (0, The conditional error of Loomp can be expressed as:
1
@romp (h,z)
Σ (1 c. -1 (1-c)))(-((s))))) (9)
q yey
20

---

For any h y, we define s" as follows: set st syr for all y + and y' * h; define s sy and let sy 5n μ. Note that st can be realized by some h H under the assumption. Then, we have
A Lcmmnn H (h)
Lemmp
Σ (1 - (g-c)))(( -,y) inf ueR
(1--c (1-
9 y'ey
a yEy
sup((1 cn) (sy - 11) + (1 (1-c)) (sh + 1u)
uel
(Sh + ( (1- (1 c.) 1 (1 (1- )) _ cn)
(supremum attained when μ -(1-g,) i sp
9,+ (1-,)) -ي (1-c,) पーत (1-c)) lー
1
24 (1- (1- 1-0 (1 c.) ch)
1-9 (1 (1-c)) cc)
qna
(minimum is attained when = :1)
(cn 22)
1-9
a+b 2
2 { b)2 Va, be [0, [
4n
2
Therefore, by Lemma B.2, (h, 2n Aet (h, x)) By Theorem B.1, complete proof.
The case where ((u)= = (1- 1): The conditional error of Loomp can be expressed as:
C (h,z)= = (1-c (1--c)(1-(s5)))
y'cy
For any h + y. we define s" as follows: set s sy for all y/ +y and y' + h; define s sy and let st = Sp + ns. Note that s" can be realized by some h e H under the assumption. Then, we have
ACT eraamp H1 (1),0)
-1s))) -iin-inf inf nict
2 (1 (5)))
Σ (1 - (1-)))))1s)))
y'E4
(v'El)
sup - (1-ch)1-]- -
(1 --]+-4++0
[4]+
G,)[ (-y
Sy + Sn + μ4]
pe
sh (ch cy)
(supremum is attained when μ² sy)
2 (ch Cy).
(minimum is attained when Sy )
n
Therefore, by Lemma B.2, ACL,0 (1, x)) $ nnAe Tromp de ( x). By Theorem B.1, we complete the proof.
21

---

B.5 Proof of Theorem 7.1
Theorem 7.1. Let HC gt. Assume that complete Then, the following H-consistency bound holds in the multi-label learning:
eh HC, R((h) - R)() ML s ST Roonn -h) R (H) Mirond (3)):
(24)
Lestud
where r(t) = 2 when @ ((u) = e, ((() = 2 when ((u) = max u} and r(t) =t
when (uu) max (0, u) puu)= mninmmxx(O. u/p), 1), p> 0.
Proof. Recall that adopt the following notation: C₁ Bi [( y) Cy Eig [[(,,))) and
cy y [ [Ly', .y), Vy' e y. We will also denote by z(h, x/, = Σi=1 (,, i) and simplify notation by using Zy,, thereby dropping the dependency on h and æ. clear that the constraint can be expressed as Eyey Zy O. Next, we will analyze case by case.
The case where Φ (u) " The conditional error of Lestnd be expressed follows:
Ln (h,
E 3
Σ VeEy
[(y', () ((h((,)))
Cyeev.
y'E'd
For any h y, we define z" follows: set 전 Zz for all y' y and y' h; define z -z, μt and let z Ip + μ.. Note that z" can be realized by some h JC under the assumption. Then, we have
A A.r.omp 2t (h, 2 Σ cyceV inf uel
Σ c
yeyy
Wey
sup(cy net
e ch(e - err)))
(Vche*h VC,,3)) )²
(supremum is attained when μ 1 log Ge"r 2 9.e%
Ch -yy
(minimum is attained when Zn = Z, 0)
Viy+ vCh
(ch c2)²
4Lmax
Therefore, by Lemma B.2, (h, ) s 2(Lmax) complete the proof.
x)) By Theorem B.I, we
The case where ((u) max u) The conditional error of Lastud can be expressed follows:
C (h = Σ cy D'Ey
1 2,,
For any h y, we define z" as follows: set z Zy for y' # y and y' # h; define z = Z, μt; and let z Zp + μ.. Note that z" can be realized by some h H under the assumption. Then, we have
A Ae Tenaa oe (h
2 Σ cy max y'ey
inf pel
Σ
Cor max 0, 1 2 22)
y'ey
1u] Cy mm,xx0,1+22) -ma0 1+ + + + cn (0, +zn² max(00 z, )
x)²)}
sup neR
2 (1 + ) 2²)
(differentiating with respect to y to optimize)
2 (cn-c)²²
(minimum is attained when 2, = O)
Ic (h, (Ae Therefore, by Lemma B.2, (L, s proof.
((Att
By Theorem B.1, complete the
22

---

The case where ((u)= = max w):
The conditional error of Lesend can be expressed as:
T Tarrn (h, = Σ Cy max((, zzy). y'Ey
For any h + y, we define z" as follows: set z for all y' + y and y' * h; define x and let z μ.. Note that z" can be realized by some h' H under the assumption. Then, we have
AC A Loana, (h
2 Σ cy ma inf peR
Σ cy max 1 y'ey
sey
Cy (max (0,1 +22 max (0, + 2n + 11}) + cn max (0, +2,)* m00x-max000 m0 2, m)²)}
= ssup pelt
2 (1 (c, - ch)
(differentiating with respect to μ to optimize) (minimum is attained when 2n = 0)
2
Therefore, by Lemma B.2, (C,,)c(h,x)) s ACT Tommn xh) By Theorem B.I, complete the proof.
The case where (u)) expressed as:
1 u/p), 1},0> 0: The conditional error of Lestnd can be
Loand (112;) Σ
Cy min(max 22,p)//
s/ey
For any h y, we define z" follows: set = Zz for y' y and y' # h; define z = Zz μt and let z Zh + μ.. Note that z" can be realized by some h H under the assumption. Then, we have
AC Tenma. (h,
Σ cy m inf yey
Σ cy min m/ g'Ey
neR
sup pel
max mmam (0, (Zn p)/p},13)
on (minn(max(0,1+
1 (in(maax0,,1
2 (cy--C)
(differentiating with respect to μ to optimize)
Therefore, by Lemma B.2, (C, s AC a (h, By Theorem B.1, we complete the proof.
C Future work
While our work introduces a unified surrogate loss framework that is Bayes-consistent across any multi-label loss, thereby broadening the scope beyond previous approaches that established con- sistency only for particular loss functions, there remains an exciting opportunity for empirical comparison with surrogate losses tailored to specific loss functions-2 direction we leave for future work. Furthermore, refining surrogate losses to theoretically enhance performance for specific target losses presents another promising avenue for research.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the section "Our Contributions" in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix C.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification: See Section 3, Section 4, Section 5, Section 6, Section 7, Appendix A, Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
onnooicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ttie//euuieeeeoeSuuuubiiiiii / //nips. wttpccccpppccccceecc httppppullcudll...../ppppppp /Codeeeooiissseeeeee cettsummissiooooo ssisnnoll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
26

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / http///eerip...// wwwtrrps.ccppuuuue
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is theoretical in nature and we do not anticipate any immediate negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
27

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "DaMkrUgFqM", "reviewer": "Reviewer_9NfQ", "summary": "The paper derives H-consistency bounds for binary-relevance style surrogate losses, as well as a new surrogate, for mutli-label learning problems, showing that the proposed multi-label logistic loss whose upper-bound on the Hamming loss is independent of the number of labels.", "questions": "In several places, the paper talks about label correlations, in particular, it claims an advantage of the new surrogate is that it takes into account label correlations. However, it is never specified what exactly that means (conditional correlations, i.e., dependent on the specific instance $x$, or marginal correlations). Further, for many loss functions (such as Hamming-loss), the Bayes-optimal prediction is a function of purely the label marginals $P[Y_i|X]$, so it is not clear to me whether taking into account label correlations actually is an advantage in those cases.\n\nThe paper mentions the decision-theoretic and the empirical-utility framework, but then seems to consider only loss functions that are defined on the level of a single instance. Aren't the two settings that same in that case?\n\nl. 525: Is the argmin unique? Are we breaking ties arbitrarily?\n\nDespite being part of the theorem, $\\mathcal{M}$ does not appear anywhere in the proof of 3.1\n\nI tried going through the proof of 4.1, but I'm not quite sure how to construct the hypothesis $h'$ with that realized $s^{\\mu}$, not do I see why the minimum is achieved for $s_h = s_y$, unless $c_h = c_y$.", "limitations": "I'm not sure if the proposed surrogate actually is tractable for label spaces with more than 50 labels.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The $H$-consistency bounds provided in the paper are more informative than existing Bayes-consistency results, as they hold not just in the infinite limit.\n\nThe novel multi-label logistic loss allows upper-bounds that do not depend on the number of labels.", "weaknesses": "The paper does not provide any experiments. While this is OK for a theory paper, it does mean that the question of whether the new surrogate works better in practice remains unanswered (which should be reflected in the conclusion section, at least), for two reasons:\na) all the theory provides are upper-bounds, which might not be indicative of actual performance\nb) while the theory provides better guarantees for the task loss if the surrogate is reduced to the level $\\epsilon$, it might be that reducing the new surrogate is just much more difficult than optimizing binary relevance. In particular, if the computational cost for reducing the multi-label logistic loss to the same level $\\epsilon$ as binary relevance is larger by at least $\\sqrt{l}$, then, normalized for compute, the advantage of the new surrogate vanishes.\n\nIt is claimed that the gradient of the multi-label logistic loss can be computed efficiently, yet the presented formulas still contain sums over the entire $2^l$ entries of the label space. Even if they can be precomputed once, already at moderate label space sizes of l ~ 100 would these quantities be intractable.\n\nIt is annoying that most equations are unnumbered. Even if they are not referred to in the paper, your readers and reviewers might want to reference them.\n\nthe equation after l. 328 switches between $\\mathbf{\\mathsf{y}}'$ and $y'$; and $y''$ changes to $y$\n\nl. 114: I'm not sure what the point here is of introducing the threshold $t$, if it is set to $0$ in the same sentence? Couldn't $t$ be simply absorbed into $h$?\n\nl. 178-180; 208: Arguably, completeness does _not_ hold in practice, because there is some form of upper-bound (e.g., weights representable in the given floating-point format)\n\nl. 231. Binary relevance is not just Bayes-consistent w.r.t. the Hamming-loss, but also works for precision-at-$k$\n\nIn the equation after line 542, I think $\\bar{L}$ should be $\\bar{L}_\\mathrm{ham}$? \n\nl. 503: I think $q$ should be $q_i$, and there is a weird subscript on that line.\n\nl. 174 consist -> consisting", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and suggestions on improving the readability. We will take them all into account when preparing the final version. Below, please find our responses to specific questions.\n\n**Weaknesses:**\n\n**1. The paper does not ...**\n\n**Response:** Thank you for your insightful comments. \n\nAs you noted, our primary focus is theoretical and algorithmic: the design of \ntheoretically principled surrogate losses for multi-label learning, supported by H-consistency bounds. We observe that some key previous publications on the topic, such as (Gao and Zhou, 2011), do not include any empirical result either. Nevertheless, we plan to include empirical results with commonly used multi-label surrogate losses in the final version of our paper, as you suggested. \n\nOur proposed framework offers significant progress by providing a unified surrogate loss that guarantees consistency for any multi-label loss. This contrasts with existing approaches, which achieve Bayes-consistency only for specific loss functions. While we have demonstrated the existence of efficient algorithms for minimizing multi-label logistic loss, we acknowledge the need for further exploration. Our future work will focus on extensive empirical analysis and the development of more universally applicable algorithmic solutions to cover a broader range of surrogate loss functions and diverse target losses.\n\nWe agree with your observation that optimization is a crucial factor influencing the choice of surrogate losses and their practical performance, in addition to stronger consistency guarantees. The selection of surrogate losses and algorithms in practice should indeed consider multiple factors, including consistency, approximation, optimization properties, label dependency, and label correlation. We hope our work provides useful theoretical insights and potential alternatives helpful for this selection, with more extensive empirical analysis to follow.\n\nIn conclusion, we believe our unified surrogate loss framework, which establishes strong consistency results for multi-label losses, represents a significant theoretical contribution. We are committed to further exploring the empirical aspects of this framework and developing practical solutions in future work.\n\n**2. It is claimed that ...**\n\n**Limitations: ...**\n\n**Response:** For many standard loss functions, the terms involving sums over the entire label space can be computed analytically. We illustrate this below for the Hamming loss and $F_{\\beta}$ measure loss functions :$\\sum_{y} ( 1 - \\overline{ \\mathsf L}_ {\\mathrm{ham}}(y, y^j)  )= -(l - 1) 2^{l} + \\sum_{y}  \\sum_{i = 1}^{l} 1_{y_i = y^j_i} = 2^{l - 1} (2 - l)$, and $ \\sum_{y} ( 1 - \\overline{ \\mathsf L}_ {F_ {\\beta}}(y, y^j)  ) =  \\sum_{y} \\frac{(1 + \\beta^2) y \\cdot y^j }{\\beta^2 \\| y \\|_1  +  \\| y^j \\|_1}$ \n\n$= \\sum_{k = 0}^{l}  \\frac{(1 + \\beta^2)  \\| y^j \\|_1\\binom{l - 1}{k - 1} }{\\beta^2 k + \\| y^j \\|_1}$. A similar analysis can be used for many other loss functions. Therefore, the presence of these terms does not impact the tractability of our algorithms. Additionally, as noted in Section 7, these terms can be precomputed once and reused, regardless of the specific sample or task under consideration. \n\n**Miscellaneous issues:**\n\nThank you for pointing these out. We will number the equations, correct the typos and refine the statements accordingly.\n\n**Questions:**\n\n**1. In several ...**\n\n**Response:** In multi-label learning, label correlation simply means that certain pairs of labels (e.g., \"cup\" and \"mug\") tend to co-occur more frequently than others (e.g., \"cup\" and \"umbrella\") as labels for input points.  Leveraging these correlations can significantly enhance the efficiency of multi-label learning.\n\nApproaches like binary relevance surrogate loss treat each label independently, missing the opportunity to exploit these inherent relationships.  Our new form of surrogate losses directly takes into account such correlations among labels. Both the binary relevance surrogate loss and our new surrogate loss are Bayes-consistent, meaning that minimizing them over the family of all measurable functions approximates the Bayes-optimal solution. However, our new surrogate losses that consider label correlations can converge faster, which is reflected in their more favorable $H$-consistency bounds, independent of the number of labels.\n\nWe will formalize these concepts and provide a more detailed discussion in the final version.\n\n**2. The paper mentions ...**\n\n**Response:** In the decision-theoretic analysis (DTA) framework, a loss function defined as a function over a single instance is considered, and the measure is defined as the expected loss, also known as the generalization error (expectation of a loss function over samples). In the empirical utility maximization (EUM) framework, the measures are directly defined as functions of the population (a function of an expectation over samples). In our paper, we adhere to the DTA framework by analyzing the loss functions and their consistency guarantees in multi-label learning.\n\n**3. l. 525 ...**\n\n**Response:** Any fixed deterministic strategy can be used to break ties. For example, we can choose the label with the lowest index under the natural ordering of labels as the tie-breaking strategy. We will elaborate on this in the final version.\n\n**4. Despite ...**\n\n**Response:** The minimizability gaps appear after taking the expectation on both sides of the inequality between lines 506 and 507, where we used the concavity of the function $\\Gamma$ and Jensen's inequality. We will elaborate on this in the final version.\n\n**5. I tried ...**\n\n**Response:** The realization is due to the completeness assumption. The minimum is achieved for $\\mathsf s_{\\mathsf h}  = \\mathsf s_{\\mathsf y}$ because $\\mathsf c_{\\mathsf h} \\geq  \\mathsf c_{\\mathsf y}$ and $\\mathsf s_{\\mathsf h} \\geq  \\mathsf s_{\\mathsf y}$ by definition. We will elaborate on these in the final version.", "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": "", "extra_scores": {}}, {"review_id": "GCv8AdRJQL", "reviewer": "Reviewer_Abmm", "summary": "The authors study surrogate losses and algorithms for multi-label learning via H-consistency bounds and introduce a novel surrogate loss, multi-label logistic loss in this paper. By broadening the H-consistency bounds analyses to more general multi-label losses and extending to multi-label comp-sum losses, the authors provide a unified surrogate loss framework for H-consistency.", "questions": "See above weaknesses.", "limitations": "Yes, the authors have adequately addressed the limitations.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written and easy to follow.\n2. The authors make comprehensive reviews of related works, including their pros and cons.\n3. The authors provide rigorous theoretical analyses of the limitations of existing binary relevance loss, the H-consistency of the proposed multi-label logistic loss, and the extensions to more general multi-label losses. The theoretical contribution is important for multi-label learning.\n4. The authors demonstrate the efficient computation of the gradient for the proposed multi-label logistic loss and conduct time complexity analyses.", "weaknesses": "1. I understand that this is a theoretical work, and experiments of empirical evaluations are not its focus. However, adding experiments to compare the proposed loss with commonly used multi-label losses on standard datasets would make the paper more comprehensive and appealing. Besides, it can also verify whether the proposed loss is effective in practice.\n2. There is a typo in line 300.($1-\\bar{L}_{ham}(\\cdot, y)$).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. I understand that this is a theoretical work, and experiments of empirical evaluations are not its focus. However, adding experiments to compare the proposed loss with commonly used multi-label losses on standard datasets would make the paper more comprehensive and appealing. Besides, it can also verify whether the proposed loss is effective in practice.**\n\n**Response:** Thank you for your valuable feedback.\n\nAs you noted, this paper is primarily theoretical and algorithmic, and establishes a sound foundation for multi-label surrogate losses, backed by $H$-consistency bounds.  Our framework offers a unique, unifying approach that ensures Bayes-consistency for any multi-label loss, a significant advantage over existing methods.\n\nWhile we have demonstrated that efficient algorithms can minimize multi-label logistic loss, we recognize the importance of further exploration. We agree that empirical comparisons with common multi-label surrogate losses would strengthen our work, and we will strive to include these in the final version.\n\nIn future work, we are excited to expand upon this foundation with extensive empirical analyses. \n\n**2. There is a typo in line 300. $(1 - \\overline{L}_{\\mathrm{ham}}(\\cdot, y)).$**\n\n**Response:** Thank you, we will correct it.", "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": "", "extra_scores": {}}, {"review_id": "FXaut5Lf5V", "reviewer": "Reviewer_sTKD", "summary": "The paper explores surrogate losses and algorithms for multi-label learning, focusing on \\( \\mathcal{H} \\)-consistency bounds. It identifies the limitations of Hamming loss and introduces a new multi-label logistic loss that accounts for label correlations. The study extends this to a broader family of multi-label losses and adapts comp-sum losses from standard classification to multi-label learning. The authors propose a unified framework providing strong consistency guarantees for multi-label losses and describe efficient gradient computation methods for minimizing these losses.", "questions": "1. Could the authors elaborate on the individual components of the multi-label logistic loss and how each contributes to its overall effectiveness?\n2. Given the detailed nature of this loss function, what is the computational complexity associated with implementing the multi-label logistic loss compared to other traditional loss functions? It is better to be able to verify the advantages and complexity of the algorithm through experiments.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors conduct a detailed analysis of the popular Hamming loss in multi-label learning when using smooth losses. They identify its sub-optimal dependency on the number of labels and its failure to account for label correlations, providing valuable insights into the limitations of existing loss functions. \n1. The authors introduce an improvement by presenting a novel surrogate loss, the multi-label logistic loss, which accounts for label correlations and benefits from label-independent \\( \\mathcal{H} \\)-consistency bounds. This innovation addresses the identified drawbacks of existing loss functions and broadens the analysis to include a more extensive family of multi-label losses, including a new extension based on linear-fractional functions related to the confusion matrix.\n1. The authors extend their work by adapting multi-label logistic losses to more comprehensive multi-label comp-sum losses. By demonstrating that this family of surrogate losses benefits from \\( \\mathcal{H} \\)-consistency bounds and Bayes-consistency across any general multi-label loss, they propose a unified surrogate loss framework. This expands upon previous work that only established consistency for specific loss functions, showcasing the applicability of their approach.\n1. The authors' writing is clear and well-structured, with each theoretical assumption and conclusion articulated distinctly.", "weaknesses": "1. In section 4, although the excellent properties of the proposed multi-label logistic loss are proven, providing a detailed explanation of each component of this loss would further enhance the reader's understanding of its superiority.\n2. If the advantages of this loss could be demonstrated through experimental validation, it would be more intuitive for readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weakness 1. In section 4, although the excellent properties of the proposed multi-label logistic loss are proven, providing a detailed explanation of each component of this loss would further enhance the reader's understanding of its superiority.**\n\n**Question 1. Could the authors elaborate on the individual components of the multi-label logistic loss and how each contributes to its overall effectiveness?**\n\n**Response:** That's an excellent question. The component $\\left( 1 - \\overline{\\mathsf{L}}_ {\\mathrm{ham}}(\\cdot, y) \\right)$ acts as a weight vector for each logistic loss corresponding to the label $y'$. The term $\\sum_{i = 1}^{l} \\left( y''_ i - y'_ i \\right) h(x, i)$ represents the difference in the scores between the label $y'$ and any other label $y''$, where these scores account for the correlations among the labels $y_i$ within the logarithmic function. The logarithmic term increases as the difference in scores increases. Therefore, the loss function imposes a greater penalty on larger differences through the penalty term $\\left( 1 - \\overline{\\mathsf{L}}_ {\\mathrm{ham}}(y', y) \\right)$, which is dependent on the Hamming losses assigned to the prediction $y'$ and true label $y$. We will add a more detailed explanation in the final version.\n\n**Weakness  2. If the advantages of this loss could be demonstrated through experimental validation, it would be more intuitive for readers.**\n\n**Question 2. Given the detailed nature of this loss function, what is the computational complexity associated with implementing the multi-label logistic loss compared to other traditional loss functions? It is better to be able to verify the advantages and complexity of the algorithm through experiments.**\n\n**Response:** Thank you for your valuable feedback. As shown in Section 7, the computational complexity for optimizing and implementing the multi-label logistic loss is $O(l)$, modulo the precomputed quantities, which is comparable to that of other common multi-label surrogate losses. \n\nAs you noted, this paper is primarily theoretical and algorithmic, and establishes a sound foundation for multi-label surrogate losses, backed by $H$-consistency bounds. Our framework offers a unique, unifying approach that ensures Bayes-consistency for any multi-label loss, a significant advantage over existing methods.\n\nWhile we have demonstrated that efficient algorithms can minimize multi-label logistic loss, we recognize the importance of further exploration. We agree that empirical comparisons with common multi-label surrogate losses would strengthen our work, and we will strive to include these in the final version.\n\nIn future work, we are excited to expand upon this foundation with extensive empirical analyses.", "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": "", "extra_scores": {}}, {"review_id": "RCZyMlSv6n", "reviewer": "Reviewer_73SN", "summary": "This paper proposes an improved approach to multi-label learning using $\\mathcal{H}$-consistency bounds by introducing the multi-label logistic loss to effectively handle label correlations. It extends to various multi-label losses, ensuring Bayes-consistency across diverse settings, and includes efficient gradient computation algorithms for minimizing the proposed loss function. This work offers a unified framework with robust consistency guarantees, advancing beyond traditional methods in multi-label learning.", "questions": "Please check the weaknesses.", "limitations": "NA", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Introducing the multi-label logistic loss, which effectively addresses label correlations often overlooked by traditional binary relevance surrogates under Hamming loss.\n\n- The paper establishes $\\mathcal{H}$-consistency bounds for a wide range of multi-label losses, ensuring Bayes-consistency across diverse multi-label learning scenarios. This extends beyond previous research that primarily focused on specific loss functions.\n\n- It offers a unified framework that accommodates various multi-label losses, including novel extensions and adaptations from standard classification. This is supported by efficient gradient computation algorithms specifically designed for minimizing the proposed multi-label logistic loss.", "weaknesses": "- The motivation and background of this paper lack clear logic and hierarchy. It is suggested to first outline the shortcomings of existing methods and then clearly present the research questions addressed in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses: The motivation and background of this paper lack clear logic and hierarchy. It is suggested to first outline the shortcomings of existing methods and then clearly present the research questions addressed in this paper.**\n\n**Response:** Thank you for the suggestion. Here is a list of shortcomings of existing methods and the research questions addressed in the paper:\n\n- Lack of Theoretical Analysis: Only a few studies focus on the theoretical analysis of multi-label learning, particularly the Bayes-consistency of surrogate losses. Can we present a comprehensive analysis of surrogate losses for multi-label learning and establish strong consistency guarantees?\n\n- Limited Bayes-Consistency: Existing methods only establish Bayes-consistency for specific loss functions. Can we derive a unified surrogate loss framework that is Bayes-consistent for any multi-label loss?\n\n- Drawback of Bayes-Consistency: Bayes-consistency is an asymptotic guarantee and does not provide convergence guarantees. It also applies only to the family of all measurable functions, unlike the restricted hypothesis sets typically used in practice. Can we leverage state-of-the-art consistency guarantees—$H$-consistency bounds—when designing surrogate loss functions for multi-label learning?\n\n- Sub-optimal Dependency on the Number of Labels: For the simplest form of multi-label loss, the popular Hamming loss, the well-known consistent binary relevance surrogate, when using smooth losses such as logistic losses, suffers from a sub-optimal dependency on the number of labels in terms of $H$-consistency bounds. Can we design smooth loss functions with improved dependency on the number of labels in their $H$-consistency bounds?\n\n- Label Correlations: One of the main concerns in multi-label learning is label correlations. The Bayes-consistent binary relevance surrogate fails to leverage label correlations. Can we design consistent loss functions that effectively benefit from label correlations as well?\n\nTo address these drawbacks, we introduce a novel surrogate loss, multi-label logistic loss, that accounts for label correlations and benefits from label-independent $H$-consistency bounds. We then broaden our analysis to cover a more extensive family of multi-label losses, including all common ones and a new extension defined based on linear-fractional functions with respect to the confusion matrix.\n\nWe also extend our multi-label logistic losses to more comprehensive multi-label comp-sum losses, adapting comp-sum losses from standard classification to multi-label learning. We prove that this family of surrogate losses benefits from $H$-consistency bounds, and thus Bayes-consistency, across any general multi-label loss. Our work thus proposes a unified surrogate loss framework that is Bayes-consistent for any multi-label loss, significantly expanding upon previous work which only established consistency for specific loss functions.\n\nAdditionally, we adapt constrained losses from standard classification to multi-label constrained losses in a similar way, which also benefit from $H$-consistency bounds and thus Bayes-consistency for any multi-label loss. We further describe efficient gradient computation algorithms for minimizing the multi-label logistic loss. This unified framework holds promise for broader applications and opens new avenues for future research in multi-label learning and related areas.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies H-consistency for multi-label learning. It has several main contributions: (i) establishing H-consistency for existing binary relevance with a surrogate loss, then strengthening existing results; (ii) it introduces a new loss called multi-label logistic loss and establishes its H-consistency; (ii) it makes extensions of H-consistency for multi-label logistic loss to a broad family of multi-label losses and extensions to a family of new surrogate loss called multi-label comp-sum losses.  The paper also makes efforts about how to compute the gradient of the proposed multi-label logistic loss. These contributions are considered as novel and interesting.  However, there are still some limitations raised about the paper: (i) lack of experiments, which is an issues mainly because it proposes a new loss and claims its computing is easy; (ii) it may not be practical to use the proposed multi-label logistic loss.  One natural loss that has been neglected in the paper is the extension of multi-class logistic loss, i.e., $-\sum_{i=1}^l y_i \log\frac{\exp(h_i(x))}{\sum_k\exp(h_k(x))}$. The author are encouraged to take the reviews into account in the revision, especially about the claim of efficient computation by either adding some experiments or weaken the claim.
Decision: Accept (poster)