Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Authors: Michal Lukasik
Lin Chen
Harikrishna Narasimhan
Aditya Krishna Menon
Wittawat Jitkrittum
Felix X. Yu
Sashank J. Reddi
Gang Fu
Mohammadhossein Bateni
Sanjiv Kumar
Venue: ICML 2025 poster (2025)
Keywords: learning to rank
area under the curve
multi-objective optimization
Primary area: general_machine_learning->supervised_learning

Abstract: Bipartite ranking is a fundamental supervised learning problem, with the goal of learning a ranking over instances with maximal area under the ROC curve (AUC) against a single binary target label. However, one may often observe multiple binary target labels, e.g., from distinct human annotators. How can one synthesize such labels into a single coherent ranking? In this work, we formally analyze two approaches to this problem—loss aggregation and label aggregation—by characterizing their Bayes-optimal solutions. We show that while both approaches can yield Pareto-optimal solutions, loss aggregation can exhibit label dictatorship: one can inadvertently (and undesirably) favor one label over others. This suggests that label aggregation can be preferable to loss aggregation, which we empirically verify.

Bipartite Ranking From Multiple Labels: On Loss Versus Label A Aggregation
Michal Lukasik" Lin Chen Harikrishna Narasimhan" Aditya Krishna Menon *1 Wittawat Jitkrittum Felix X. Yu! Sashank J. Reddi"
Gang Fu'
Mohammadhossein Bateni Sanjiv Kumar'
Abstract
Bipartite ranking conventionally assumes the existence of single binary label denoting whether or not an instance is "positive". However, in practice, there may be multiple binary labels, each identifying a different set of "positive" instances. For example, in information retrieval, is com- mon for there to be distinct label sources (e.g.. whether or not user clicks on a document, whether or not a hu- man rater deems document be relevant) (Svore et al., 201 Similar challenges arise in applications including medical diagnosis (e.g., balancing opinions from multiple experts as to the presence of a certain condition (Verma et al., 2023)), recommendation systems (e.g., balancing click probability with diversity), and computational adver- tising (e.g., balancing click-through rates with conversion rates); see Appendix E for more discussion of problems involving synthesizing multiple label sources.
Bipartite ranking is a fundamental supervised learning problem, with the goal of learning a rank- ing over instances with maximal area under the ROC curve (AUC) against a single binary target label. However, one may often observe multi- ple binary target labels, e.g., from distinct human annotators. How can synthesize such labels into single coherent ranking? In this work, we formally analyze two approaches to this problem loss aggregation and label aggregation - by characterizing their Bayes-optimal solutions. We show that while both approaches can yield Pareto- optimal solutions, loss aggregation can exhibit label dictatorship: one can inadvertently (and undesirably) favor one label over others. This sug- gests that label aggregation can be preferable to loss aggregation, which we empirically verify.
Given multiple binary labels, can one produce single coher- ent ranking over instances? Addressing this requires formal- ising the goal of such ranking, and then specifying the me- chanics of achieving this goal. The multi-ohjective learning to rank literature provides guidance on both points (Svore et al., 20. Typically, the goal here is to find Pareto opti- mal solutions, i.e., solutions that are not dominated across all objectives (Ribeiro et al., 2015). Towards achieving this, previous works have considered two primary approaches: (I) loss aggregation (also known as linear scalarization, or weighted sum), where the objective is a weighted combi- nation of per-label objectives (Lin al., 2019); (2) label aggregation, where the objective is formulated on single target formed from suitable aggregation of the multiple la- bels, such as weighted combination (Carmel et al., 2020).
1. Introduction
Bipartite ranking is fundamental supervised learning prob- lem (Freund et al., 2003; Cortes & Mohri, 2003; Agarwal et al., 2005; Clémençon et al., 2008; Kotlowski et al., 2011: Menon & Williamson, 2016), wherein the goal is to learn ranker that orders "positive" instances over "negative" instances. This is formalized as learning ranker with max- imal area under the ROC curve (AUC) (Cortes & Mohri, 2003; Agarwal et al., 2005; Krzanowski & Hand, 2009), and is arguably the simplest instantiation of learning to rank (Liu, 2009). Bipartite ranking has seen applications in practical problems ranging from medical diagnosis (Swets, 1988; Pepe. 2003) information retrieval (Ng & Kantor, 2000; Macskassy & Provost, 2001), and is the basis for several other supervised learning problems (Narasimhan & Agarwal, 2013; 3; Reddi et al., 2021; Tang et al., 2022).
Empirically, both loss and label aggregation have proven successful for multi-objective ranking problems. Theoret- ically. however, there has been limited analysis providing guidance on the following natural question: are there rea- sons favor label over loss aggregation, or vice-versa?
In this work, we study this question in the context of bi- partite ranking. We study the Bayes-optimal scorers for both aggregation approaches, which represent the theoreti- cal minimizers given full access to the underlying statistical distributions. We find that both methods broadly yield com- parable optimal rankings, which furthermore are Pareto op-
"Lead authors. Google Research. Correspondence to: Michal Lukasik Emlukasikagooglee.cmm Lin Chen <Lincheagoogle.com com?.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Objective
Defn.
Cost Cagl
Stochustic lubels (Any K)
Deterministic labels (K 2) Purcto-opt
Dictutorship
Prop.
Loss aggregation
(4)
N/A
Eg al)) (x)
a()) (0) +a(0) (p)))) v
v
5.2, 6.1
Label aggregation with
No closed form
(1)(2) + (2))))
5.3. 6.2
Σ, y()))
(5)
1(y 8)) 1 5/
En (2)
(x) +1)))))))))))))
5.4
Table 1. Bayes-optimal scorer for two approaches hipartite ranking with K binary labels. Here, assume that have random
variables (X, y() Y(K)) representing instances and labels drawn from some joint distribution, with (x* = P(y(k) =1 X = x)
denoting the marginal class-probability function for each label. Suitable instantiations of both loss aggregation and label aggregation however, the loss aggregation approach results in an undesirable "label dictatorship" phenomenon, wherein one label dominates the other (see $6.1). The label aggregation objective (5) requires the specification pairwise costs Cys',
satisfy notion of Pareto-optinan
The constants a (k) ax/ /x/(1 (8) (1-x(A) arise in Proposition 6.1, where x (A) = -(((()) = 1) denotes the label priors.
timal. However, we explicate how Pareto optimality while providing foundational concept for multi-objective prob- lems- may by itself be insufficient for desirable practical solution. Indeed, upon closer inspection, we demonstrate that loss aggregation can lead to a label dictatorship phe- nomenon, wherein certain labels are implicitly favored over others. This suggests that label aggregation can be preferred over loss aggregation, which we validate empirically.
Our goal is learn a scorer X - R that ranks the positive examples (i.e., those with Y 1) over the negative ones, as quantified by the area under the ROC curve, or AUC.
Definition 2.1 (Agarwal & Niyogi (2009)). For any scorer S: X - R and distribution D, the (bipartite) AUC is:
AUC(; D) = Ex [M([(X) - f(x)) 1Y> (I)
1 H(=) = 1(2 > 0) + 2 1(= = 00)
In summary, our contributions are (cf. Table l):
(i) We formalize the problem of bipartite ranking from mul- tiple labels ($3), and the instantiation of loss aggregation and label aggregation in this setting ($-4);
Intuitively, the AUC is the fraction of pairs (I, x') E X x X with positive and negative labels wherein f scores the positive over the negative, with reward of 0.5 for ties.
(ii) We characterize the Bayes-optimal solutions to both loss 155 and label aggregation ($5.2), and establish Pareto- optimality of (suitable instantiations of) both methods;
Given some fixed distribution D. a Bayes-optimal scorer f is one that achieves the highest possible AUC; i.e., AUC(f" D) 2 AUC(f: D) for any f: X + R. One may employ the Neyman-Pearson lemma (Lehmann & Romano, 2005) to establish these scorers closely follow n(x).
(ii) We show that loss aggregation can lead to undesirable label dictatorship phenomenon ($6), and empirically validate this on synthetic and real-world datasets ($7).
Proposition 2.2 (Clémençon et al. (2008); Menon & Williamson (2016)). For any distribution D. any Bayes- optimal AUC scorer f" satisfies
Our study serves to analyze the theoretical properties of loss and label aggregation, rather than constructing novel algorithms. This analysis, however, yields practical insights for selecting amongst these methods.
(Vx, E X) n(x) > n(2') - ((a)
2. Background and Notation
or equally, n is any non-decreasing transformation of f
Learning to rank problems seek to learn a scorer that or- ders instances according to an underlying utility score (Liu, 2009). The area under the ROC curve (AUC) is a traditional metric used to evaluate the efficacy of such a ranking (Cortes & Mohri, 2003; Agarwal et al., 2005; Clémençon et al., 2008; Menon & Williamson, 2016). Below, we define AUC for problems with binary and multi-class labels.
We remark here that neither the AUC nor its Bayes-optimal scorer depend on the class prior т. Thus, the (population) AUC is invariant to the amount of label skew, supporting its common usage as a metric in problems characterized by label imbalance (Ling & Li, 1998; Menon et al., 2013).
2.2. Multipartite AUC
One may extend bipartite ranking to ordinal multi-class la- bels y = {1.2, L), wherein higher label values denote higher presence of a certain attribute (e.g., star ratings de- noting user's item preferences). In this case, our goal is to learn a scorer that ranks examples with higher labels over examples with lower labels. Further, one may apply variable costs on mis-ranking of pairs with different labels.
2.1. Bipartite AUC
Consider a supervised learning problem with input space X, binary labels y = {0, 1}. and distribution D over X x y. Let (X, Y) be random variables distributed according to D. Denote by n(x) = P(Y = 1|X= = z) the class- pooss-rrbbabiityy function and . = P(Y = 1) the positive class prior.
2

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Formally, let Dmp denote distribution over X y. As before, we denote the conditional-class probability function by Bly (x) = P(Y = y X z),, and the class priors by Ty = P(Y = v). Further, let Cys' 2 O denote the cost of scoring an instance with label E y below an instance with label y' E y. The following is an adaptation of the bipartite AUC (Definition 2.1) to multi-class problems.
Our goal remains to produce a single scorer s: X + IR. To do so, we must specify a concrete metric for assessing f-
3.2. Pareto optimal per-label AUC maximisation
One natural summary of f's performance is the per-label AUC vector, ie., (UUC(f:D()), ................................ ...CI. AUC(f: ((K)). The problem of synthesizing such vector into a single metric falls within the purview of multi-objective optimiza- tion (Ehrgott, 2005). Adapting a standard goal from this literature, it is natural to seek scorers that are Pareto opti- mal (Ehrgott, 2005) with respect to the per-label AUCs.
Definition 2.3 (Uematsu & Lee (2015)). For any scorer f: X - R. distribution Dmp and costs (Cyy 2 0: y. E
y). the multi-partite AUC is:
AUC (f: = BxEx lorr.
(2)
- -(X))
Definition 3.1 (Pareto dominance), We say a scorer f: X + R Pareto dominates another g: X + R with respect to distributions (D(*) ]ие[K] and only if:
When L= 2. the objective reduces to a scaling of (12). Un- like the bipartite case, the multipartite AUC does not admit a tractable Bayes-optimal scorer in general. An exception is when either L = 3, or the costs satisfy the following scale condition: for suitable constants wy: By 2 O,
(1) Vk E [K]: AUC(;; D(() 2 AUG(S;
(2) 7k E [K] AUC(;; D(A) AUC(J; D(O)..
Definition 3.2 (Pareto optimality). For any (D(*) the set of Pareto optimal scorers TPFS comprises scorers that are not Pareto dominated by any other scorer.
(yy.y' E V) Cyy' wyy - Wyy (sy 1 syy) 1yy > y¹), (3)
For example, (3) holds when Cuy' = (y- v/) ( > v))- Under such a condition, we have the following.
Essentially, a scorer is Pareto optimal if no other scorer dominates it across at least one AUC objective, while not harming it across all AUC objectives.
Proposition 2.4 (Uematsu & Lee (2015, Theorem 3)). Sup- pose L = 3, or the costs {Cwor 2 0: y, E f} satisfy the scale condition (3). For any distribution Dmp- any Bayes- optimal multi-partiin AUC scorer f satisfies
3.3. Does Pareto optimality suffice?
Pareto optimality is a necessary, but not sufficient condition for a solution to be practically useful: a model that aggres- sively optimizes one objective at the complete expense of others, while being Pareto optimal, can be undesirable.
(Vx, x E EX) 3(x²)
r())> (x')
B(x)= = E C1.1 (2(2)
Σ C, (x)
For example, consider document retrieval problem, with the goal of satisfying various aspects of user query; e-g., an ideal system should return documents that are both relevant to the query and likely to engage the user (He et al., 2023). Relevance can be assessed through annotation from a hu- man or machine expert, while engagement can be measured through metrics such as click-through rate or revenue.
or equally, B is any non-decreasing transformation of f
3. Bipartite Ranking With Multiple Labels
We now formalize our setting of interest - bipartite ranking from multiple labels - and the core goal of identifying a Pareto optimal solution with respect to these labels.
In practice, the goals of relevance and engagement may be at odds with each other. To illustrate this point, consider queries from the MS MARCO benchmark dataset (Bajaj et al., 2018). We predict the engagement and relevance of different documents for a query by prompting the Gem- ini model (Team, 2024) (see Table 5 in Appendix for de- tails). Illustrative queries, documents, and predicted engage- ment and relevance scores are reported in Table 2. For the query "What is another name for rust?", document with high relevance but low engagement contains the right answer, albeit with an obscure presentation. Conversely, a document with high engagement but low relevance superfi- cially matches keywords, but lacks the correct answer.
3.1. Formal setup
Consider a setting where we have access to multiple labels for each instance x E X, and would like to produce a single coherent ranking over instances. For simplicity, we begin by assuming each individual label is binary. Formally, for integer K >> 2, (X, Y(1), ...., Y(K)) be random variables distributed according to joint distribution Dint over X x {0, 1 Let μ denote the marginal distribution of X. For each k E [K]. we have an induced marginal distribution (()) over (X, Y(K)). Let (x) = P(Y(K)- = 1 = x) denote the marginal class class-probel probability function of each label k E [K] and n (k) = (((()) 1) the class prior.
On the other hand, for the query "How much does it cost
3

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Query
Low relevance & High engagement documentt
High relevance & Low engagement document
"What is another name for rust?"
formed when exposed lo both aaygen wated water vapopurs. The formula for rust is Fe203 x22.. Now the varies which determines the extent to which rust is formed. Bosically Rust is formed throughout the surface of the irva thus preventing rusting the inner layers.
First
result the oxidation iron. most commoni cause pro- longed exposure to water. Any metal that contains iron, including steel, will bond with the oxygen atoms found in water to form layer of iron oxide, Rust will increase and speed up the comrssion process, upkeep importint here are two ways you can a potato remove rust: Simply stab the knife into polato and wait day or ovemight. 2 Slice potato in half, coat the inside with generous portion of baking soda, and go to sown the risted surface
the haking soda-coated potato
"How nuch does it cost
Once you determine what kind of decking materials you'll lll need build the structure, time get down to price. While the average
I Pre- the-iiahicated bot tuhs cost less, hut are still priced hetween $3,000 and $8 tlur smallcr--ized models). Allhoough you give up some features and styling with inflatable, you can get a good-quality inflatable hot tub starting at about $500. 3 There is quiti a difference in price here.
build deek averages between $4,000 and 510,000, that doesa't t account for the materials. Here is the average cost of cach docking material, broken down by average price range per board: It's important to know what board sizes you'll need purchase for your deck.nce you determine what kind docking materials you'll need huild the stricture, it's time to get down to price. White the average cost to build deck averages between $4,000 and $10,000, that doesn't account for the materials.
to build deck with tub?"
Table 2. An illustration of the trade-off hetween engagement and relevance across queries and documents from the MS MARCO dataset (Bajaj et al., 2018). A purely relevance-driven approach recommends the documents from the rightmost column, which contains the correct answer, albeit with an unclear presentation. Conversely, purely engagement-drivee approach recommends the documents from the first column, which may superficially match keywords, but lack the correct answer. While both solutions may be Pareto optimal, in practice, one may favor only one of these solutions; further, the particular choice can vary depending on the query. Therefore, a solution which globally favors one signal over the other (i.e., where one label a dictator) may be undesirable.
to build a deck with a hot tub?", a document with high relevance but low engagement addresses the specific question of the hot tub pricing. but ignores the more gen- eral context of the price for building the deck. A document with high engagement but low relevance misses the hot tub aspect, but does answer the general question of deck pricing.
linear combination of the objectives (Ruchte & Grabocka, 2021). Such an approach is typically referred to as linear scalarization, and may be seen as performing loss aggrega- fion. In our case, this amounts to maximizing
Σ a2 AUC(f; (())) KE[K]
These examples highlight a common practical challenge: a trade-off often exists between different objectives (in this case, relevance and engagement). Further, while scorers focusing exclusively on one metric could be Pareto optimal - -specifically, if no single document excels at both metrics simultaneously- such solutions may be practically undesir- able. Indeed, solely optimizing relevance at the expense of engagement may be desirable for the first query (where the document contains the correct answer), but less desirable for the second query (where the query intent is open-ended).
for mixing coefficients a.,..., > 0. This is equivalent to the following loss aggregated AUC objective.
Definition 4.1 (Loss aggregation). For any scorer f: X + R. distribution Diat over (X, Y(),..., Y(KO), and weights (az > 0) (ε[K]] the loss aggregated AUC AUC is:
AUCLOA (
(4)
= =E Exx aak H([(X) - ((X))) y(u)> yrs]
Exxx KE[K]
Therefore, alongside ensuring Pareto optimality, it is cru- cial to assess whether solution does not overly favor one of the labels, c.g. via the gap between the per-objective AUC scores (as we consider in $7). This motivates a deeper investigation into the precise forms of Bayes-optimal solu- tions for different aggregation approaches, allowing us to understand their inherent behaviors and potential biases.
For brevity, we subsequently omit the dependence of AUCTma(J) on Dimt Given a finite sample {(x0) ((.1) ...., .......fe .y((.)) [eIN drawn from Dim the empir- ical loss aggregated AUC is
AUCLOA α Σ Σ
as ax- (c-H([((()- - ((200)))
RE [K] (R.))P
4. The Loss and Label Aggregation Methods
where p(k) = {((,)) E [M] x [N]: 10y((M) > y(it))
We now formalize two natural approaches for bipartite rank- ing with multiple binary labels. These aggregate either the losses over multiple labels, or the labels themselves.
4.2. Label aggregation
Weighting the individual per-label AUCs is conceptually simple. An alternative approach is to combine the K labels (y..) Y(K) via some aggregation function vi to obtain a single new aggregated label Y (Svore et al., 2011; Agar- wal et al., 201 1; Dai et al., 2011 1; Carmel et al., 2020; Wei
4.1. Loss aggregation
A common strategy in the multi-objective optimization lit- erature to achieve Pareto optimal solutions is to optimize a
4

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
al., 2023). Given such an aggregated label, one may then maximize the multi-partite AUC (2) Y, as follows:
(x) =
1 E
ak
(1)
(6)
K
T(k) REIK]
.(1 (1- x())
Definition 4.2 (Label aggregation), For any scorer f: X R. distribution Dim over (X, Y(I),... ,..., Y(k)), aggregation function 4b +yk + y, and costs {cgor 2 0) B. the label aggregated AUC is:
equally, "y is some non-decreasing transformation of f"-
The final expression is intuitive: the optimal scorers involve a weighted sum of individual ctass-probabilityy functions
ny(h) In fact, when K = 1, this reduces to the standard result for the AUC (Lemma 2.2).
AUCLaA )
(5)
Exxx [op9-- H(f(X) - ((x())-(xx)) Y > Y
5.2. Bayes-optimal scorers for label aggregation
where Y = =V((), ,.... V(K)) and y _ [K].
Unlike loss aggregation. label aggregation may not always produce Pareto optimal solutions. We show this below with additive label aggregation function and with costs Cpp' 1. ....,, Y(K)) = Ex Y(K), and Cga' = 1, Vū, D' E y. There exists a set of distributions [D(*) ke((K, mixing weights fax 2 (]ke(K). and a scorer f X + IR such that f maximizes the label aggregated AUC in (5), but is not Pareto optimal.
Given finite sample ((x(1) y/(t.).... ....)................... . (t ) KE(N drawn from Dimt, and y(t) = EnE(K] shihk the empirical label aggregated AUC is
Proposition 5.3. Suppose
AUCLaA (f) &
Σ
Cg0 -(((xx()) - f(x6))),
(K.))
where P= = ((i,)) E [ [N]: 1(g(; g0))..
Interestingly, this issue can be remedied with a simple change the AUC objective. Specifically, we choose the misranking costs to be Cgp' 10 > g') j 5'1 in (5), where the cost of misranking a pair of instances scales lin- early with the difference in their aggregated labels. We can then show that the optimal scorers are obtained through sim- ple summation of the class probability functions 17 r)(*)(r)) thus, the Bayes-optimal scorers are also Pareto optimal. Proposition 5.4. Suppose (Y(1), .....
There are several natural choices of aggregation func- tion. Per $3.1, we consider K' individual binary labels y(k) E 1]. One approach is to sum these binary labels: ((,(") Y(K) = EeE(K]
Y(a) E [0. This results in an integer ordinal value, representing the count of positive labels for an instance x. Another natural label aggregation mechanism could be to take the product of the labels: (i ...., Y(k) [IKE(K] ((k) E 1).
Y(K)) (((())...,,Y((K) For any distributions
Ex Y(k),
and Cgs' 1( > 5') -/ T'). (D()) he(K", any Bayes-optimal scorer 8 for the label- aggregated AUC in (5) satisfies
5. Bayes- Optimal Scorers Under Aggregation
We now characterize the set of Bayes-optimal scorers for loss aggregation (Definition 4.1) and label aggregation (Def- inition 4.2). This shall be a step towards understanding the solutions provided by each method.
7xx) > 7(x') = (())>
(x) = [a)=En' (x);
KE[K]
5.1. Bayes-optimal scorers for loss aggregation
or equally, Y is some non-decreasing transformation of f Furthermore, I is Pareto optimal w.r.f. (D(())
We first show that any scorer that is optimal for loss aggre- gation is also Pareto optimal; this follows straiglt-forwardly from Ruchte& & Grabocka (2021).
The simple form of (7) critically relies choosing costs Cpy' [ > 57) 1 - 5 in the label aggregated AUC objective (5), As established by Uematsu & Lee (2015) and utilized in our proof (Appendix B), these costs ensure that the optimal scorer follows Y X = z²). which equals (x) by linearity of expectation. Other costs (e.g., uniform Ggg' = 1, per Proposition 5.3) do not generally lead to this direct summation of (^(x) as the optimal scorer.
Proposition 5.1. For any distributions [D(K) and mixing weights {ax 2 O]kE[K], a scorer 8 : X - lK that maximizes the loss aggregated AUC in (4) is Pareto optimal.
Σn (x)))))))))
As noted in Section 3, Pareto optimality alone may not suffice to assess the usefulness of solution. We therefore take closer look at the form of the Bayes-optimal scorer.
We also note that for arbitrary set of costs Cag' the Bayes- optimal scorer will in general not admit a tractable closed- form solution. This is not surprising: indeed, even when K = 1, the multi-partite AUC does not have a tractable closed-form scorer in general (Uematsu & Lee, 2015). How- ever, for the specific choice of uniform costs Cap = 1, we
Proposition 5.2. For any distributions }D(K) and mixing weights {az 2 []kE[K] any Bayes-optimal scorer I" for the loss aggregated AUC satisfies
(x)) > 7(0') = (r))) (x))
5

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
present scorers that are asymptotically optimal for AUCLA (in the limiting case of K + oo) under some distributional assumptions; see Theorem C.I and Corollary C.2 in $C.
We emphasize that the assumption of deterministic labels is for illustrative clarity of the "label dictatorship" phe- nomenon (Proposition 6.1, Figure 1); our main results on Bayes-optimal scorers (Proposition 5.2 and Proposition 5.4) hold for general 17 (1x). as validated in $7.
5.3. Contrasting the Bayes-optimal scorers
Upon closer inspection, the optimal solution to loss aggrega- tion in (6) reveals subtlety: for K > 1, even for uniform weighting of the individual label AUCs (i.e., 0g = 1, Vk), the optimal scorers depend on the underlying marginal class priors x (k)), Conceptually, this is a surprise: indeed, it is in contrast to the standard behaviour when K = I, wherein the class priors do not influence the AUC optimizer.
6.1. Loss aggregation can yield label dictatorship
We first show that the optimal scorer for loss aggregation ex- hibits a certain dictatorial behavior under the deterministic label setting. This is easy to see when K =
Proposition 6.1. Suppose 1) (z)
E {0, 10. Vx E X and K = 2. For mixing weights 01,02 2 O, denote a (8)
x (i k E {1,2]. Then any Bayes-optimal scorer
Practically, this suggests that the choice of the mixing weights ag determines the extent to which the optimal scorer favors one label over the others. More precisely, the opti- mal scorer favors labels that are marginally skewed (x(() is away from 0.5), over labels that are balanced (z) x 0.5). As we discuss in $6.1, this can lead to an objective that inadvertently favors certain labels based purely on their dataset- imbalance, rather than their instance-specific information content, potentially leading to "label dicta- torship" (see Appendix F for an illustrative example). This is unexpected: one might expect that a uniform weighting (ax- = 1) would induce scorers that treat all labels equitably.
f for the loss aggregated AUC in (4) satisfies:
If a1)) > a12)
(x) > =1 = f(x)>
If a0) > ())
n ( > (z) - (())>(()))
When (1) (2), the ranking is predominantly determined by 17(), and when (1) < (2)), the ranking is predomi- nantly determined by 17(2) i.e., one of the labels acts as "dictator" in determining the optimal solution. This "label dictatorship" behavior can be undesirable in practice. Even if both labels provide perfectly clean conditional signals (i.e., (x) E {0, 1)), a label might dominate the rank- ing due its marginal skewness, rather than its contextual importance. An example illustrating such an undesirable scenario in information retrieval is provided in Appendix F, In contrast, label aggregation results in scorers that equally balance both labels even under uniform costs Cgg' = 1.
is critical to distinguish the marginal probabilities (A()) (( 1) from the instance-connitiooal probabilities (x) = P(Y(#) = 1 X z). A label can be per- fectly balanced marginally (i.e., (A) = 0.5) while being completely noise-free conditionally (i.e., 17(() (x) E 1) for all x). While weighting by the inverse marginal skew (/[nr()(1 - [ might appear statistically natural, this may not align with the conditional quality of the signals.
1}
By contrast, under label aggregation, the optimal scorers equally balance each (A Crucially, the optimal scorers do not incorporate additional weighting under the hood, and thus avoid favoring one set of labels over the others. Further analysis (see Appendix D) shows this optimal scorer (Propo- labels
Proposition 6.2. Suppose 17 (x) E {0. 1), Vx E X and K 2. Then for both costs Cgy' = 1 and Cyg 10ū > v') - 1/ - V1 any Bayes-optimal scorer f for the label- aggregated AUC in (5) satisfies
(xx) > 7x') =
sition 5.4) behaves predictably with aanti))correlaat and can be generalized with explicit non- con-uniform weights, maintaining direct sensitivity to these weights without the hidden rreendepennsscciss of loss aggregation.
>xx = (z) 7z)))
(8)
or equally, y is some non-decreasing transformation of f*
6.2. Illustration of label dictatorship
6. The Perils of Loss Aggregation
We illustrate the above in Figure by showing the partial orders induced by the two objectives for two deterministic binary labels (Y()), (())). Each circle denotes an instance with a combination of (Y(), (Y())), and the arrows indicate that a particular combination is ranked below another. Based on the value of (1) and (2),, loss aggregation either always ranks the label combination (1, 0) above (0, 1), or always ranks (1, 0) below (0, 1). By contrast, label aggregation does not induce any ordering between (1, 0) and (0, 1).
To better highlight the differences between loss aggregation and label aggregation, we consider the special case of de- terministic labels, where P( y....., Y(k) yx) E {0. 1), Vx Vx E X, y (0, 1 Here, we demonstrate that loss aggregation can exhibit undesirable "label dictatorship" behavior, wherein one label is favored over another.
6

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
uct aggregation mechanism is more conservative, in that it induces only a subset of the partial orders among label combinations induced by sum aggregation. Formally:
(1.1)
(1.0)
(1,1)
(1,0)
Lemma 6.3. Suppose (x) E {0,13,Ve Vx E X. Let feum and fproa be Bayes-optimal scorers for the label aggregated AUC in (5) with Yuum ExE(K] Y(k) and
(0,1)
(0,0)
0.11
(0,0)
Y prod = -IlKE(K) Y(k) respectively. Then any 2, x' ex: (a) Ysum (2) > Ysum (1') = (ium(x) > faum (x');
(a) LoA, a > 9
(b) LoA, (1) < (a)
(1,1)
(1,0)
(1,1)
(1,0)
(b) Yprod (x) Yprod (x')
= (proa(x)) fproa (z'):
(c) Tpro Tprodd (z')
= Tsum (1) > 7sum (z'),
where 7aum (x) = ExE[K] (x)),, and Tproa(z) = = II,.., Y(K) = =1 X
(0,1)
(0,0)
(0,1)
(0,0)
P
(c) LaA, sum.
(d) LaA, product.
7. Experimental Results
Figure I. Illustration of partial orders among examples for two deterministic binary labels induced by: (a) Loss aggregation with ( > a² (b) Loss aggregation with (1) < a²)); (c) Label
We present suite of synthetic and real-world experiments to empirically validate our theoretical findings. Specifically, we aim to verify: (i) the "label dictatorship" phenomenon predicted for loss aggregation (Proposition 6.1 and $6. particularly its emergence due to the aforementioned sensi- tivity to (k); and (ii) the consequent tendency for label ag- gregation (Proposition 6.2 and $6.2) to offer more balanced handling of multiple labels compared to loss aggregation.
Aggregation with Y y(1) + y(?); (d) Label Aggregation with aA
Y= Y=YO), y(2)_ As before, a (k)
Each
T(A) (1 (k))
circle denotes an example with values for the two binary labels. An arrow from a circle marked (Y(1) y(?)) to a circle marked (Y()), ((2)) indicates that the label combination (Y(1), y(2) is ranked below (YO), V(2)). The red arrow for the loss aggregation methods depicts the dictatorial behavior described in Section 6.1.
To measure the degree of balanced handling of labels, we report the difference between the per-label AUCs: high dif- ferences indicate that one of the two labels is disproportion- ately favored. Since this metric can be trivially maximized by a scorer achieving 0.5 AUC for both labels, we addition- ally report the minimum over the per-label AUCs. Note that worst-class performance is common metric in prior works fairness (Williamson & Menon, 2019; Sagawa al., 2020). While our focus is on label and loss aggregation, in future work it will be of interest to study how well directly maximizing the minimum per-label AUC would perform.
To make this point concrete, recall our MS MARCO ex- ample (Section 3.3), where Y()) represents relevance and y(2) represents engagement. Then, node (1, 0) conceptually corresponds the document with high relevance but low engagement (the rightmost column in Table 2), while (0, 1) corresponds to the document with low relevance but high engagement (the middle column in Table 2).
The "label dietatorship" behavior of loss aggregation highlighted by the red arrows in Figures 1(a) and ((b) translates to imposing a striet, global preference between high-relevance & low-engagement and low-relevance &
We present experiments on a synthetic and 3 real world datasets with training neural models on loss and label aggre- gation objectives. When optimizing the AUC-based objec- tives, following prior works we employ a logistic or hinge surrogate function. See Appendix G.2 for details.
high-engagement documents. This preference is deter-
mined by the relative values of (2) = ai/ (1) (1)))
and a (2) a2/(=(?) - x()))) (cf. Proposition 6.1).
Specifically,, the ranking will favor relevance if (1)) > (2).
Additionally, in Appendix G.1 we empirically verify the derived forms of the Bayes-optimal scorers for loss and label aggregation (Proposition 5.2, Proposition 5.4).
and engagement if the inequality is reversed. These a values depend on the mixing weights dg and the marginal label skews (Kk), regardless of the specific query or document. As argued in $3.3, such fixed global trade-off might be undesirable. By contrast, label aggregation avoids imposing strict order between high-relevance & low-engagement and low-relevance & high-engagement documents.
Bayes-optimal solutions on synthetic data We begin by analyzing the "label dictatorship" phenomenon directly on the Bayes-optimal scorers (i.e., withoul any model training) on synthetic data. We consider 2D prediction task with two labels, and compare loss and label aggregation as we vary the label skewness T(1,, π (?)) This variation in skewness di- rectly probes two contrasting theoretical predictions: recall
Before closing, in Figure we contrast label aggregation via product Y Y()), y(2) versus summation. The prod-
7

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
10
50
0.08
0.565
Lake des
Low Ap
Liketiap Lou Ags
Les Lou Agp
0.07
E.64
0.34
0.06
0.560
644
332
6:02
0.02
Dift
0.03
Min
0.555
131
cce
6:22
0.30
0.01
0.04
0.03
Objective
Label Ago
0.550
0.545
Objective
Label Agg
0.02
Ago
0.75
0.80
0.85
0.40
0.95
0.75
0.60
c.85
0.40
0.35
Figure 2. Plot of AUC(: - AUC(:; DI for optimal scor- ers as a function of skewness in label Y(2), We compare label aggregation and loss aggregation on the synthetic dataset as de- scribed in the main text. We fix T0)) P(Y(1) 1) 0.5 and vary x x(3) = P(Y = 1). Larger values of sigmoid scaling parameter r make the label distribution closer to deterministic. A lower difference indicates more balanced label treatment by the optimal solution; loss aggregation leads to a higher differenec. Figure reports individual per-label AUC metrics.
Marginal mortgage prob
Marginal mortgage prob.
Figure 3. Plots of |ACCimorgagee AUC(loan) (lower better) and min (UC(morggage) } (higher is better) on the Banking dataset. We compare label aggregation and loss aggrega- tion as we vary the marginal probability of the mortgage label. We find label ageregation fare better in the higher skewness regime.
the mortgage and loan variables two targets.
To study the behavior of label and loss aggregation under label skews, we re-sample this dataset with varying pro- portions of the positive mortgage label, and average results over 25 trials. We train a linear model on numerical fea- tures using Adam for 100 epochs. In Table and Figure 3, we compare the scorers learned by optimizing the loss aggregation objective (4) with d1 d2 = 1 and the label ag- gregation objective (5) with costs Cys' = [ū > 77' ly 7/ We employ the logistic surrogate loss in both cases. Notice that label aggregation is able to better balance between the two labels, yielding the highest Min AUC metric.
that the Bayes-optimal scorer for loss aggregation (Proposi- tion 5.2) involves weighting of individual class-probabilities
(x)) (x) inversely proportional to (Ak)_ (1 - 7(0)), thus leading to "label dictatorship" (Proposition 6) By con- trast, the optimal scorer under label aggregation (with costs Cyg' = 10 1--1 V',, Proposition 5.4) does not involve π (8),
We generate instances E IR22 uniformly from [-1, 1j2. We model the two class probability distributions using logistic model, with (z) a(T w. x) and (x))
a(T (w p)). for sigmoid function (z) = [+exp(-2)
W 22' v2 w2 = [0, 1]" scale parameter >> 0, and shift parameter pž 0. As T - +oo, the label distributions become more deterministic. As p -> +oc, the more skewed is the label distribution 2xx (xr). Specifically, our choice of wi ensures that (11)= (X)) = 0.5; we vary the skewness of (2)) (2) (X)] alone by varying p.
Objective
AUC mortguge
AUC loan
Dif AUC
Min AUC 7
ALComoorgagge)
0.637 0.001
0.523 1 0.002
0.113 0.004
0.002
AUC(loa))
0,550 + 0.005
0.573 # 0,002
0,023 + 0.005
0,550 + 0.005
AUGLA
0.616 + 0.003
0.562 + 0.002
0.054 + 0.005
0.562 4: 0.002
AUC
0.626 + 0.003
0.555 + 0.002
0.071 0.005
0.555 0.002
Table 3. Results on the Banking dataset with the proportion of posi- tive mortgage label set to 0.9. While optimizing an objective for an individual label maximizes the corresponding AUC, we find label aggregation to strike halance between the two evaluation metrics, yielding the highest Min AUC. Here, AUCLeA AUC(morigage + loan) and AU
For each instantiation of the above distributions ( and D(2), we compute the Bayes-optimal scorers for both loss aggregation (6) with e = d2 = 1, and label aggregation (7), and evaluate the difference AUcC = |AUC(f: D()) - AUC(J: D(2)) on 10 samples drawn from (D(1, D(2)). In Figure 2, we plot the differences in the per-label AUC as function of the second label's skewness (2)), Observe that for most skewness values, the optimal scorer for loss aggregation leads to a larger gap in AUCs between the two labels. This is due to the optimal scorer for loss aggregation (6) closely depending on the label priors (1) and π. (2), In fact, the closer the distributions are to being deterministic, the larger is AUC for loss aggregation. This observation closely aligns with the dictatorial behavior described in Section 1 for loss aggregation under deterministic labels.
LoA = AUC(mortgage) + AUC(loan).
Hel HelpSteer. HelpSteer (Wang et al., 2023b) consists of eval- uations of LLM responses across 5 categories: helpfulness, factuality, correctness, coherence, complexity and verbosity. On each category, responses are rated from 0 to 4, where higher means better. While originally intended for usage in LLM alignment, we repurpose the dataset here to illustrate the tradeoffs when ranking along competing signals.
We consider task of ranking concatenations of prompt and candidate response. We binarize each category based on whether or not it equals 4, and fix the first label to coherence (the most balanced category), while iteratively choosing the second label to be each of the remaining categories. Figure 4
Banking, We consider the UCI Banking dataset composed of information about Bank customers, advertising campaign details, and the success thereof (Moro et al., 2014). We take
8

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
225
6.40
8. Related Work
Objectiv
nos Agp
2.59
Objective
Loos Agp
9.15
<abe Ago
5.550
Ago
Bipartite ranking. Bipartite ranking is a fundamental su- pervised learning problem, with intimate ties binary classification and class-probability estimation (Narasimhan & Agarwal, 2013). A large body of work has stud- ied various theoretical aspects of the problem, including statistical generalisation (Agarwal et al., 2005; Agarwal, 2014), consistency of suitable surrogate loss minimisa- tion (Clémençon et al., 2008; Uematsu & Lee, 2015; Menon & Williamson, 2016), relation to classic supervised learn- ing problems (Cortes & Mohri, 2003; Kotlowski et al., 2011; Narasimhan & Agarwal, 2013), effective algorithm design (Freund et al., 2003), and extensions to top-ranking settings (Rudin, 2009; Agarwal et al., 2011; Li et al., 2014).
2.1
0.55
3.00
5.54
complodty
vehvisty
helphttess
curmettnes
complesity
vurboste
harphieness
Figure 4. Plot Diff AUC (AUC(; -UCC;; D (lower is better) and Min AUC min min (AUC(:; DO), AUC(:; } (higher is hetter) for scorers learned with different labels y(2) (sorted according to their skewness, from the most skewed to the least skewed). Experiments on the HelpSteer dataset, where the first label is fixed to coherence (which is the closest to balance, and thus, (2) = P = 1) R 0.5), and the second label chosen over the set of all remaining labels (and so, x² = P(Y(2) = 1) of varying skewness). We find loss aggregation to lead to a higher difference between per-label AUC metrics.
Multi-objective ranking. There has been much work on finding Parcto optimal solutions for multi-objective rank- ing (Mahapatra et al., 2023). A primary focus has been on modifying the LambdaMART objective (Burges, 2010) and evaluating the nDCG evaluation metric, which the orig- inal LambdaMART objective optimizes the upper bound for ( (Wang et al., 2018). Two prominent lines of works fo- cus on loss aggregation (or linear scalarization) (Ruchte & Grabocka, 2021) and label aggregation (Svore et al., 201 I; Agarwal et al., 201 I; Dai et al., 2011; Carmel al., 2020; Wei et al., 2023). To the best of our knowledge, prior works neither considered multi-objective AUC optimization, nor theoretically analyzed the corresponding optimal solutions.
Objective
AUC Click
AUC Rel
Dif AUC
Min AUC
AUC(Click)
0.74
0.61
0.13
0.61
AUC(Rel)
0.70
0.67
0.03
0.67
AUCLaA
0.73
0.68
0.05
0.68
AUCLOA
0.73
0.67
0.06
0.67
Table 4. Results on the MSLR dataset. Learning on both label (click and relevance) helps even when evaluated each label alone. La- hel aggregation strikes a better balance between the two objectives, and achieves the largest minimum AUC over the two labels.
Multi-label ranking. Multi-label classification involves learning to predict multiple labels associated with a given instance (Tsoumakas et al., 2010; Read et al., 2009; Dem- bezyúski et al., 2010). Multi-label ranking generalizes this to learn a ranker over the multiple candidate labels (Brinker et al., 2006; Fürnkranz et al., 2008; Dembezyáski al., 2012). Canonically, such a ranker may be assessed based on an instance-specie analogue of the AUC (Wu et al., 2021). While the problem setting is similar to what we consider, the goal is fundamentally different: multi-label ranking seeks to produce a score for every candidate label, while we seek to produce a single score that synthesizes the labels.
shows that label aggregation yields the lowest difference between per-label AUC across all settings.
MSLR. We next consider MSLR Web3ak, a dataset of users' query-document interactions (Qin & Liu, 2013). We follow the methodology from Mahapatra al. (2023) in construct- ing the target scoring function by removing Query-URL Click Count (Click), and using it in conjunction with the Relevance label. We train an MLP model over the concate- nated features and follow paremetrrseeerrs specified in the TensorFlow ranking library (Pasumarthi et al., 2019).
9. Conclusion and Future Work
We have studied the problem of bipartite ranking from mul- tiple labels, with a characterization of the Bayes-optimal solutions for loss and label aggregation techniques. While these optimal scorers have similar form, we established that loss aggregation can lead to an undesirable "dictator- ship" issue. In future work, it would be of interest to study surrogate losses for the loss and label aggregation strate- gies. Another interesting direction would be to move beyond AUC to metrics such as the nDCG (Wang et al., 2013).
In Table 4, we report results across different objectives. Since the AUC over clicks is always seen be higher than AUC over relevance, min(AUC click, AUC relevance) AUC relevance across all objectives. We find that, com- pared to the label aggregation solution, loss aggregation solutions tend to over-optimize one metric over the other, depending on the weights. On the other hand, label aggrega- tion yields the highest min(AU (AUC click, AUC relevance) and Pareto dominates the loss aggregation with equal weights.
9

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Impact Statement
http://ressarchhnicrooffft ctteett..oomeeeee cww/cooo////eee ww/um/peo////////ee uwppepple///// cburges/tech reports/MSR- TR---R------00 2010- 1e110-2.00 .dd.
This paper presents work goals of which is to advance the field of machine learning, specifically in the area of bipartite ranking with multiple labels. While there are many potential societal consequences of our work, we don't 't feel they must be specifically highlighted here. The presented analysis of loss and label aggregation methods provides deeper understanding of multi-label bipartite ranking, potentially leading to improved algorithms in information retrieval and medical diagnosis applications.
Carmel, D., Haramaty, E., Lazzrson, A., and Sewinn-ytan... L. Multi-objective ranking optimization for product search using stochastic label aggregation. In Proceed- ings of The Web Conference 2020, wwW '20, PP. 373-383, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370233. doi: 10.1 00.1145/366442333888122 URL https::/doi.org/// 2445336664333388022
Clémençon, S., Lugosi, G., and Vayatis, Ranking and empirical minimization of u-statistics. The Annals of Statistics, 36(2):844-874, 2008. ISSN 00905364. URL
References
Agarwal, D., Chen, B.-C., Flango, P., and Wang, X. Click shaping optimize multiple objectives. In Proceed- ings of the 17th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD 11,, pp. 132-140, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 978 97814503081333 doi: 10.1145720204008222045... URL https://doi.org//0. 1245/2020408.2222433
Cortes, C. and Mohri, M. Auc optimization vs. error rate minimization. In Thrun, S., Saul, I.,, and Schölkopf, B. (eds.), Advances in Neu- ral Information Processing Systems, volume 16. MIT Press, 2003. URL https://proceeddings. neurips filees/paperr/00////// Paper. aff pttp:///er....e.ooooorrrrrrrrp
Agarwal, S. Surrogate regret bounds for bipartite ranking via strongly proper losses. Journal of Machine Learning Research, 15(49); 2014. URL http://jmlt. orggpapprrs/vss/gaaraall
Dai, N., Shokouhi, M., and Davison, B. D. Learning to rank for freshness and relevance. In Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '11, pp. 95-104, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450307574. doi: 10. 2,.1445220991162209993 URL 1145/2009916.2009933
Agarwal, S. and Niyogi, P. Generalization bounds for rank- ing algorithms via algorithmic stability. Journal of Ma- chine Learning Research, 10(16))441-474, 2009. URL http://jmtr.ors org/ http://rww....pp////////a//a/a/a /ptppp/s//////aaaaaallaaaaa
Agarwal, S., Graepel, T., Herbrich, R., Har-Peled, S., and Roth, Generalization bounds for the area under the roc curve. Journal of Machine Learning Research, 6 (14):393-425, 2005. URL http://jmmr... htcplj/wr..rrr/////eeeeeeeoooeee org. htggppper///////// ttmm
Dembczyński. K., Cheng, W., and Hüllermeier, E. Bayes op- timal multilabel classification via probabilistic classifier chains. Proceedings of the 27th International Confer- ence on International Conference on Machine Learning, ICML 10, pp. 279-28888 286. Madison, WI, USA, 2010. Omni- press. ISBN 9781 1788160559077..
Bajaj, P., Campos, D., Craswell, N., Deng, L., Gao, J., Liu, X., Majumder, R., McNamara, A., Mitra, B., Nguyen, T., Rosenberg, M., Song, X., Stoica, A., Tiwary, S., and Wang, T. MS MARCO: A human generated machine reading comprehension dataset, 2018. URL https:// arxiv. wwwp///////.....o///o/o/ 09268.
Dembezyúski, K., Kotlowski, W., and Hüllermeier, E. Con- sistent multilabel ranking through univariate loss mini- mization. In Proceedings of the 29th International Cofer- ence on International Conference on Machine Learning, ICML'11, pp. 1347-1354, Madison, WI, USA, 2012, Om- nipress. ISBN 978 150331285..
Brinker, K., Fürnkranz, J., and Hüllermeier, E. A unified model for multilabel classification and ranking. In Pro-
Ehrgott, M. Multicriteria Optimization. Springer, 2005.
ceedings of the 2006 Conference on ECAI 2006: 17th European Conference Artificial Intelligence August 29 September 1, 2006, Riva Del Garda, Italy, pp. 489-493, NLD, 2006. IOS Press. ISBN 1586036424.
Freund, Y., Iyer, R., Schapire, R. E.,, and Singer, Y. An efficient boosting algorithm for combining preferences. J. Mach. Learn. Res., 4(mull):933-99) December 2003.
ISSN 1532-4435.
Burges, C. J. C. From RankNet to Lamb- daRank to LambdaMART: An overview. Tech- nical report, Microsoft Research, 2010. URL
Fürnkranz, J., Hüllermeier, E., Mencía, E. L., and Brinker, K. Multilabel classification via calibrated label ranking. Machine learning, 73(2): 133-113,, 2008
10

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
He, Y., Tian, Y., Wang, M., Chen, F., Yu, L.,, Tang, M., Chen, C., Zhang, N., Kuang, B., and Prakash, A. QueZengage: Embedding-baas based retrieval for relevant and engaging products at facebook marketplace. In Companion Pro- ceedings of the ACM Web Conference 2023, WWw '23 Companion, pp. 386-390, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394192. doi: 10.1145/3543833355663. URL http://i.....rr..11.../...//ee/. 0a..////33338333333
Mahapatra, D., Dong, C., Chen, Y., and Momma, M. Multi- label learning to rank through multi-objective optimiza- tion. In Proceedings of the 29th ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining, Pp. 4605-461 2023.
Menon, A., Narasimhan, H., Agarwal, S., and Chawla, S. On the statistical consistency of algorithms for binary classification under class imbalance. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th Interna- tional Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 603- 611, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL https://proceeedings mlr. wtw.a/ngw......per/eeaeeeeee //mm/mmmnn.....mm html.
Kotlowski, W., Dembczzyíski, K., and Hüllermeier, E. Bipar- tite ranking through minimization of univariate loss. In Proceedings of the 28th International Conference on In- ternational Conference on Machine Learning, ICML'11, pp. 1113-1120, Madison, WI, USA, 2011. Omnipress. ISBN 9781450306195.
Menon, A. K. and Williamson, R. C. Bipartite ranking: a risk-theoretic perspective. Journal of Machine Learning Research, 17(195):1-12,, 2016. URL BRRLhtt://jmlr... papers/va7/14-26553 265.444416.....
Krzanowski, W. and Hand, J. ROC Curves for Con- tinuous Data. Chapman & Hall/CRC, 1st edition, 2009. ISBN 1439800219.
Moro, S., Cortez, P., and Rita, P. A data-driven ap- proach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014. ISSN 0167-9236. doi:
Lehmann, E. L. and Romano, J. P. Testing Statistical Hy- potheses. Springer Science & Business Media, 2005,
001. URL URLLttttps//ww..cccccrrrrrrr... articcle/pii//ox1772226..008
Li, N., Jin, R., and Zhou, Z.-H. Top rank optimization in linear time. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 14, pp. 1502-1510, Cambridge, MA, USA, 2014. MIT Press.
Narasimhan, H. and Agarwal, S. On the relationship be- tween binary classification, bipartite ranking, and binary class probability estimation. In Proceedings of the 27th International Conference on Neural Information Process- ing Systems Volume 2, NIPS' 13, pp. 2913-2921, Red Hook, NY, USA, 2013. Curran Associates Inc.
Lin, X., Chen, H., Pei, C., Sun, F., Xiao, X., Sun, H., Zhang, Y., Ou, W., and liang, P. A pareto-efficient algorithm for multiple objective optimization in e-commerce recom- mendation. In Proceedings of the 13th ACM Conference on recommender systems, pp. 20-28, 2019.
Ng, K. B. and Kantor, P. B. Predicting the effectiveness of naive data fusion on the basis of system characteristics. Journal of the American Society for Information Science, 31(13):1177-11) 2000.
Ling, C. X. and Li, Data mining for direct marketing: problems and solutions. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, KDD'98, pp. 73-79. AAAI Press, 1998.
Pasumarthi, R. K., Bruch, S., Wang, X., Li, C., Bender- sky, M., Najork, M., Pfeifer, J., Golbandi, N., Anil, R., and Wolf, S. Tf-ranking: Scalable tensorflow library for rearning-to-ranks In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining, pp. 2970-2978, 2019.
Liu, T.-Y. Learning to rank for information retrieval. Found. Trends Inf. Retr, 333)2355-331, March 2009. ISSN 1554- 0669. doi: 10. 10.1561//5000000016 URL https://doi.
Pepe. M. S. The Statistical Evaluation of Medical Tests for Classification and Prediction. Oxford University Press, 03 2003. ISBN 97801985098A4 doi: 10.1093/ 0s0/997801985098440000000 081.0001. 1e. /tt.:///////////11181/33
org/10. 1550//000055/110000000011
Macskassy, S. A. and Provost, Intelligent informa- tion triage. In Proceedings of the 24th Annual In- ternational ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '01, pp. 318-326, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581 133316. doi: 10. 1445383952..840155 023952.384012
URL https://doi.org/
Perkio, J., Tuulos, V., Buntine, W., and Tirri, H. Multi- faceted information retrieval system for large scale email archives. In The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI005), pp. 557-564. IEEE, 2005.
URL https: http///oo...//....../....

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Qin, T. and Liu, T. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2597 2013. URL http://arxxv..rg//
Tang, S., Luo, F., and Wu, J. Smooth-aue: Smoothing the path towards rank-based ctr prediction. In Proceedings of the 45th International ACM SIGIR Conference on Re- search and Development in Information Retrieval, pp. 2400-2404, 2022.
Read, J., Pfahringer, B., Holmes, G., and Frank, E. Classifier chains for multi-label classification. In Buntine, W. Gro- belnik, M., Mladenić, D., and Shawe-Taylors J. (eds.), Ma- chine Learning and Knowledge Discovery in Databases, pp. 254-269) 269, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-04174-77
Team, G. Gemini: A family of highly capable multi- modal models, 2024. URL https://arxiv.orggabs.
2312.11805,
Tsoumakas, G., Katakis, I,, and Vlahavas, Mining Multi-label Data, pp. 667-685. Springer US, Boston, MA, 2010. ISBN 978-0-387-0982344 978-0-3877-09823-4333 URL https://doi.org/oe 1007/978-0-387-09222 34.
Reddi, S., Pasumarthi, R. K., Menon, A., Rawat, A.S Yu, F., Kim, S., Veit, A., and Kumar, S. Rankdistil: Knowl- edge distillation for ranking. In International Conference on Artificial Intelligence and Statistics, pp. PMLR, 2021.
doi: 10.1007/
Uematsu, K. and Lee, Y. Statistical optimality in multipartite ranking and ordinal regression. IEEE Transactions Pattern Analysis and Machine Intelligence, 37(5): 1080- 1094, 2015. doi: 10. 10.1 11110T9AM..20142560935
Ribeiro, M. T., Ziviani, N., Moura, E. S. D., Hata, I., Lac- erda, A., and Veloso, A. Multiobjective pareto-efficient approaches for recommender systems. ACM Trans. In- tell. Syst. Technol. 5(4), December 2015. ISSN 2157- 6904. doi: 10.1 10.1145/222930. URL https://doi.org org/ 10. 10.1145/262935.
Verma, R., Barrejon, D., and Nalisnick, E. Learning to defer to multiple experts: Consistent surrogate losses, confi- dence calibration, and conformal ensembles. In Ruiz, F., Dy, J., and van de Meent, J.-W. (eds.), Proceedings of The 26th International Conference on Artificial Intelli- gence and Statistics, volume 206 of Proceedings of Ma- chine Learning Research, pp. 11415-11433 11434. PMLR, 25- 27 Apr 2023. URL https://proceedding mlr...g....rrrr................e prrpeeeeee v206/verma23a.
Ruchte, M. and Grabocka, J. Scalable pareto front approx- imation for deep multi-objective learning, 2021. URL
13392.
Rudin, C. The p-norm push:
A simple convex ranking algorithm that concentrates at the top of the list. Journal of Machine Learning Research, 10(78):2233-2271, 2009. URL http://jml:: org/ haapperr//vo/rrddnnn html.
Wang. X., Li, C., Golbandi, N., Bendersky, M., and Na- jork, M. The lambdaloss framework for ranking met- ric optimization. In Proceedings of the 27th ACM In- ternational Conference on Information and Knowledge Management, CIKM '18 pp. 1313-1322, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450360142. doi: 10. 000114////69220.27777888 URL https://dbi.org: http://ti...rr//....1///////////
Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case gen- eralization. In International Conference on Learning Representations (ICLR), 2020.
Wang, X., Jin, Q., Huang, S., Zhang, M., Liu, X., Zhao, Z., Chen, Y., Zhang, 7., Yang, J., Wen, F., et al. Towards the better ranking consistency: A multi-task learning framework for early stage ads ranking. In AdKDD, 2023a.
Sun, X., Zhang, B., Zhang, C., Ren, H., and Cai, M. Enhanc- ing personalized ranking with differentiable group auc optimization. arXiv preprint arXiv:2304.09170 2023.
Svore, K. M., Volkovs, M. N., and Burges, C. J. Learn- ing to rank with multiple objective functions. In Pro- ceedings of the 20th International Conference on World Wide Web, www '11, pp. 367-376, New York, NY, USA, 2011, Association for Computing Machinery. ISBN 9781450306324. doi: 10. 1935//9996400111994555 URL 196449..
Wang, Y., Wang, L., Li, Y., He, D., and Liu, T.-Y. A theoret- ical analysis of ndog type ranking measures. In Shalev- Shwartz, S. and Steinwart, I. (eds.), Proceedings of the 26th Annual Conference on Learning Theory, volume 30 Proceedings of Machine Learning Research, pp. 25- 54, Princeton, NJ, USA, 12-14 Jun 2013. PMIR. URL https: http:ss///poceeennss..o .ml.. wttpp//reeeeaagi/////// .htll.
Swets, J. A. Measuring the accuracy of diagnostic sys- tems. Science, 240(4857):1285 1293, 1988. doi: 10. 00.11266science.22876111 URL org org/doi/abs/1o. 11c...cceeeeee...388888555
Wang. Z., Dong, Y., Zeng, J., Adams, V., Sreedhar, M. N., Egert, D., Delalleau, O., Scowcroft, J. P., Kant, N., Swope, A., and Kuchaiev, O. Helpsteer: Multi attribee helpfulness dataset for steerlm, 2023b.
12

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Wei, J., Zhu, Z.,, Luo, T., Amid, E., Kumar, A., and Liu, Y. To aggregate not? learning with separate noisy labels. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 2523-2535, 2023.
Williamson, R. C. and Menon, A. K. Fairess risk measures, 2019. URL https://arxiv.org/abbbt
Wu, G., LI, C., Xu, K., and Zhu, J. Rethinking and reweighting the univariate losses for multi-label ranking: Consistency and generalization. Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.). Advances in Neural Information Processing Systems, volume 34, pp. 14332-14344, Curran As- sociates, Inc., 2021. URL https://proceedings ceupips. files//paerr/aaa//ille// /B519/bbeeook/11331e3ss3dddefff pdf
In Ranzato, M.,
Zheng, Y. and Wang, D. X. A survey of recommender sys- tems with multi-objective optimization. Neurocomputing, 474:14 141-13,, 2022.
13

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
A. Additional helper results
Lemma A.1. Let denote the set of pairwise scorers 8: X - satisfying the symmetry condition: o(x,x') = (()
For any distribution μ and weight function w: X X - let
argmax Ex- Ex (') H(x((X sEB
Then,
(1, > 0 +
- w(x' (z', x) > 0.
Proof of Lemma A.I. By symmetry of the expectation, and the definition of H (-), the optimal solution is equivalently
s" E argmax axgmaxxx-ppxx [w X') H(((X, X)) + w(X' X) ((x,((X
$58
(')
if, > 0 if X') < 0 if sXx
argmax Ex Bxiup
w(X', X) (XXX''+(XX'X X
SEB
For each fixed (z, x') E X x X, we thus have
s"xx,x')>0
w(x x') w(x', x²) > 0.
Note that if wxx 2') = w(xx, (x), then the choice of s* sz x') may be arbitrary.
Lemma A.2. For any distribution y and weight function w: + R,
f argmax Ex~, (xXXX') X') H(J(X)
(10)
8: X+X+
Then, if there exists some g= X TR such that
g(z) > g(x') = w(Ixx') > w(x' x),
we must have
f())) > ( (3 = g(x) > g(2¹)
(11)
Proof of Lemma A.2. Let
Rpair (s) = Ex Bx [w(X, X') ([s((XXX))
Rai (f) - Ex~,Ilx-~ ~u (w(X,X') H(f(X) - f(X)))
If there exists satisfying the prescribed condition, then by Lemma A.I, any optimal pairwise scorer s" for Rpair satisfies s* (x,xx) > 0 + g(x) > g(x').
= 8" ((r,,')>< >0 = w(xxx') > w(x', x). and so Jait is ,,,",,,),,,, an optimal pairwise scorer for Reair. Thus, for any alternate scorer g: X - IR with Jain (z, x') = g(z) - g(x'), ). we must have (pair(gaitt) S Reair (Bair). This however implies that Rait (g) S Rait (g) i.e., g is an optimal scorer for the present objective Rait (10).
Now let Saitf (xr, x²)= = g(x) g(x'). Then, gaint (x,xx") >>>00 (²,,,')00
Now suppose f is any candidate optimal solution for Rain. Then, f must satisfy the given condition (11), else (again appealing to Lemma A.1) Jäw will not be optimal for Rpair. Thus, the result follows.
Lemma A.3 (Agarwal al. (2005)). For scorer f: X + R and distribution D, the AUC is equally
AUC(f: D) Ex Bxing_ [H(f(X) f(X'))
(12)
(xz) 1(= 0) 1(= =
where q+ (x) Prlyy = 1) and q q-(x) (xly 0) denote the class-conditional distributions.
14

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Proof of Lemma A.3. See proof of Lemma A.5, which is strict generalisation.
Lemma A.4 (Agarwal (2014)). For any scorer f: X + IR and distribution D, the AUC-ROC is equally
AUC(f: = 1x Bx ~M (x, - - w w(x,x') x') = TT1 T) 7(x)) (1-7(xx)).
(13)
Proof of Lemma A.4. By an application of Bayes' rule to Lemma A.3,
AUC(f: D) = Ex Ex [H(((X) f(X'))
1 π (1-T)
Bxinn (x(: (1 - --(()) H(((X) f(XM
Lemma A.5 (Uematsu & Lee (2015)). For any scorer f: X R. distribution Dmmp. and costs (cvv
AUC(J; pmp) Bex (w X') -X((XX [(X'))
w(x,x') = 1
1(y > 1') Cyys my(xr) 7o (2')
MEY v'Ey
1(y > y') Cyy!" By Tay
y yeyy
Proof of Lemma A.5. We provide proof for completeness. By definition of conditional expectation.
AUC(fi Dmp)
= Exltxx Jery H(F(X) - f(x)) IY> Y
-s X U.a
Σ
D(a,z's v.v/ Y Y)) Cyp' H(f(x) - f(x')) dx dx'
-J xxxx V.yV
1( > v¹) D(I, Voys)
Gyy! H(f(x) - [(''i) - dx do'
D(Y Y")
SExX E1(y > v') D(x,a') D(y sf |xxxx)) Cyy (((('))((x'))) dx
D(Y> > Y")
U.y
ExI
Σ 1(y 1( 5)) (x(2)) my (x') Curl H(((()-
D(Y > Y))
Now observe that
D( D()>))= Σ Σ
1( > 2/) Ty Tgg
ye[l] v'(L)
2
y
DEY
Lemma A.6. For any scorer f: X + R and distributions (D(K) } the loss aggregated AUC is
AUCLAA (f)
Ex- Ex [w (x, X') -
-
( (z) (1 xx))
w(,r, x²)
K
(()) (1 - π (k))
kE[K]
We elide again details on the choice of base measure used define the density on
15

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Proof of Lemma A.6. Building Definition 2.1, have
AUC(S:
(Dpp (E((K)
Σ
ExEx H(f(X)- - f((')) | ((0) > Y(O)]
K
KE[K]
Bx (x) (x=1)(((X')) ()(X)))(((XX)) - -(x))]
K
x(K).
(1 I(())
KE[K]
The result thus follows.
B. Proofs of results in body
Proof of Lemma 2.2. First, observe that by symmetry
1
AUC(f:D)
Exx [n(X) -1- -(f()- - f(X'))
π. (1 - T)
1
1Ex=BBX-- 2 [n(X) (1- -(X))) - -
n (1 - m
(X') - -x(())) H(((X' [(xi]]]
- -(x)) -((()) F(X)]
Bxin 5 (xx()))) -(f(X)(((XX)))))))
Now observe that
w(x,x') > w(x'22) x) = n(0) > n1x¹)
Thus, by Lemma A.2, the optimal scorer satisfies (x) - (1') > = 1(z)- - 11(x))) >
Proof of Lemma 2.4. We provide a proof for L 3 3 for completeness. For the general case, see Uematsu & Lee (2015).
Observe that
w(r x²) uc(x', x))
Σ VEV N'EY
1 > 3/) Cysl (1((x) my(()) (6))-E))
1(y v/) Cyps my((') ny(
NEEN'EY N'EY
Σ yEy N'Ey
1(y v/) Cyp" my ()(x) (o') - ΣΣ
1(y < 5/) Cv'v my(x)) no (2')
1
Σ Σ
auv (2) To (2')
DEV D'EN
1
Σ (x(x) (x)
DEY
where Ogy = 1yy > v/) Cyv' - 1(y < v²) Co'y. and By(x') = =E Ggv' Ty (2'). When T, 3,
Bo(x') C10 1/2 (z') C20 72(x'))
-10 17 (x') C22 + C0 (x'))) + C20 Th (x')
= C20 70 (1) + (C20 - c10) m (x') - C20
(x()) ) = C10 70/ x1) - -c21 =2(2a')
C10 17(21) (x)) - 021 + 021 (0())) 621 17 (a.)
16

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
(c1o 021) no((²) + 021 (1((') 021 (²(x') C20 (u(2²)) + C21 (1()..
We may rewrite the first two expressions in terms of B2:
8a(x') = B2(x'') + (e20- 610 -221 .71 (1') C00 (1 - (2(x') + (c10- 021 020) 770(z') -211
The claim is that
(x) = C10 171 (x) + C00 172(2)
C20 (2) + C21 m1 (z)
C20 T0(2) + (c10 C20) 1/1 (x) + C20
C20 (x( + C21 171 (x)
(o(ar
B2(x)
Observe that
8o(x')
(o(x)
(x(') (1(x))
1 1
(c20 010 (21)
(2(1')
(2(x)
(2(x')
B2(x)
32(x²)
32(x)
(e20 C10 021)
[32(z) m (2') (2()') m (I)] C20 [B2(x) (2(2)),
1 where the proportionality factor is 31())-19(')) 0. Observe that the first term simplifies to:
3²(x) m (x') - (2(2)) 7/1 (zx)
= [c20 - nx( + 621 m7 (z)] mh (=²) [e20 mo(2²) + c21 - (1(x')] (x)
= C20 - (2) m (xx) - no (3') m (x)]
Thus,
30(x²) (2'))) (2(x))
Bo(x)
x (c20
c10 c21) [no(x)) m (2') - -no(=) m (1)] - [B2(x) - (2
Now observe that
w(x,, - u'''''
Bo(x')) (20(x)) (x') (m())) B2(x') 72(2)
[32(x') + (c20 C10 - -21) (1(11))))))) (2') c2ul (z)+
[0) + (C10 - C21 - C20) 7o - cul (x) + 32(x') (x(x)
= (2')') - -n)(x) + (c20- C10 02)) m (x') mx(x) - c20 [1())
32(x') . -m (x) + (C10- - 021 - c20) m0(2²) m (z) -21 . (x) + (2()))) m2(x)
(e20 C10 c21) Im (a') no(x) mo(a)) mz)) + [82(x') - B2(x))
Thus, w(x, x²) w(x x) 0 Bo(w)) (o(z)
Pa(ar) (g(=))
Proof of Proposition 5.2. Note that
w(xxx') K
(x)
Σ kE[K]
(x)((()) (2)),,
(*().
(1 (k))
K
z
(1
((1))
kE[K]
and so
w(z,x') > w(xx,
Σ kE[R]
(x)
1
Σ
1
(0)
K
T
(1
n (k)
K
(k)
x
RE[K]
Thus, it follows that the Bayes-optimal scorer takes the form of the average class probabilities.
17

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Proof of Proposition 5.3. Suppose K 2, and let Y = =kee[]] Y(k)
(o, K}. Note that Y =0 = Y(
A Y(2) O, and similarly Y = 2 < Y()) = 1A Y(2) = 1. Further suppose that Y T Y(2) X. We now have
(z(2)) (1 (z)) : 11-181(0)
= 1 - - - (x)) + (x) . (x))
n (x) = (x) (1 (1- (f) + (1 - (z) (x)
= (x) + (x) - 2. (z) -7 (x)
(z) n/0 (x).
By Uematsu & Lee (2015, Theorem 3), the oayesaoptimal scorer of AUC with uniform costs against Y will preserve the ordering of
(()) (1(2) + 72)))
T0(x) + (x)
(z) + 1/ (x)) - 17 (x)) (x) 1 (1)) (7(2
Consider a dataset composed of 6 examples with independently distributed binary scoring functions, with the following distribution D(I) for the first signal: 17, (z1) 1, 77 (x²2 = 0.2, 71 (ass)) = 0.62, mn (2.) 0.44, mn (2z) 0.56, mi (166) 0.81, and the following distribution D22) for the second signal: (1()1)) 0.44 12 0.56, (2( = 0.81,
(144 1, 722 (25)= 0.2, (26) 0.62.
The optimal solution for the label aggregation objective is foj (a)) = 1.78571, Sogt (22) = 0.72973, Sapa (22) 1.86380. fopt (Ia) 1.78571, fapt (#s) 0.72973, (2g) 1.86380, and yields AUC(fapt: D()) 0.65559 and AUC( (22) = 0.65559. That solution is however Pareto dominated by any scoring function following the ordering of the examples: (4, 2, 5, 3), which yields AUC(g; D(1) 0.65706 and AUC(g; D(2)) 0.65862.
Proof of Proposition 5.4. Let Y = Ex Y(R) E 10. have class probability function fj: X +
K}).
By Uematsu & Lee (2015, Corollary 1), with costs Cyp = (ū > 1/) 10 - 5/1. the Bayes-optimal scorer will preserve the ordering of
K
K
= = ( x = 2] = =Σx n (x)) = > n (z).
n==
==1
We will show that the above evaluates to Ek= (2). We start with the RHS:
(b) (x)
K
Σ
P P((()= y1
y(k) yK
X = x) 1ym = =)
k= yl,
K
Σ
P(Y() = V1. Y(K) = =yx
P
X = 2) 11m =1) 1 (E, -1),1(E,1} 21)
YE 10,1)
K
Σ
P ((()) DI Y(K) =yk x = 2) 1 1 = = Σ
Σソıæ =n)
k= (0
n=1
K
3Σ =ln=lyE(0.11
P (Y(U) = yı .I..... Y(K) yk x x)) 1 = 1) 1 E, yソ = n)
18

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
K K
Σ
P (yil)) = - Y(k) = =y x x= xx) xx=x) - (2,
[E Uo = n) 1( =1)
k= n= yE(0,1)x
Σ
Σ
P
P((()) 11. Y(K) =yK X = x) 1 (1, 2/ =n) Σx= 1 = 1)
n=1 yE{0,13.
Σ
P ((1)) y1,..., Y(K) ,.K,,,,(KK- =yx X = x)) 1 (1 yo =n)
yx
yE(0,1)
K
Σ n
Σ yEf0,13x
P (Y())= yI...., y(k) ((k...,,(()==_ =
yyk yK x 2) -1(E, ys =n)
K
Σ n
P
Y n x= x²)
K
= n mm())
Σ n=1
Since the optimal scorer has the same form that for the loss aggregated AUC in Proposition 5.2 when az = =x()). (1 (,)),, vk, and we know that the optimal scorers for the loss aggregated AUC are Pareto optimal from Proposition 5.1, it follows that the above solution is also Pareto optimal.
Proof of Proposition 6.1. We know from Proposition 5.2 that the optimal scorer will preserve the ordering of (*) a (x) + a2) (x))
We start with the case where () > (2). Since the labels are deterministic r7 ())))))))) E {0,1). Hence when
(x) > n (z'). we have that 17 (z) = 1 and (x') = O. Therefore
(x) = a (1) + (2) (2) (x) 2 (1)) > (2) 2a 17 (x))
a n7
= (x)= fz').
Similarly, when (2) > (1)) and n7 (x) > (z)) we have 7 (x) = 1 and 1/ 1) (x²) = 0. and therefore:
("(x) a1)) -7 (z) + a 2 >a za(1) "0).,/1 ()")
(1)) (1)) (1))+ 2 7))) (()))
which completes the proof.
- 5/ follows directly from the more general Proof of Proposition 6.2. The proof for ordinal costs Cas' = 1(g > gg) -l -1--
case in Proposition 5.4.
We now provide the proof for costs Cog' 1. By Lemma 2.4, since K 330 (Y can be 0, 1 2), the Bayes-optimal scorer will preserve the ordering of
(x)x)
(x) + (2(
mo(x) + (x)
=, Y2) = (M
= P(Y() = 0, Y 0 X x) + ((Y = 0, Y(2) =1 X
P 1
P
We will show that fx(x) is strictly monotonic transformation of:
n (x)) + (x)) = p( = 0, =1 X=
19

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
+ -2-P(Y()) Y(2) 1, x x).
Since the labels are deterministic, P( = i X = x) = for exactly one particular (i.5). We consider all four possible cases:
(1) 0, Y 0 X 2) We have: (*) and n (z) + (2) O.
(2) = 0, 2 = X = z) = 1. We have: ((x) and (x) + (x) = 1.
()) = 1, Y:2) 0 X = z) = 1. We have: f (x) and 17 (z) + // (x) = 1.
(4) ( 1, Y =1 X
1. We have: (z) and (2) 17 (x) (z) 2.
Clearly, (x) is strictly monotonic transformation of (x) + 1/ (2) (x).
Proof of Lemma 6.3. The first statement (a) follows directly from Proposition 5.2.
For the second statement (b), let Y II Y(k) {0, 1} have class probability function Uprod: X - [0, 1J. Applying Lemma 2.2, the Bayes-optimal scorer fproa preserve the ordering of:
?prod (x) = 7prod (x) = P(Y = I,..., Y(K) = 1 x)
For the third statement (c), given that the labels are deterministic, we note that Yprod > Pproa (2') implies that P(Y(1) 1..... Y(K)
x) 1, while P(Y(1) I,..., Y(K) =1k...,(()) 1|x x²) = 0. This indicates that
Ysum (z)
Ex 17 (k) (x) K and 7sum (x') = Ex (k) (x K. As result, 7sum (I) 7su (x¹).
C. Additional theoretical results
Theorem C.1. Suppose that the labels are binary, i.e., ((k) E {0, for all lo E N21, and ag > O. Assume further that the labels (V(M) kkENz are jointly independent conditioned on X. Consider the aggregation function ((((1) y..., Y(K)) =
Exe[K] ag (Kk, Define
8r argmax AUCLA (F:(D(1)). FX-
f(x) Σ aen)(=)
KE(K]
where o: R + +RR R is a strictly increasing function. Then,
AUCIA (F:(D AUCIA (f:(D(1))
ELEKY at EiELLEY ma(x:) (1 (X:)
$ Bxixx
(EiE a EietLay
(x.) (x)))))))(())) mx(x))) 3/2
where (t) A 2t I-+- and X1 and X2 are i..dd. copies X
Corollary C.2. If ag = for all and qu (x) is bounded away from and 1, i.e., there exists e (0, 1/2) such that (x) E |c, 1- for all is Nz1 and for all E X, then the expected AUC difference between the optimal prediction function fr and f converges to zero with rate of O(1/KK)):
AUCLA (F:(D()))) AUCLA (f:(D())) = (1x)
VK
Proof of Theorem C.I. Given a function f:X + R, we first rewrite AUC (f: (D(+)) as follows:
AUCLaS (Fi(D((1)) =E H(((x)) f(xi)
Σ a (K))
Σ
(k)
ag 2
KE
kE[K]
20

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
E H(f(X²) - f(Xi)I
[EaciK] a.Y <I EEECIA E Y
P [EKE[K] as Y EKE(KK ax 2
E H(f(x)) - f(Xi) a
aors ELEIKK y
CK
where
CK _ p
Σ
aK ((())
E
On (())
kE|K]
KE[K]
1
Σ ax y -0)
1 - IP
2
kE|K]
kE[K]
Define
EKEIKI ak (Tx(X2) -7 (X1))
X2) A
ELE[KI de EiE(L2) The (Xx) (1 7h (X:))
and the functionals
[K(J) E ( EEeEN Y < EnEln on (v (x1,
(f) - -
where (--) is the cumulative distribution function of the standard normal distribution.
Next, we will show that f maximizes Fx() In other words, we aim to prove that for any f.
F2() S FR()).
On one hand, we have
1 (f(((()))) (1 xx) - (Z
Fk(()
(X2 X1)]
2
1
マ [((((()) - f(X,)) ( (X1, Xx)) + H(())) - (1- (XI,
$ 2 B |max (2 (v (X1, X2)) 2 (M (X1, X2)III|
On the other hand, let Si EKE(K) 01 (X1,, 82 EKE[K] 4oT (X2), and Φ,, + (v (X1,X2) Since & is strictly increasing, H(f(X²) f(Xi)) = HS2 S1) and H(f(x)) f(X2)) = H(1 -S2). Then,
F2(O- = E [H(((x))
E [H(((x))
-(((())) (.,
= E (11SS228) + 1 2 -1( )0or)))))) p. x.+ + (11Si2S))+ + 1 -
118--811) ) (1 (1-b,)
x.)
E [max (0,, 1 D.
Now, we proceed to bound the gap between (f( and (f). We first rewrite Fx (f) as
Fx (f)
21

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
= E ((f(Xa) - ((X)) 1
[x1,X|]
[ENCIN) <XxC)) as y2
E
H(F(X)) f(X:))
Σ an Y
Σ
Y
(k)
X1,2
KE[K]
kE[K]
- (xi)) | X1,x² X2 ]
E
HI((x2) S(X)))
Σ
Yx+ + E
Y
Σ
ax -
kE[K]
kE[K]
RE(K]
E (2() - I(X))) (Sx < v (2) X2)),
where
Y& 2 ak (Y(t)) (xi)
Y _ ak (Y5)) nh (xa))))
EREIK) YN + EKEIKK YE
SK
v SmELK] of ExE(U.)) m (X:) (1 (X.))
Note that Yv and Y3 have zero mean, i.e., E Yv X1, X2] = E Y X2] = 0. Moreover, we have
E Yal² 2 X1, X2
= = (((b] my (x1)
|x1,X]
aonn (x1) (1 m (X1)),
E Ykl 3 X1 Xx]
= azf |((b] - nx (x1) )²²
|1, X2
= (x) (1 - (x1) [( (1-nk (xx))) + =x()))
3 n (X1) (1 nx
Similarly,
E Y 2 X1, X1] (x2) (1 (1xr((()
E
Y 3 X1, X2
5 $2"0 2x (X2) (1 m (X2))
By the Berry-Esseen theorem, for any t,
(Sx
<t X1, X2) - + (t)
-3/2
Σ YY X1 X2 + Σ
E
| 1 (x. Xa]
KE|K]
kE[K]
Σ E [Ma X1, X2] + Σ R. [Ya] X1, X3]
RE]K]
KE[K]]
ΣREIKY
0 EiE(1 The (X,) (1 - 7/4 (X+))
[KE[K] of EiE(LE)) The (X,) (1 - 7r (x.)) 3/2¹
We can now bound the gap between (f) and Fk)():
[Fx()- - (F)
22

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
[B(H(((X2) [(X))P (Sk <X, - (X,, {E(H)(((X2) f(x)) (SK < < (2) X1 - 4 (v [2))1]]
s <B|P[(>< < (X X2) - 4 (v X2))l
EKEIKT oe Eie(1 m (X,) - 7 (X,))
S
EKEIKI of EietL (x)) (x.)))) (x))) 3/2
2
Therefore,
F - Fk(F)
= (Px(f)) -K((D)) + - + -x(()))((())
ENEIKI oh EiEtLe) nh (X:) (1 mx)))
S E
(x,)) (1-(x)))) 3/2
EnE(KK] o Eie(1a) (X,) (1
Next, we establish upper bound for IP ExElRaas Y6 -KKE(K] as Y -6)=))) 0): =0):
P
a4
((k)
(k)
Σ
ag
2 =0
(k)
KE[K]
kE[K]
Y (k) =0 Xxx ]
E
P
OK ( (K)
Σ
KE[K]
kE[K]
E
IP (SK= V (X1, X2) X2]]
E
P(SK S v (X1, X2) (2, (x,
lim
st1 PP (Sxx S X1, Xa)
(P St X2) -x) (t))
E
ISK Sv vX(x X2) X2) 4 (2 X2))
lim Xx)
Taking the absolute value, we get
P
Σ as Y((k)
Σ
ax Yx)
(k) =0)
KE(K]
RE[K]
(S S X1, X2) - (1)]
< E
PP Su (X1: X2) (21 $ (v ((((X),22)) + lim
(x)
ExE(K] o EiE(UE)) (1-) (X,))
< E
Ekee(Ky of Eie(1a) (xx (1 - (1-1)(Xx.)) 3/2
Consequently, we obtain a lower bound for ex:
EKEJK| of EiE(1 7k (X:) (1 mh (X:))
CK 2 max
1
.0
2
[IEEKK] of EvE(12) (X;) (1 The (x:) 3/2
Recall that AUCLaS (f: (D(H)))
Fx.())
We then have
ex
AUCLa (F:((())))) AUCIaA (J: (D(N)))
23

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Fx(f)) (x
CK
Exclal of Lic (1.2) mx(K)(I-m(Xx]])
2 E
(EKEIK) of (1E(1 (x))
ELEINy of 21 Th (x(x)((1-xxxx;))
(EEENN of DiE na (x)
EnELKi ae Eie 1h (X:) (1 mi (X:))
EnE[K] o EiE(L2)) Th (X,) (1- (x.))) 3/2
Proof of Corollary C.2. By Theorem C.1, we have
AUCLaA (f:(D(()))
- AUCLaS (f: (F:()()))
S 16
E
[ (ENE(K) EiE(ue)) Th (x mh (X.1)) 1/2
S 1b
220(1 c)K
0
V
D. Further Analysis of Label Aggregation
This section addresses further properties of label aggregation, including its behavior with anti-correlated labels and its sensitivity to mixing weights, expanding on the discussions in Section 5.2.
D.1. Behavior with Anti-correlated Labels
Our theory (Proposition 5.4) shows the optimal scorer for label aggregation (cost Cgg 1 ranks by f*)) x ( (xr). For K = 2, this is equivalent ranking by 5(x) p((()) 1, Y(2) 1 X x) ((Y 0, Y(2) = 0
X z). The derivation below shows (x) 6(z).
= 1, 22 From Proposition 5.4, the scorer is (z)))) (z). We have (x)) -
+
= 0 x = + 1, =,,,) =
1, )2 = X = 2) and of (2) = 0,)
=1|
= x). Summing them gives
=1, = = = z). (22) = X x) the sum simplifies 1 (p((()) Y(2) =0 x) +)+ 1+ 8(x).
(x) + 1/ () (z) = p( (1
=0, =0, = =0, =1|==
= 1,
= Y(2)
Since p((()) Y() = X= z)
= ==]
= =
This shows the optimal scorer does depend on label correlations via 6(z). Let's consider the implications:
Overlapping (Y(1) = (?)): 6(x) x 7/ (æ). the ranking uses 7/ (r), which is sensible.
Anti-correlated (Y = Y(2)); 6(x) = 0. The scorer f(xx) is constant, yielding no ranking. This indicates
reduced robustness when the aggregated label Y()) y(2) 1 is constant, making the AUC objective ill-defined.
Mild anti-correlation: Here, both (((()) = 1, 2 = = x) and p(Y(1) = o. Y = 0 X = x) would be small, and the ranking depends on their difference via 5(x). E.g., when 5(x) > 0. it is more likely that both labels are I than 0, resulting in x being ranked higher. The behavior would depend on the exact conditional probabilities.
24

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
D.2. Sensitivity of Label Aggregation to Mixing Weights
We next generalize label aggregation by using non-uniformm weights 0',, 02 > 0 for the aggregation function, i.e., Y a1 Y(I) + 02 Y again for the K = 2 case for simplicity.
Following assumptions of Proposition 5.4 (that the Bayes-optimal scorer for costs Cyj' = - y preserves the ordering of
E| æD), the Bayes-optimal scorer rīz) = E| X x] becomes:
Π(x) = -0 (((()))) = 0, y(2) = 0 = z) + 01 - p(Y = Y(2) = X =
+ p(Y(1)) 0, Y( = 1 X z) (a1 +2) p((()) = Y 1 X x)
-an.bo = 1, = X z) + p = 1, Y(2) =1 X = x)]
+ 192-mmn (I(( 11
- 0, 1
+ 1, 1,
X = x)]
= =0 (1) + (x)
This result shows that the optimal scorer for weighted label aggregation is a direct linear combination of the individual plobabiboyyy functions ()()) weighted by the explicitly chosen aggregation weights Crs.
This contrasts sharply with the optimal scorer for loss aggregation (Proposition 5.4), which is Σx - -00-(1-000 17 () (z). In
loss aggregation, the effective weight on 1f(x (z) depends not only on the chosen mixing weight but also implicitly on the label prior (k),
Therefore, regarding sensitivity:
The label aggregation optimal scorer (under the assumptions above) is sensitive to the choice of weights ag in a direct and predictable way: the final scorer is exactly the or -weightt sum of the 77 (z)) It is notably insensitive to the class priors (4))
The loss aggregation optimal scorer is sensitive to both the chosen weights ag and the class priors x (*) through the (K)) x (8)) term.
E. Further Discussion on Application Scenarios
The problem of synthesizing multiple binary labels into a single coherent ranking has widespread applications beyond the initial examples of information retrieval and medical diagnosis mentioned in $1. Our analysis of loss versus label aggregation, particularly regarding Pareto optimality and the "label dictatorship" issue, can inform choices various real-world systems. Below, we elaborate on some potential application scenarios:
Users' information needs can be complex, requiring documents to be relevant across multiple dimensions or interpretations. For example, a search system might need to rank documents based on topical relevance to different aspects query, alongside signals for document freshness, geographical relevance for location-sensitive queries, or authoritativeness of the source. Each of these aspects can be represented by a (potentially binary) label (e.g.. "ish, "is iis.go..releannn Effectively combining these signals crucial for user satisfaction (Perkio et al., 2005).
Multi-faceted Information Retrieval:
Recommendation Systems: Modern recommender systems often optimize for multiple objectives simultaneously. For instance, beyond predicting user engagement (e.g., click-through rate, purchase probability), systems may also aim to promote relevance to users' long-term interests, ensure diversity in recommendations to avoid filter bubbles, or uphold fairness considerations across different item providers or content creators (Zheng & Wang, 2022).
Computational Advertising: Ranking advertisements effectively requires balancing predictions from multiple models. Commonly, platforms consider both the predicted click-through rate (CTR) and the predicted conversion rate (CVR) the likelihood that a click leads desired action (e.g.. a sale). The final ranking aims to optimize overall platform revenue or advertiser value, which often involves synthesis of these distinct predictive labels (Wang et al., 2023a).
In each of these scenarios, understanding how different aggregation strategies (loss versus label) behave, as explored in our work, can lead to more principled system design. The choice of aggregation method can influence how trade-offs between objectives are handled and whether certain objectives inadvertently dominate others.
25

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
F. Illustrative Example of Undesirable Dictatorship in Loss Aggregation
$5.1 discusses how the Bayes-optimal scorer for loss aggregation (Proposition 5.2) weights individual blas-pprbability functions (7* by ax/[<(A/
x ( ]]. This means that even with uniform explicit weights O = labels that are more marginally skewed (i.e., n (4k) is far from 0.5) receive higher effective weighting. We clarify that T( P 1) is the marginal prevalence of a label, which is distinct from its conditional probability 77 (x) P(Y = X x) for specific instance A label can have balanced marginal prior (T RJ 0.5) yet be perfectly deterministic (noise-free) conditionally (c.g.. (x) E {0,1}). 1)).
Proposition 6.1 1 formalizes the problem whereby one label can become a "dictator", i.e. the ranking overly favors it. Below an illustrative example from information retrieval where such dictatorship, driven by marginal skewness, would be undesirable.
Consider ranking documents based on two binary, conditionally deterministic frree, (x)) E {0,1)) labels:
y()) "is.relevant" " (core topical relevance to the user's query).
Y "is.recent" (document published in the last 24 hours).
Assume the following marginal priors in the document collection for a typical query:
For "is.relevant" (Y())): A good number of documents are relevant, and many are not. Let t(1) = -0.4. Thus, n (1) - x())== = 0.4 x 0.6 = 0.24.
For "is recent" (Y())): Very few documents are extremely recent. Let (2)) 0.01. Thus, n (1 -2(2)) 0.01 x 0.99 0.0099.
If we use loss aggregation with uniform explicit weights 01 = 1 and 02 1, the (k) terms from Proposition 6.1 become:
a = a (1) - x1)] = 1/0.24 x 4.17.
2 =2/1 x x = 1/0.0099 101.01.
Since (2) >> (1)), according to Proposition 6.1, the "is_recent" label (Y(2) will dictate the ranking. The system will primarily rank documents based on whether they are extremely recent. An irrelevant but very recent document would likely be ranked above a highly relevant document that is not from the last 24 hours.
This outcome is undesirable if the user's primary goal is to find relevant information, with recency being secondary, tie-breaking, less critical factor. The loss aggregation objective, in this case, inadvertently prioritizes the "iserecent" signal heavily, not because its conditional signal is necessarily stronger more important for the user's core task, but because its marginal distribution is highly skewed. The system optimizes for a property of the label's distribution in the dataset (its rarity) rather than strictly adhering to an equal consideration of the (equally clean) conditional signals for relevance and recency. This highlights why relying on marginal priors for weighting can be problematic. Label aggregation (Proposition 5.4, with appropriate costs) would score by 17 (x))))) + (x)). giving equal intrinsic weight to the conditional signals from (1)) and ((2) regardless of their marginal priors.
G. Empirical details
In this section we provide details to empirical experiments in the paper.
In Table 5 we summarize the prompts used to obtain relevance and clicks labels for the MS MARCO examples shown in Tables 2.
G.1. Synthetic data generation for the exhaustive enumeration of the optimal solutions
We begin with a synthetic experiment with a goal of verifying our theory pertaining to maximizers of the loss aggregation objectives. We generate a synthetic dataset, and compute the optimal solutions via brute force evaluation;
26

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
Label
Input prompt
Engagement
Imagine you are an information retrieval expert. Your aim to judge whether the following document will be clicked if it is shown for the following query.
Query: {query)
Document: {document)
Do you predict this document will be clicked for this query? Output only yes or no and nothing else.
Relevance
Imagine you are information retrieval expert. Your aim is to judge whether the following document will be considered relevant by normal user if it is shown for the following query.
Query: {query)
Document: [document} Do you predict this document will be considered relevant by a normal user for this query? Output only yes or no and nothing else.
Table 5. Prompts used for predicting engagement and relevance of different documents per query in MS MARCO dataset (Bajaj et al., 2018). We select documents according the original order from the MS MARCO dataset.
We consider a two dimensional Gaussian distribution with zero mean and a uniformly sampled covariance matrix E. We sample N two-dimensional samples and consider the first dimension to correspond to 31 (I) (clicks) and the second dimension to y2(2:) (relevance). We make the two scores bi-level by thresholding the numbers O.
We aim to consider exhaustive set of hypotheses such that it is possible to conduct brute force evaluation of different objectives. To this end, we consider the following hypothesis class f. We consider the image of f to be [P] = 21.2..... .............................. P). For each sample x and the corresponding relevance scores y1 (I) and (z). if both relevance scores agree, we set fxx to correspond to P- y) (x) (i.e., the maximum value if both scores equal 1, and 0 if both scores equal 0). For all remaining (where y1 (z) * 92(z)), we consider all assignments of f from [P]. This way, if yı (x) # y2(z)) on M samples, the hypothesis class y for f consists pM hypotheses.
We enumerate different values for the on and og weights in the loss aggregation objective from a cartesian product [5] x [5), and for each pair of values, we exhaustively enumerate all and calculate: the loss aggregation objective ExelK] ag AUC(f: yk) and both of the per scoring function objectives AUC(f: y1) and AUC(f:W y2). We then do the same for label aggregation and label product objectives.
In the end, we plot the maximizers of loss and label aggregation in Figure 5, and confirm the following characterizations of the optimal solutions:
(a) УïP consists of all assignments of scores from (0. 1, to the disagreeing examples (they can disagree in any way, and only need be smaller than 3).
(b) ii consists only a single assignment to f to the disagreeing examples such that: f for examples with yı (x)
U2 (z) is and otherwise it 2.
(c) Vi consists of only a single assignment to f to the disagreeing examples such that: f for examples with yı (x))
y/ (x) is and otherwise it is 1.
(d) V A consists of all assignments to f to the disagreeing examples such that any relation is satisfied between the two sets of disagreeing examples. This case is equivalent to LA.
G.2. Details on AUC optimization
The indicator function in the AUC definition (1) makes non non-differenniable, and thus, direct AUC optimization is challenging. To mitigate this, previous works propose relaxation of the indicator function with different surrogate functions, including the hinge loss function, the logistic loss function and other choices (Sun et al., 2023; Tang al., 2022). Thus, for a surrogate function é arrive the following formulation:
AUC = -Ex- Bx- -
27

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
1.00
LA
AUC(f; relevance
LS 01 02
LS a1 <0² LP
0.98
0.96
0.90
0.95 AUC(f: clicks)
1.00
Figure 5. AUC metrics for Bayes-optimal solutions according to different objectives. We confirm the following relations among the per-objective optimal solutions sets: VioA,> fioA, Vi.a fip and Vi.oA C VioA,= VisA C Vi... Notice the Pareto front given by linear function spanned by the solutions corresponding to VioA. and Vi.AA,
Objective x(3)
r(2)
x(2)
0.7
7(2)
r/2)
AUC(s))
0.53
0.44
0.52
0.56
0.50
AUC(2) 0.49
0.46
0.50
0.54
0.45
AUCLaa 0.06
0.04
0.08
0.07
0.07
AUC(L.)
0.13
0.09
0.11
0.10
Table 6. [AUC(y)) - AUC(y=) on the synthetic dataset from MLP model training. Each column value .........9)) corresponds to the marginal probability for the second label, (gy 1), while the marginal probability for the first label is fixed, P 1) 0.5. We find label aggregation yields the lowest difference between per-label AUC metrics. Here, AUC AUC + ya) and AUC(1.) AUC(2)) AUC(yz).
In our work, unless otherwise stated, we assume a logistic surrogate function Φ
G.3. Details on synthetic training experiments
We draw uniform two-dimensional random vectors W1, W2 over [-1, 1J² and calculate label distributions using sigmoid linear model, with (xx) = aa wi z) and (x) = a(T w z), where (12) I+exp(-s) is the sigmoid function. We then sample labels yn (x) and y2(x) uniformly from the distributions (7 (x) and 17 (x)
We train a 3-layer MLP model with hidden dimension 256 and ReLU activation over 8K examples for 50 epochs. We evaluate on held out 2K examples.
G.4. Additional results
For completeness, in Figure 6 we report metrics for per-signal AUC corresponding to results Figure 2.
G.S. Additional synthetic experiments
We generate instances x E R2² from uniform distribution over 1|2 We next draw uniform random vectors J41 /2,, Ja,, 44 over [0, 1)2 controlling the skewness label distributions (x) and (x)) (see Appendix G.3 details of the data generation process). Depending on the sampled values, we end up with different marginal skewness of the distributions. We fix the marginal (1) 0.5 and vary (2) to control the effect label skewness on the performance of different techniques. We train multi-layer perceptron model with varying level of skewness for the second label, while keeping the first label balanced. We report the results in Table 6. We find that the difference between the per-label AUC is the smallest for label aggregation when the distribution for the second label is imbalanced. Thus, label aggregation better balances between the two objectives, whereas loss aggregation tends to favor one over the other.
28

---

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation
1.00
1.00
1.00
Objective
Objective
Objective
Label Agg
Label Agg
Label
Loss Agg
Loss Agg
Loss Agg
0.98
Clicks AUC
0.98
Clicks AUC
0.98
0.97
0.97
0.97
Clicks
0.95
0.95
0.95
0.94
0.94
0.94
0.2
0.4
0.0
0,2
0.4
0.0
n(2)
n
/f
10
T-
25
T- 50
1.00
1.00
1.00
Objective Label Agg
0.98
0.98
Relevance AUC
Agg
Relevance AUC
AUC
0.96
0.96
0.96
0.94
0.94
0.94
Objective
Objective
Agg
Label Agg
Loss Agg
Loss Agg
0.2
0.0
0.2 n!
0.4
0.2
0.4
nPI
n(
Figure 6. Plots of AUC(; (1)) (i.... clicks) and AUC(-; (2)) (i.e., relevance) for optimal scorers function of skewness in label ((2) corresponding to to results in Figure 2. We compare label aggregation and loss aggregation on a synthetic dataset. We fix 0.5 and vary - P(Y 1). The sigmoid scaling parameter controls how close the label distribution
(1) (I to a deterministic distribution (the larger r, the closer it is to deterministic distribution). We find loss aggregation to lead to higher difference between per-label AUC metrics.
29


Reviews:
[{"review_id": "y6iYs7oISS", "reviewer": "Reviewer_PfnK", "summary": "This paper investigates the problem of bipartite ranking with multiple binary labels, comparing two approaches: loss aggregation and label aggregation. The authors provide a theoretical analysis of the Bayes-optimal solutions for both methods and empirically validate their findings. Extensive experiments have been conducted.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and insightful questions.  We address the specific points you raised below.\n\n**1. Anti-correlated Labels:**\n> \"test label aggregation … with ‌anti-correlated labels‌\"\n\nThank you for this insightful question. We show below that the optimal scorer *does* depend on the correlation between the labels; for the special case of anti-correlated labels, we get no useful signals, resulting in a constant scorer.  \n\nSpecifically, Proposition 5.4 shows the optimal scorer for label aggregation (cost $c_{\\overline{y}\\overline{y}^{\\prime}} = |\\overline{y} - \\overline{y}^{\\prime}|$) ranks by $f^*(x) \\propto \\sum_k \\eta^{(k)}(x)$. For $K=2$, this is equivalent to ranking by $\\delta(x) = p(Y_1=1, Y_2=1 | x) - p(Y_1=0, Y_2=0 | x)$. The derivation below shows $f^*(x) \\propto \\delta(x)$.\n\n(Derivation: From Prop 5.4, the scorer is $\\eta_1(x)+\\eta_2(x)$. We have $\\eta_1(x) = p(Y_1=1, Y_2=0 | x) + p(Y_1=1, Y_2=1 | x)$ and $\\eta_2(x) = p(Y_1=0, Y_2=1 | x) + p(Y_1=1, Y_2=1 | x)$. Summing them gives $\\eta_1(x) + \\eta_2(x) = p(Y_1=1, Y_2=0 | x) + p(Y_1=0, Y_2=1 | x) + 2 p(Y_1=1, Y_2=1 | x)$. Since $p(Y_1=1, Y_2=0 | x) + p(Y_1=0, Y_2=1 | x) + p(Y_1=1, Y_2=1 | x) + p(Y_1=0, Y_2=0 | x) = 1$, the sum simplifies to $1 - p(Y_1=0, Y_2=0 | x) + p(Y_1=1, Y_2=1 | x) = 1 + \\delta(x)$.)\n\nThus the optimal scorer depends on label correlations via $\\delta(x)$. Let's consider the implications:\n* **Overlapping ($Y_1=Y_2$):** $\\delta(x) \\propto \\eta_1(x)$, so the ranking uses $\\eta_1(x)$, which is sensible. \n* **Anti-correlated ($Y_1 = 1-Y_2$):** $\\delta(x) = 0$. The scorer $f^*(x)$ is constant, yielding no ranking. This is unsurprising  as the aggregated label $Y_1+Y_2=1$ is constant, making the AUC objective ill-defined.\n* **Mild anti-correlation:** Here, both $p(Y_1=1, Y_2=1 | x)$ and $p(Y_1=0, Y_2=0 | x)$ would be small, and the ranking depends on their difference via $\\delta(x)$. For example, when $\\delta(x) > 0$, it is more likely that both labels are 1 than 0, resulting in $x$ being ranked higher. \n\n**2. Sensitivity of Label Aggregation to Weights:**\n> \"How‌ sensitive are the results to … ‌mixing weights‌ in label aggregation?\"\n\nThis is a great question! Below, we generalize label aggregation with non-uniform weights $\\alpha_1, \\alpha_2 > 0$, i.e., $\\bar{Y} = \\alpha_1 \\cdot Y_1 + \\alpha_2 \\cdot Y_2$, again for the $K=2$ case for simplicity.\n\nFrom Proposition 5.4, the Bayes-optimal scorer $\\bar{\\eta}(x) = E[\\bar{Y}|X=x]$ becomes:\n$\\bar{\\eta}(x) = 0 \\cdot p(Y_1=0, Y_2=0 | x) + \\alpha_1 \\cdot p(Y_1=1, Y_2=0 | x) + \\alpha_2 \\cdot p(Y_1=0, Y_2=1 | x) + (\\alpha_1+\\alpha_2) \\cdot p(Y_1=1, Y_2=1 | x)$\n$ = \\alpha_1 \\cdot [ p(Y_1=1, Y_2=0 | x) + p(Y_1=1, Y_2=1 | x) ] + \\alpha_2 \\cdot [ p(Y_1=0, Y_2=1 | x) + p(Y_1=1, Y_2=1 | x) ] = \\alpha_1 \\eta_1(x) + \\alpha_2 \\eta_2(x)$\n\nThis shows that the optimal scorer is a direct linear combination of the class-probability functions $\\eta_k(x)$, weighted by the *explicitly chosen* aggregation weights $\\alpha_k$.\n\nThis contrasts sharply with the optimal scorer for loss aggregation (Proposition 5.2), which is $\\sum_k \\frac{a_k}{\\pi^{(k)}(1-\\pi^{(k)})} \\eta^{(k)}(x)$. Here, the effective weight on $\\eta^{(k)}(x)$ depends not only on the chosen weight $a_k$ but also implicitly on the label prior $\\pi^{(k)}$.\n\nTherefore, regarding sensitivity:\n* The **label aggregation** optimal scorer is sensitive to the choice of weights $\\alpha_k$ in a **direct and predictable** way: the final scorer is exactly the $\\alpha_k$-weighted sum of the $\\eta_k(x)$. It is notably **insensitive to the class priors $\\pi^{(k)}$**.\n* The **loss aggregation** optimal scorer is sensitive to both the chosen weights $a_k$ and the **class priors $\\pi^{(k)}$** through the $\\pi^{(k)}(1-\\pi^{(k)})$ term.\n\n**3. Deterministic Label Assumption:**\n> \"Theorem 1‌ assumes deterministic labels .However, most labels in real-world are noisy.\"\n\nThank you for pointing this out. We searched our manuscript but could not find \"Theorem 1\". We kindly ask for clarification on which result is being referred to.\n\nAssuming the concern relates to our use of deterministic labels in Section 6 (where $\\eta^{(k)}(x) \\in \\{0, 1\\}$): this was purely for **illustrative purposes**, to provide a clear and simple setting to demonstrate the \"label dictatorship\" phenomenon associated with loss aggregation (Proposition 6.1, Figure 1).\n\nOur main theoretical results on Bayes-optimal scorers in Prop 5.2 (Loss Agg.) and  Prop 5.4 (Label Agg.) do **not** require deterministic labels: they hold for general $\\eta^{(k)}(x)$.\n\nFurthermore, our Section 7 experiments use both synthetic dataset (generated from a non-deterministic distribution) and real-world datasets (Banking, MSLR), confirming relevance in non-deterministic settings.", "claims_and_evidence": "NA", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "Key theoretical results (Theorems 1–3 in the main text and Appendices A–B) are provided. Theorem 1‌ (Bayes-optimality of loss aggregation) assumes deterministic labels (Equation 3) .However, most labels in real-world are noisy. Theorem 3‌ (Label aggregation avoids dictatorship) is compelling but relies on the Pareto-optimality definition.", "experimental_designs_or_analyses": "The impact of label correlations (e.g., overlapping vs. orthogonal labels) on aggregation methods is not studied.", "relation_to_broader_scientific_literature": "The field of Multi-objective optimization might be beneficial", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n1.The motivation is clear\n2.Extensive theoretical analysis has been conducted.\n\nWeaknesses:\n1. Could you test label aggregation on a dataset with ‌anti-correlated labels‌ (e.g., one label’s positives are another’s negatives) to assess robustness\n2.How sensitive are the results to the choice of ‌mixing weights‌ (e.g., uniform vs. task-specific) in label aggregation?", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "ZRsYr1NljX", "reviewer": "Reviewer_aFZ3", "summary": "The paper formulates a new problem, where each instance is associated with multiple labels and the goal is to find a ranking for these labels. To deal with this problem, the paper derives the Bayes-optimal solvers for two commonly used loss functions loss aggregation and label aggregation and proves pareto-optimality of these two methods. The effectiveness of the proposed methods are validated by empirical studies.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and insightful questions.  We address the specific points you raised below.\n\n**1. Regarding Theory Guiding Design:**\n> \"...nor does it explain how the theoretical results guide the design of the method.\"\n> \"How can the theoretical results guide the design of the method?\"\n\nThank you for this important question on the practical implications of our theory. As opposed to informing methods from theory, we follow a different structure in our paper, where we start with an established goal of Pareto-optimality, describe two methods for achieving that goal (i.e., label aggregation and linear scalarization), and using the Bayes optimality framework analyze whether they achieve it. Indeed the theoretical results do not serve a purpose of constructing methods, but rather, they allow us to analyze the proposed methods.\n\nThat being said, our analysis does lead to practical conclusions. First, we introduce a novel criterion eluding Pareto optimality, the “dictatorial issue”, which a practitioner may want to keep in mind. Second, as demonstrated with our experiments on both synthetic and real world experiments, one should be careful when choosing linear scalarization, as it suffers from the dictatorial issue, contrary to label aggregation techniques. \n\n**2. Regarding Application Scenarios:**\n> \"The paper does not provide a detailed discussion of the application scenarios of the method...\"\n\nWe appreciate this point and agree that a more elaborate discussion of application scenarios would strengthen the paper. The applications of multi-objective learning to rank are widespread. We briefly mentioned potential areas like information retrieval and medical diagnosis in the Introduction and used a motivating example from information retrieval (relevance vs. engagement trade-off) in Section 3.3. To further elaborate, in the revised manuscript, we will add a dedicated subsection to discuss potential real-world applications in greater detail. This will include more concrete examples, such as:\n\n* **Multi-faceted Information Retrieval:** Ranking documents based on relevance to different query interpretations or aspects (e.g., topicality, freshness, geographical relevance). [R1]\n* **Recommendation Systems:** Recommending items (e.g., products, movies, news articles) by balancing multiple objectives like predicted user click/purchase probability, relevance to long-term interests, promotion of diversity, or fairness considerations across item groups. [R2]\n* **Computational Advertising:** Ranking ads based on predicted click-through rate and predicted conversion rate. [R3]\n\nFor each scenario, we will briefly discuss why synthesizing multiple labels is necessary and how the choice between loss aggregation and label aggregation (informed by our analysis of Pareto optimality and the \"dictatorship\" issue) might impact the final ranking outcome. We believe this expanded discussion will better illustrate the practical relevance and potential impact of our work.\n\n[R1] Perkio, Jukka, et al. \"Multi-faceted information retrieval system for large scale email archives.\" The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05). IEEE, 2005.\n\n[R2] Zheng, Yong, and David Xuejun Wang. \"A survey of recommender systems with multi-objective optimization.\" Neurocomputing 474 (2022): 141-153.\n\n[R3] Wang, Xuewei, et al. \"Towards the Better Ranking Consistency: A Multi-task Learning Framework for Early Stage Ads Ranking.\" AdKDD (2023).", "claims_and_evidence": "Most claims in the paper are supported by the theoretical proof or empirical results.", "methods_and_evaluation_criteria": "The paper focused on the AUC metric, which is commonly used in ranking problems. From theoretical and empirical perspectives, the paper show positive results for the proposed method.", "theoretical_claims": "I do not focus on this topic. It is difficult for me to check the correctness of proofs.", "experimental_designs_or_analyses": "The paper mainly performs experiments on a toy dataset and two realistic datasets. Although it focused on the theoretical properties of two loss functions, it is suggested to perform experiments on much more datasets from diverse domians.", "relation_to_broader_scientific_literature": "The paper focus on a general problem, ranking, which is relevant to multiple research communities.", "essential_references_not_discussed": "The relevant works are fully discussed in the paper.", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper provides rigorous theoretical results for their claims.\n\nWeakness:\n\nThe paper does not provide a detailed discussion of the application scenarios of the method, nor does it explain how the theoretical results guide the design of the method.\n\nAlthough this is a rather theoretical work, the results presented in the paper are still insufficient. The paper should conduct experiments on more datasets.", "other_comments_or_suggestions": "The font in the figure is suggested to be adjusted to match the text in the main body.", "questions_for_authors": "How can the theoretical results guide the design of the method?", "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": "pOskwa7AhX", "reviewer": "Reviewer_T6u6", "summary": "The paper studies the bipartite ranking problem in a multi-label setting, comparing two approaches: one based on loss aggregation and the other on label aggregation. It shows that loss aggregation can result in label dictatorship.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and insightful questions. We clarify below:\n\n**1. Regarding Interpretation of Prop 6.1 / Loss Aggregation Weighting & Practical Example:**\n> Re: Prop 6.1 & loss weighting. Why problematic if $\\pi^{(k)}\\approx 0.5$? Isn't less weight on noisy labels reasonable? Clarify problematic nature & provide practical example where dictatorship undesirable.\n\nWe clarify that $\\pi^{(k)}$ represents the overall **balance or prevalence** of label $k$ across the dataset, *not* the conditional uncertainty or noise $P(Y^{(k)}=1|x)$ for a specific instance $x$. A label can be perfectly balanced ($\\pi^{(k)}=0.5$) while being conditionally deterministic (zero noise). For example, with instances $x_1, x_2$ where $\\eta^{(1)}(x_1)=1, \\eta^{(1)}(x_2)=0$, we have $\\pi^{(1)}=0.5$ (balanced marginal) but zero conditional label noise.\n\nTherefore, the loss aggregation weighting $1/[\\pi^{(k)}(1-\\pi^{(k)})]$ favors *marginal imbalance (skewness)*, not necessarily conditional signal quality. Our concern is that this skew-based weighting may conflict with practical goals.\n\n**Illustrative Example:** IR Example: Assume Y(1)='relevance' is balanced ($\\pi^{(1)} \\approx 0.5$) and Y(2)='is recent' is highly skewed ($\\pi^{(2)} \\approx 0$). Even if both relevance and recency signals are perfectly clean (conditionally deterministic, $\\eta^{(k)}(x) \\in \\{0,1\\}$), loss aggregation with uniform $a_k=1$ yields $\\alpha^{(2)} \\gg \\alpha^{(1)}$, making 'is recent' dominate the ranking (Prop 6.1). If the user cares primarily about relevance, but the system heavily prioritizes recency regardless of relevance due to skew, this \"dictatorship\" is undesirable. The system optimizes for marginal imbalance, ignoring the balanced relevance signal.\n\nThis issue persists even with non-deterministic labels (Prop 5.2), where the optimal scorer remains sensitive to the marginal priors $\\pi^{(k)}$. Our experiments (Section 7) on data with varying skewness provide empirical support.\n\n**Action:** We will revise Section 5.1 and Section 6.1 to clearly distinguish marginal imbalance ($\\pi^{(k)}$) from conditional label distributions ($\\eta^{(k)}(x)$). We will incorporate an illustrative example and refine the IR explanation to clarify why favoring labels based on marginal skew $\\pi^{(k)}$ can be practically undesirable.\n\n**2. Regarding Understanding Label Aggregation by Summation (Prop 5.3/5.4):**\n> Re: Prop 5.3/5.4. Difficulty understanding label summation $\\sum_k Y^{(k)}$. Are $Y^{(k)}$ binary? The sum is not {0,1}. How does this compare to multi-class label addition (e.g., \"cat\" + \"dog\")?\n\nThank you for requesting clarification.\n* **Setup:** As introduced in Section 3.1, our setting involves $K$ distinct **binary** labels $Y^{(1)}, \\ldots, Y^{(K)}$ for input $x$, where $Y^{(k)} \\in \\{0, 1\\}$. These represent different facets or signals (e.g., clicks vs. ratings mentioned in Sec 1, 3.3). We aim to learn a single scorer $f : \\mathcal{X} \\rightarrow \\mathbb{R}$.\n* **Summation:** In Section 4.2 (specifically for Prop 5.3 and 5.4), we use the aggregation $\\psi(Y^{(1)}, \\ldots, Y^{(K)}) = \\sum_{k=1}^K Y^{(k)}$. Since each $Y^{(k)}$ is binary, the sum $\\bar{Y}$ is an integer in $\\{0, 1, \\ldots, K\\}$, representing the *count* of positive labels.\n* **Resulting Label:** You are correct, this sum $\\bar{Y}$ is generally **not binary** (it is ordinal).\n* **Handling the Sum:** This is handled by treating the task as **multipartite ranking** with respect to this ordinal label $\\bar{Y}$. We optimize the multipartite AUC defined in Definition 2.3 / Eq. 5 using $\\bar{Y}$.\n* **Role of Costs (Crucial):** Prop 5.4's key insight relies on using specific costs $c_{\\overline{y}\\overline{y}^{\\prime}} = \\mathbf{1}(\\overline{y} > \\overline{y}^{\\prime}) \\cdot |\\overline{y} - \\overline{y}^{\\prime}|$ within the multipartite AUC objective (Eq. 5). Under *this specific cost structure*, the Bayes-optimal scorer simplifies remarkably to $f^*(x) \\propto \\sum_{k=1}^K \\eta^{(k)}(x)$ (Eq. 7). As shown in the proof, this occurs because $E[\\bar{Y} | X=x] = \\sum_k E[Y^{(k)}|X=x] = \\sum_k \\eta^{(k)}(x)$, and these specific costs make $E[\\bar{Y}|X=x]$ the optimal scorer (per Uematsu & Lee, 2015). This simplification does not generally hold for other costs (like $c_{\\overline{y}\\overline{y}^{\\prime}} = 1$ used for Prop 5.3).\n* **Distinction from Multi-Class:** This is fundamentally different from having mutually exclusive multi-class labels (like \"cat\", \"dog\"). We are summing *binary indicators* related to the *same instance*, not arithmetically combining distinct semantic categories.\n\n**Action:** We will add text clarifying that $Y^{(k)}$ are binary, $\\bar{Y}=\\sum_k Y^{(k)}$ serves as an intermediate ordinal target for multipartite ranking, and emphasize the critical role of the specific cost function $c_{\\overline{y}\\overline{y}^{\\prime}} = |\\overline{y} - \\overline{y}^{\\prime}|$ in deriving the clean result of Prop 5.4.\n\nPlease let us know if any further clarification is needed.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked proofs of Propositions 6.1, 5.2, and 5.4.", "experimental_designs_or_analyses": "Yes. I did not find any issues in the experimental designs.", "relation_to_broader_scientific_literature": "The paper advances a line of work on learning with multiple labels.", "essential_references_not_discussed": "I am not aware of any.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "In line 251-260, the authors state that `Practically, this suggests that the choice of the mixing weights $a_k$ determines the extent to which the optimal scorer favors one label over the others. More precisely, the optimal scorer \\textit{favors labels that are skewed} ( $ \\pi^{(k)}$ is away from 0.5 ), over labels that are balanced ( $ \\pi^{(k)} \\approx 0.5$ ). As we shall see in \\S6.1, this can lead to undesirable behaviour for the loss aggregation objective, unless one commits to a very specific choice of mixing weights $a_k$. This is unexpected: one might naturally assume that a uniform weighting ($a_k = 1$) would induce scorers that treat all labels equitably.\"\n\nI am not sure I agree with the authors' assessment here. The term $\\pi^{(k)}(1-\\pi^{(k)})$ is the variance of the label distribution for category $k$. This means that the Bayes-optimal classifier aggregates individual Bayes-optimal classifiers by weighting them inversely to their variances. Since the framework is Bayesian, I would expect the prior probabilities to carry meaningful information. If $\\pi^{(k)} \\approx 0.5$, then the label is almost entirely noise and contains little to no useful signal. In such a case, is it not reasonable for the Bayes-optimal scorer to put less weight on $Y^{(k)}$?\n\n\nGiven this, I would like the authors to clarify why the implication of Proposition 6.1 is considered problematic. In the scenario where class probabilities are either $0$ or $1$ and $\\alpha^{(1)} > \\alpha^{(2)}$, the emergence of a dictatorial label seems natural. Do you have a practical example where such a scenario occurs, but a dictatorial label is undesirable? Perhaps you could construct an example within your running framework of information retrieval, demonstrating a case that mathematically aligns with Proposition 6.1 (with deterministic labels), where ideally, we would not want a dictatorial label to emerge, yet it does.  \n\n\n\n\n\n\n\nI am having difficulty understanding Proposition 5.3, Proposition 5.4, and the surrounding discussion. What does it mean to aggregate labels by summing them, i.e., $\\sum_{k} Y^{(k)}$? Are the individual labels $Y^{(k)}$ binary? If so, their sum may no longer belong to $\\{0,1\\}$. On the other hand, if the labels are multiclass, how does summation apply in this case? For example, what does adding the labels “cat” and “dog” yield?", "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: The authors study the problem of bipartite rankings with multiple labels, focusing on two well-known approaches to this problem -- loss aggregation and label aggregation. Specifically, they formalize this problem, show that the Bayes-optimal solutions to AUC maximization are Pareto optimal, and that loss aggregation can lead to label dictatorships (an undesirable outcome). They empirically validate these findings on synthetic (data generated from a transformation from a uniform distribution of instances in R^2) and real-world datasets (UCI Banking [mortgage and personal loan] and MSLR Web30k [click and relevance]). 

Strengths of this work identified by reviewers include:
- While learning bipartite rankings with multiple labels has been defined and applied in practice, this is the first work that characterizes the properties of existing formulations and establishes theoretical justification for choosing one formulation over another.
- The stated claims are rigorously (analytically) supported and reflected in empirical results.

Limitations of this work identified by the reviewers include:
- Reviewer PfnK initiated some discussion regarding relationships between the labels. While this is relatively straightforward for people working in this space, the discussion in the rebuttal is potentially elucidating to potential users of this method.
- The primary concern is limited experiments. The synthetic experiments behave as expected and the two 'real-world' datasets only have two output variables. I believe this is sufficient, but secondary experiments (e.g., sensitivity analyses) would strengthen the work. Minimally, I would recommend discussing specifics regarding the range of utility of this setting (as addressed in rebuttal for reviewer aFZ3).

In any case, this is a general formulation for an important problem with useful results. The paper is well-motivated, well-constructed, well-supported, and well-written. The experiments could be improved to better demonstrate the importance of the problem, but this is a very clean paper providing potentially important results.
Decision: Accept (poster)