ComRank: Ranking Loss for Multi-Label Complementary Label Learning
Authors: Jing-Yi Zhu
Yi Gao
Miao Xu
Min-Ling Zhang
Venue: NeurIPS 2025 poster ()
Keywords: multi-label learning
complementary label leaning
weakly supervised learning
Primary area: general_machine_learning

Abstract: Multi-label complementary label learning (MLCLL) is a weakly supervised paradigm that addresses multi-label learning (MLL) tasks using complementary labels (i.e., irrelevant labels) instead of relevant labels. Existing methods typically adopt an unbiased risk estimator (URE) under the assumption that complementary labels follow a uniform distribution. However, this assumption fails in real-world scenarios due to instance-specific annotation biases, making URE-based methods ineffective under such conditions. Furthermore, existing methods underutilize label correlations inherent in MLL. To address these limitations, we propose ComRank, a ranking loss framework for MLCLL, which encourages complementary labels to be ranked lower than non-complementary ones, thereby modeling pairwise label relationships. Theoretically, our surrogate loss ensures Bayes consistency under both uniform and biased cases. Experiments demonstrate the effectiveness of our method in MLCLL tasks. The code is available at https://github.com/JellyJamZhu/ComRank.

ComRank: Ranking Loss for Multi-Label Complementary Label Learning
Jing-Yi Zhu Yi Gaol.2, Miao Xu², Min-Ling Zhang 1.2
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China 2 Key Laboratory of Computer Network and Information Integration (Southeast University),
Ministry of Education, China
The University of Queensland, Australia
(zhujingyi, gao gao_yi, zhangm1)@sent edu. en,
{miao xuu@uq. edu.
Abstract
Multi-label complementary label learning (MLCLL) is a weakly supervised paradigm that addresses multi-label learning (MLL) tasks using complementary labels (i.e., irrelevant labels) instead of relevant labels. Existing methods typically adopt unbiased risk estimator (URE) under the assumption that complemen- tary labels follow a uniform distribution. However, this assumption fails in real- world scenarios due to instance-specific annotation biases, making URE-based methods ineffective under such conditions. Furthermore, existing methods un- derutilize label correlations inherent in MIL. To address these limitations, propose ComRank, Rank, a ranking loss framework for MI.CLI, which encourages complementary labels be ranked lower than non-complementary ones, thereby modeling pairwise label relationships. Theoretically, our surrogate loss ensures Bayes consistency under both uniform and biased cases. Experiments demon- strate the effectiveness of our method in MLCLL tasks. The code is available at https//ggttauu.ooomm//////z////n
Introduction
Multi-label learning (MLL) refers to a task where an instance is associated with multiple relevant labels, which has broad applications in real-world scenarios (Zhang and Zhou, 2014 Tang al. 2023, Kou et al. 2024). However, accurately labeling a large number of instances with all their true labels incurs high labor costs. To address this issue, weakly supervised learning for MLL has gained widespread attention in recent years, including semi-supervised multi-label learning [Liu et al. 2006
Niu al. 2019), multi-label learning with missing labels (Sun al. 2010 Wu al. 2014 and
partial multi labei learning (PML) (Xie and Huang 2018 Zhang and Fang 2020].
Multi-labe label complementary label learning (MLCLL) has recently emerged weakly supervised
learning paradigm, which enables algorithms to learn from complementary labels instead of rele-
vant labels to address the MIL problem. In MICLL, each training instance is associated with complementary label rather than relevant labels, where the complementary label specifies a label that the instance does not belong to. One application for MLCLL privacy preservation, such as in sensitive surveys where respondents may hesitate to provide all truthful answers. By only asking them to exclude certain options, data collection becomes easier and more privacy-friendly while also reducing labeling costs.
"Corresoonding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The conventional solution for MLCLL currently revolves around the unbiased risk estimator (URE), which is a powerful tool in weakly supervised learning that enables the accurate estimation of true classification risk. Specifically, these methods derive URE by assuming that complementary labels follow uniform distribution, where a URE can be constructed based on common MILL loss functions such as binary cross-entropy loss (BCE), mean squared error loss (MSE), and mean absolute error loss (MAE). With the above uniform assumption, Gao et al. [023] firstly investigate the MLCLL problem and derive a URE. Moreover, they propose a gradient-frienlly MLCLL loss to enhance gradient updating of the URE. However, this uniform assumption may fail in real-world scenarios, where annotators may provide complementary labels with biases influenced by the characteristics of the instances. Moreover, previous URE-based methods do not fully exploit label correlations, which critical in MLL.
In MI.CIL, based on the fact that complementary labels are known to be irrelevant, while non- complementary labels may include relevant ones, it is generally desirable for the predicted probabili- ties of complementary labels to rank lower than those of non-complementary labels. This intuition naturally aligns with the objective of ranking loss. Inspired by this observation, we propose com- plementary ranking loss (called ComRank) framework for MLCLL, which encourages learning by enforcing this ranking constraint and capturing pairwise relationships between labels. Additionally, our framework uses an exponential loss as the surrogate loss, while the complementary ranking loss achieves Bayes consistency under both cases of uniform and biased complementary labels. This overcomes the limitation of the URE, which only has theoretical guarantees under uniform complementary labels. Furthermore, information from the rankings, offering unique advantages in MLL.. Outstanding experimental results demonstrate the effectiveness of our method. The main contributions of this paper are as follows:
proposed framework can directly capture label correlation
We theoretically analyze why existing URE-based methods cannot work well on comple- mentary labels with biased distribution. URE strongly depends on the uniform assumption of complementary labels, and fails to estimate the expected risk when the complementary label distribution shifts.
We firstly introduce ranking loss into MLCLL and propose complementary ranking loss framework, ComRank, for MICLL. We theoretically prove that it possesses Bayes consistency under both uniform and biased complementary labels. Experiments on different complementary label distributions demonstrate the outstanding performance of our method.
The remainder of this paper is organized as follows: Section 2 summarizes the related work, and preliminaries are introduced section 3 Discussion on URE with different complementary label distribution are provided in section 4 Section section introduue ComRank and its experimental results. The last section concludes our work.
2 Related Work
Multi-label learning. MLL is a classification task where each instance can be related to multiple
labels simultaneously (Tia et al. 2023 Shi et al. 2024). Considering label correlations during training.
there has been extensive theoretical exploration of ranking in MLL. Gao and Zhou [201]] first
defined the consistency of MLL and Li et al. (2117) introduced the concept of Bayes consistency
into the context of ranking loss for MLL, proposing surrogate loss proven to be consistent from the perspective of the Bayes prediction rule. Xie and Huang (0088) shows that probabilistic MLL, ranking between positive and negative labels can help disambiguate false positives. [L et al. (2024) illustrates that missing labels can be assumed to rank between positive and negative labels in weakly supervised MLL settings. However, these studies ranking loss are all focused supervised scenarios and are not applicable to the MLCLL problem.
Complementary label learning (CLL). CLL was first proposed to solve the multi-class classification tasks, which aims to train multi-class classifier using complementary labels. Ishida et al. 2017] initially derived a URE by modifying mairiis-cooppaiionn and one nee-veruu--all losses for CLL under the assumption of uniform complementary label distribution. To get rid of trapping in specific losses,
Ishida et al. 2019) extended a general URE framework that can accommodate arbitrary losses. Recognizing that the uniform assumption for generating complementary labels may fail handle the real-world scenarios, various methods that diverge from uniform assumption have also been
2

---

investigated, such as Yu et al. transition matrix, and Gao and Zhang 202T] developed discriminative model without the uniform assumption. The success of these methods is based on the multi-class scenarios, but they may not be suitable for the MI.LLI problem.
20188 relaxed CLL to biased complementary labels by estimating a
Multi-label complementary label learning. MLCLL was first introduced by Gao et al. [023 as a solution to the challenge of collecting and accurately annotating multi-label data. Under the uniform assumption (i.e., randomly sampled from irrelevant labels), Gao et al. [2023] derived a URE, which ensures the classifier learned through complementary labels converges to the optimal classifier in MLL. Furthermore, in later research, Gao et al. (2024) allowed the use of biased complementary labels to recover relevant labels through an estimated transition matrix, and Gao al. [2025] further investigated the URE in the setting of multiple complementary labels. Unfortunately, these methods fail to consider the biased complementary label distribution, or do not provide theoretical guarantees to derive a URE under biased distribution.
Therefore, in this paper, we demonstrate why URE-based methods cannot remain unbiased across non-uniform complementary label distributions, making it impossible for these methods to accurately estimate the true classification risk in MLL. Furthermore, we propose novel complementary ranking loss framework, ComRank, for MLCLL, which offers theoretical guarantees under both uniform and biased complementary label distributions.
3 Preliminaries
In MLL, X' C Rd and y S (0. 13. represent the d-dimensional feature space and the label space
with K labels, respectively. A multi-label sample can represented as (az Y) E X x),, where æ and
Y follow the probability distribution p(rr, Y). Let the training set be D { Y:) 1 < i < N). Here, Y can be written as a K K-diimessional vector y [v' yy. ..... ". E {0, jKK where y² = indicates that the label k is related to æ. The objective of MLL to train a multi-label classitier
X + R² by minimizing the following expected risk R(g)), where I& E [0, 1] is the predicted
probability for the k-th element and denotes the common MLL loss:
g" = arg min R(g) = arg min E Ep(a, v) [C(g(2)), Y)] gEG
(1)
gEG
In MLCLL, we define the complementary training set as δ = {(x; TT) 1 < N), where
y: {>/ Y.J. To ensure the validity of Dr. Y; cannot be 0 or V, so | = =2 2 2. and follow a distribution p(æ, 1). For convenience, ÿ can be represented as K-dimensional vector y = [ gz² ........7 Ix E {0, 1)",, where o² = indicates that the label l: is the complementary label of æ. MLCLL aims train multi-label classification classifier g : X + R² which can predict relevant labels for unseen instances. Let C represent the MLCLL loss, and the optimal classifier g is obtained by minimizing the expected risk of MLCLL:
g' = arg min R(g) = arg min Ep(a.9) [E(g(z).0) gEG
(2)
gEG
Before commencing the analysis, we first present the definitions of URE, URE is an important tool for weakly supervised method [Ishida et al. 2019 Feng et al. 2020), providing an accurate estimation of the true risk R(g). i... R(g) = R(gg) Therefore, R(g) is referred as a URE of R(g).
4 Complementary Label Distribution
Existing URE-based methods in MLCLL recover relevant labels and construct corresponding clas- sifiers from complementary labels by making reasonable assumptions about the distribution of complementary labels. As a result, the complementary label distribution plays a crucial role in the modeling process. However, current assumption and theorem have certain limitations. Therefore, systematic discussion and reasonable extension of them will be conducted in this section. We start from the uniform assumption and the existing URE derived from it.
Assumption 4.1. [Ishida et al. 2017
Gao et al. 2023 Uniform Distribution Assumption:
if k & Y,, if E Y,
plk = g|z,)
YTT
(3)
0,
3

---

provides information that complementary labels are uniformly selected from the label space excluding relevant labels. This implies that each irrelevant label has an equal probability of heing chosen as complementary label by annotators. Based on this distribution, the contribution of p(1;, Y) to p(a. y) also uniform. As a result, a URE can be easily derived according to Assumption 4.1 which is shown as follows.
Assumption 4.1
Gao et al. 2023) URE under the uniform distribution: With p(k = u)ae) defined in Assumption 4. and Rgg) defined in Eq. 4 the equality R(g)) = (g) holds, where
Theorem 4.2.
(g) = Ep(xr.)
1
E ((g.8) VER.AY
(4)
2k-1-1
However, in the real world, a uniform distribution may hardly cover actual scenarios. Some label combinations may be more likely to occur than others. Labels with a higher correlation to the relevant labels are closer to relevant labels and less likely to be chosen as complementary labels (Gao et al. 2024). For example, when the relevant label is water, annotators are more likely to choose deserl (a low co-occurrence label) rather than lake (a high co-occurrence label) the complementary label. At the same time, lake is more likely to be closer to the relevant label compared to desert.
Therefore, we extend complementary labels from a uniform distribution to biased distribution. Let > K represents the correlation matrix, where L has | 2 rows, with each row corresponding to a label set Y E y. The element ly represents the correlation between the label set Y and the k-th label. The closer Y is to the k-th label, the larger lyx is. Note that is used only for inference and does not appear in later computations.
matrix L |
Assumption 4.3. Biased Distribution Assumption:
TyE 0,
if Y
p(k: ō ÿ
(5)
if
where = Ex 2 Tyz
lyk p(k E Y|a)).
Assumption summarizes the condition probabilities of biased complementary label distribution. Here, in Eq. (5) is the normalization factor, ensuring that p(k ğ x forms a valid probability distribution. The correlation ly k in Eq. (5) is proportional to p(k e: Y [z), meaning the correlation between label & and set Y is proportional to the conditional probability that label k belongs to set Y. given x.
Besides, the design of previous work is generally based on Label-Dependee Assumption, that is: The complementary label ÿ is independent of the features conditioned on the relevant label set Y. i.e., Y) > p(g ke, Y) [Ishida et al. 2017 7 2019 Gao et al. 2023]. This assumption does not adequately encompass real-world scenarios, as annotators subconsciously select labels that not too similar based on the instance's 's features, rather than the relevant labels, in the process of choosing complementary labels. Therefore, we adopt a more realistic Instance-dependent Assumption. which
has been widely used in other weakly supervised scenarios [Xia et al. 2020 Chen et al. 2021 Kou
al. 2023].
Assumption 4.4. Instance-Dependeer Assumption: Given an instance æ, the complementary label is independent of Y, i.c. x Y)= = =(]]x))
Assumption 4.4 is fundamental premise regarding the relationship between complementary labels and instances, positing that the selection of a complementary label depends on the instance. In some scenarios-sur such as image containing multiple mmimals-annotar relevant categories based solely on features. However, our assumption is motivated by the observation that annotators often eliminate obviously irrelevant labels by inspecting the input instance (e.g.. excluding "building" from an image showing animals), without needing to infer the full set of relevant labels. This behavior supports modeling conditionally independent of Y given We adopt this assumption as a tractable approximation that reflects limited annotator under biased complementary label distributions.
may struggle to exclude all
Subsequently, we investigate the URE under the Biased Distribution Assumption. To simplify the computation, we first express the probability distribution in Assumption 4.4 in matrix form as bias

---

-2)X Here, lyx: = =p(k z) represents the probability of label & being selected as the complementary label when the relevant label set for at is Y. Theorem 4.5 then provides the URF derived from the biased complementary labels.
transition matrix, denoted by == [| -
Theorem 4.5. URE under biased distribution: Given p(k - 7) and R(g), the equality Rig)
R(g) Rg) holds when
Rg(g) Bpp(a,))
Σ
(6)
YCV.TYY
where lyg belongs to the matrix L [TTx and L is the Moore-Peer Poorr-Penrooee pseudoinverse of L
The proof stated in Appendix B Compared to the URE under uniform distribution, the construction of URE (Eq. (6)) under biased distribution is heavily dependent on the specific characteristics of the distribution. The uniform assumption ensures that each complementary label contributes equally to the distribution of the relevant labels. However, once there is bias in the contributions, p(z, 9) is no longer uniform, which inevitably causes the URE to change. Therefore, the URE derived under the uniform assumption complementary labels changes. In other words, it becomes ineffective under the biased assumption.
longer accurately estimate the expected risk once the distribution of
The Proposed Framework
5.1 Complementary Ranking Loss
In addition to the lack of universality across different distributions, URE-based methods not take label correlations into account, thus losing important information needed to solve the MLL problem. Since complementary labels are known to be irrelevant, while con-complementtry labels may include relevant ones, enforcing lower scores for complementary labels may help distinguish likely-relevant labels. This intuitive motivation naturally aligns with the goal of ranking loss, making suitable choice for integration into MLCLL. By incorporating label correlations without significantly increasing computational complexity, ranking loss has proven to be an effective tool for capturing pairwise label correlations [Zhang and Fang 2020 Zhang et al. 2018 Fürnkranz al. 2008). In MLL, the traditional ranking loss is defined as
((g(x),
Σ
Σ
[[gx(z) (x)]]
Acm S.IY j=1.jøY
where I(() is the indicator function, which outputs 1 when the condition holds and otherwise 0. Inspired by the complementary 0-1 loss (Chou et al. 2020), we propose the complementary ranking loss for MLCLL:
E(g(x).)) =
(g)( (z()))
k=1,A
Unlike URE-based methods, the complementary ranking loss does not rely on any assumption regarding complementary labels. Instead, complementary ranking loss directly compares the predicted probabilities between different labels. Similar to ranking loss in supervised MLL., it penalizes cases where the complementary label predicted probability is higher than that of non-complementary label, because a complementary label is certainly not a relevant label, while a non-complementary label may be either relevant irrelevant. Therefore, it is generally reasonable to assign lower scores to complementary labels, as they are less likely to be relevant compared to non-complementary labels. The rationale behind this design will be formally justified in the next subsection.
However, directly optimizing the complementary ranking loss is challenging, as is typically NP- hard due to its non-convexity and discontinuity. Thus, convex surrogate loss can be introduced to facilitate more efficient optimization, a common method in ranking loss methods:
C(g(x),))
Σ
((gg(x) 9u (x))),
k=
5

---

Algorithm ComRank Algorithm
Input:
D: the complementary-label training set ((x,, Ft))
0: the initial parameters of classifier g
T: the number epochs
A: external stochastic optimization algorithm
Output:
g: learned multi-label classifier
Training Routine
1: for 6= -= 1 to T do
2: Let L be the risk,
3:
C -= - (Z ū:))
4:
Set gradients - VV
5:
Update 0 by A with VoL
6: end for
where represents the surrogate loss. In this paper, we propose a complementary ranking loss framework named ComRank, using exponential function as the surrogate loss, shown follows. The algorithm of applying ComRank can referred from Algorithm
(CR(g(x).9)
Σ
explgs (x)) - 9u (z)).
1=1.
5.2 Bayes Consistency for ComRank
Bayes consistency is a desirable property of a loss function, ensuring that minimizing the expected loss leads the Bayes prediction rule (Li et al., 2017 Cheng et al. 2010). We say that loss has Bayes consistency if it leads to follow the Bayes prediction rule:
g = p(k E Y Y(æ)).
In contrast, URE only guarantees that the expected risk of MLCLL aligns with that of fully supervised MLL, without directly evaluating the classification results. Therefore, Bayes consistency a more rigorous criterion than URE.
To verify the rationality of ComRank, it's necessary demonstrate ComRank's ss theoretical soundness by establishing Bayes consistency. The analysis begins with the following lemma.
Lemma 5.1. Under (cR(g(x),)) v). g" g (x) if and only if ø|æ) plj 5)x).
The proof can be found in Appendix The conclusion of Lemma 5.1 is achieved through risk minimization, which a fundamental result that applies to all distributional scenarios of MLCLL. Moreover, this reflects the relationship between the predictive probabilities given by (g ()) Ø) and the probability of becoming complementary label. With Lemma 5.1 we can demonstrate that LCn (g( (x),)) 7) exhibits Bayes consistency under both the uniform distribution (Assumption 4.1 and the biased distribution (Assumption 4.3
Theorem 5.2. Bayes Consistency for ComRank: For both uniform and biased complementary label distribations, (xx) 2 g' (a:) holds under LCR (z)) if and only if p(k E Y|=) 2 p(j E Y\a)).
The proof is stated in Appendix D Theorem 5.2
shows that ComRank establishes a theoretical connection whereby the ranking between complementary and non-complementary labels can be transferred to the ranking between irrelevant and relevant labels. Next, we will provide experimental results to support its performance.

---

Table 1: Average Precision (mean=istd) on the training data with uniform complementary labels, The best performance of each dataset is shown in boldface, where indicates that smaller/larger values of metrics are better performance.
Methods
L-UW
CCMN
PMLMD
PARD
MAE
GDF
R.(g)
ComRank
39611.016
.5811.019
441::.03
74011.00
432.1.019
.7591.012
.734.:0114
.78011.010
yeast
6854.018
6461.001
.9542.023
6084.118
.9811.018
.7122.019
.6791.016
.7151.019
caron
.3552.037
.3374.042
5374.092
4444.035
4271.047
.6222.067
.1112.088
.6342.008
rovl-s]
.45.1.020
.094.028
.348:1030
4681.089
4271.029
.7111.057
.363:1019
.4911.118
bibtex
2371.009
.594..025
280::.044
.471.022
28711009
.6142.017
.4131.016
.6581.014
bookmark
550=2.009
.3974.028
.181
.5494.010
.5062.007
.619-006
.5124.007
.6281.005
nuswideBoW
4511.010
A311.014
.55
4571.057
46611011
.5531.008
.595.1.008
.58510010
Table 2: Summary of pairwise t-test for ComRank against other comparing approaches at 0.05 significance level on uniform datasets, showing form of Win/Tie/Loss.
ComRank against
L-UW
CCMN
PMLMD
PARD
MAE
GDF
(g(g)
in total
One Error
5/2/0
5/2/0
6/1/0
5/2/0
5/2/0
4/3/0
6/1/0
36/13/0
Coverage
6/1/0
7/0/0
5/2/0
6/1/0
6/1/0
4/3/0
6/1/0
40/9/0
Ranking Loss
6/1/0
7/0/0
6/1/0
6/1/0
6/1/0
4/3/0
6/1/0
41/8/0
Average Precision
6/1/0
6/1/0
6/1/0
6/1/0
5/2/0
4/3/0
6/0/1
39/9/1
in total
23/5/0
25/3/0
23/5/0
23/5/0
22/6/0
16/12/0
24/0/1
156/40/0
Experiments
6.1 Experimental Setup
Datasets. To fully verify the effectiveness of ComRank, we select seven multi-label datasets for experiments The range of their data sizes is from 1702 to 269648, and data domains include text, biology, and images. Their details can be referred from Appendix We unify data preprocessing on these datasets. To comprehensively illustrate the experimental impact of the single complementary label, line with previous studies [Gao et al. 2023 2024 [Hang and Zhang 2024]. for datasets with label space larger than 50, extract the 15 most frequently occurring labels and delete instances that did not appear with these labels.
Data Processing. We use uniform and biased complementary labels to conduct experiments. Specifi- cally, 1) Uniform complementary labels: Each instance æ; is equipped with complementary label randomly selected from {>' -Y,), where irrelevant labels have an equal probability of being cho- sen; 2) Blased complementary labels: The selection of the complementary label for æ; follows biased rule: based co-occurrence rates computed from the original dataset, labels with lower co-occurrence rates are more likely to be selected. The model is trained on data annotated with complementary labels, while the test data is labeled with relevant labels.
Baselines. ComRank is compared with seven recent competitive methods, including one CLL method: L-UW; one MLL method: CCMN; two PML methods: PMLMD and PARD; and three MLCLL methods: MAE, GDF and R. which are shown the following details:
L-UW [ao and Zhang 2021 A CLL method that incorporates a weighted loss based on empirical risk to enhance the prediction gap between potential relevant labels and complementary labels.
CCMN [Xie and Huang 2023 A MLL method that leverages class-conditional multi-label noise for learning, constructing unbiased estimators.
PMLMD [Xie et al. 2021]: A PML method in the form of ranking loss, specially equipped with weight and meta seeta-disamiiuattonn to figure out candidate labels in partial multi-label learning label sets.
Publicly available at
wwwp:aastttttmtmmhitie hlm.
7

---

Table 3: Average Precision (mean=std)) on the training data with biased complementary labels. The best performance of each dataset is shown in boldface, where indicates that smaller/larger values of metrics are better performance.
Methods
L-UW
CCMN
PMLMD
PARD
MAE
GDF
R.(g)
ComRank
391.1.021
4611.020
445:1.032
.6911.021
424.1.018
.7291.020
.716:1.026
.7511.015
yeast
6911.018
.6501.032
77224.025
.6111.099
.7031.018
.7142.019
.6911.014
.7171.019
caron
.33:2.038
.3522.052
.5114.065
A324.055
4391.050
.6102.078
.115t.041
.6262.080
rovl-s]
.50.1.029
38642.028
.3411.034
.8851.098
42241.022
.5214.021
A13:1.044
.542.1.099
bibtex
2344:.011
2682.031
.3294.104
.4461.017
2851.000
.2771.019
.4142.018
.6651.021
bookmark
5525+.012
.3894.024
.180#1005
.5574.009
.5182.088
.299..006
.5174.013
.6472.000
nuswideBoW
4391.011
.022.0088
.55.1.023
49611.014
4541.012
.5561.012
.5941.008
,89110000
Table 4: Summary of pairwise t-test for ComRank against other comparing approaches at 0.05 significance level on biased datasets, showing in form of Win/Tie/Loss.
ComRank against
L-UW
CCMN
PMLMD
PARD
MAE
GDF
Ru(g)
in total
One Error
6/1/0
6/1/0
6/1/0
5/2/0
6/1/0
4/3/0
5/2/0
38/1 1/0
Coverage
6/1/0
7/0/0
5/2/0
7/0/0
7/0/0
4/3/0
7/0/0
43/6/0
Ranking Loss
6/1/0
7/0/0
5/2/0
7/0/0
7/0/0
1/6/0
7/0/0
40/9/0
Average Precision
7/0/0
7/0/0
5/2/0
6/1/0
6/1/0
4/3/0
6/1/0
41/8/0
in total
25/3/0
27/1/0
21/7/0
25/3/0
26/2/0
13/14/0
25/3/0
162/34/0
PARD [Hang and Zhang
A PML method based probabilistic graphical model, designed to infer potential ground-truu label information by modeling the generation process of partial multi-label data.
2024
MAE Gao
al. 2023]
A MLCLL method that leverages MAE loss within the URE
framework for learning.
GDF Gao et al.
2023 A MLCLL method that utilizes gradient descent-friendly loss
based on URE
R. (g) |ao et al. 2023]: ; The MLCLL loss function derived from R., (g) in Eq. the URE based on uniform complementary labels.
Evaluation Metrics. We evaluate performance using four common MLL metries: Ranking Loss, Coverage, One Error and Average Precision. Their details can be referred from Zhang and Zhou [2014]. Notably, the metric of Ranking Loss evaluates the fraction of reversely ordered label pairs, le.., an irrelevant label is ranked higher than relevant label, which different from our method.
Implementation Details. Our experiments are conducted using PyTorch [Paszke et al. 2019] and NVIDIA TITAN RTX. To ensure fair comparisons, linear model applied implement For statistical analysis, we employ ten-fold cross-validation, where the dataset is to all datasets. randomly divided into ten subsets. The results
reported the mean and standard deviation (std) of the metric. The weight decay was set to le 3, and the learning rate was selected from {le 3, le 2, le 1}. It multiplied by 0.1 when the iteration count reaches 100 and 150 [Wang et al. 2021]. The training epochs for all datasets are 200. These settings were kept consistent across all methods.
6.2 Comparison on Uniform Complementary Labels
To evaluate the effectiveness of our method under uniform complementary label situation, we use uniform complementary-latee labeled data to train.
Results. Table reports the results for Average Precision, while the results for Coverage, One Error, and Runking Losy are provided in Ta Appendix due to space limitations. As shown, ComRank achieves significant improvements across all datasets. Among the 42 dataset-metric combinations, ComRank achieves the best performance in 39 cases. The most notable improvement occurs on the bibtex dataset, where Average Precision increases from 0.237 (under the L-UW method)

---

16
0
Geelark
10
10%
Pyach
(a) bibtex (uniform)
(b) scene (uniform)
(c) bibtex (biased)
(d) scene (biased)
Figure I: Average Precision on datasets with uniform or biased complementary labels. Dark lines show the mean of testing results, where light shadows correspond to the std.
Table 5: The running time (in 102 seconds) of methods with multiple uniform complementary labels.
Dataset
#Label Classes
CCMN
L-UW
GDF
MAE
Ra (g)
ComRank
enron
53
2.94
3.22
3.79
3.72
3.14
3.15
rcvl-sl
101
4.13
3.67
4.12
3.56
3.76
3.64
bibtex
159
5.11
3.76
4.07
3.69
3.89
3,91
bookmark
208
33.25
17.11
17.18
18.68
17.23
17.19
avg
11.36
6.94
7.29
7.41
7.01
6.97
to 0.658, clearly demonstrating ComRank's strong learning capability. Additionally, compared to CLL methods, ComRank reduces the One Error from 0.73 to 0.308 the enron dataset, highlighting its adaptability to MIL. in the complementary label setting.
Statistical Tests. Table 2 presents the pairwise t-test results of ComRank against seven methods at a 0.05 significance level across four metrics. For each pairwise comparison, we use the t-test to determine statistical significance. If ComRank significantly outperforms the baseline, we add I to the win count; if ComRank is significantly worse, we add to the loss count; otherwise, we add to the tie count. The final results are reported in the format of win/tie/loss. ComRank consistently outperforms the baselines statistically, achieving 23/5/0 against L-UW, 25/3/0 against CCMN, and showing similar strong performance against other methods. Particularly, ComRank demonstrates dominance in metrics One Error, Coverage and Ranking Loss, where achieves no losses across almost all baselines. These results highlight the effectiveness of ComRank.
Convergence Analysis on the Uniform Distribution. [igure[[showe the epoch situation of Average Precision for compared methods and ComRank in bibtex and scene datasets, and similar tendency also shows on other datasets. Remaining metrics are Figure of Appendix As shown in the figure, ComRank demonstrates the best performance among all methods, exhibiting the fastest and most substantial improvement in Average Precision. Notably, GDF, (g), and CCMN show slight instability, with oscillations emerging midway toward the end of training. In contrast, ComRank maintains high stability throughout the optimization process, highlighting its effectiveness in gradient descent when complementary labels selected uniformly.
6.3 Comparison on Biased Complementary Labels
To assess the effectiveness of our method under biased distribution, we train from biased complementtry-labblle data generated by the co-occurrence rates of relevant labels.
Results. Table 3 shows the results of Average Precision, while Coverage, One Error and Ranking Loss results are in Table of of Appendix due to page limitation. Similar the uniform setting, ComRank demonstrates significant improvements across all datasets. Out of the seven datasets, it achieves the best performance across all metries on five. Among them, on the scene dataset, One Error is reduced dramatically from 0.852 (under L-UW) to 0.402. Compared to these methods, especially URE-based methods such as R,, and GDF, ComRank continues to show superior performance by reducing Coverage on scene from 0.422 (under Ra(g)) to O. 130, and improving Average Precision on bibtex from 0.614 (under GDF) to 0.658. These results clearly demonstrate ComRank's 's advantage in handling biased complementary label scenarios.

---

Table 6: Comparison of Frobenius norm distances for label correlation preservation.
Datasets
CCMN
L-UW
GDF
MAE
(g(
ComRank
scene
6,44
6.38
1.83
6.42
1.36
1.82
yeast
4.45
4.68
5.79
5.92
3.70
6.34
enron
14.92
12.88
14.33
14.84
3.33
3.65
revl-s1
12.42
15.06
11.32
15.04
3.20
4.95
bibtex
15.18
14.98
13.69
15.22
1.80
2.71
bookmark
13.38
15.09
11.38
15.09
1.27
11.26
nuswideBoW
14.52
14.45
9.22
14.58
4.93
8.96
Statistical Tests. Table 4 displays the pairwise t-test results of ComRank compared to various baselines on biased datasets. In particular, ComRank demonstrates superiority for all metrics with no losses in all cases. It is worth noting that, ComRank achieves near-perfect performance compared with (g) (25/3/0), underscoring its adaptability across datasets and biased complementary label scenarios.
Convergence Analysis on the Biased Distribution. Figure shows the epoch situation of Average Precision for compared methods and ComRank various datasets. Figures of Coverage, Ranking Loss and One Error are Figure of Apendix G Also, curve of ComRank shows the best performance among all methods, and remains highly stable, demonstrating its effectiveness in the gradient descent process, especially for biased complementary labels.
6.4 Further Analysis.
Complexity Analysis. With a single complementary label per instance, the proposed ComRank method has computational complexity of O('(K' -))- Although the complexity grows with more complementary labels, our implementation avoids the high cost of pairwise comparisons by leveraging matrix operations with masking, ensuring efficiency even for large label spaces. To empirically assess scalability, we report the running time on datasets where each instance has K/ uniform complementary labels (T. ComRank achieves comparable or faster speeds than most baselines, demonstrating its scalability.
Label Correlation Preservation. We evaluate each method's ' ability to preserve label correlations by comparing the Pearson correlation matrices of the test labels and the predicted scores, under uniform complementary labels. Their difference, measured by the Frobenius norm distance (lower is better), most baselines,
reported in Table 6 ComRank achieves superior correlation preservation demonstrating that its ranking-based design effectively retains meaningful label dependencies.
Surrogate Loss Ablation. The table 10 in Appendix H reports the Average Precision from ablation study on different surrogate losses under uniform complementary labels. We compared for log loss, sigmoid loss, softmax loss and ComRank (with exponential loss). Their details can be referred to from Appendix H Comrank achieves competitive performance in most cases, validating its effectiveness and Bayes consistency.
7 Conclusion
In this paper, we theoretically analyze the limitations of URE, revealing that its reliance on distri- butional assumptions restricts its effectiveness to scenarios with uniformly selected complementary labels. Under biased complementary labels, URE struggles provide unbiased risk estimation and fails to capture inter-label relationships. To address these issues, we propose ComRank, complementary ranking loss framework that is theoretically justified under both uniform and biased complementary label settings. Our risk minimization analysis demonstrates that ComRank has Bayes consistency both cases. Experimental results further validate remarkable stability and effectiveness in learning. A current limitation of this work is that ComRank is based on multiple assumptions, including distributional assumptions and independence assumptions. the future, we hope to extend it to more general scenarios.
10

---

Acknowledgements
The authors wish to thank the anonymous reviewers for their helpful comments and suggestions. This work supported by the National Science Foundation of China (62225602, 624B2042). MX is supported by the Australian Research Council (DE2301011 166).. We thank the Big Data Center of Southeast University for providing the facility support the numerical calculations in this paper.
References
Peng-Fei Chen, Jun-Jie Ye, Guang- Yong Chen, Jing- Ling-Wei& Zhao, and Pheng-Am Heng. Beyond class-conditional assumption: A primary attempt combat instance-dependent label noise. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, volume 35, pages 11442-11450, 2021.
Wei-Wei Cheng, Eyke Hüllermeier, and Krzysztof Dembezynski. Bayes optimal multilabel classifi- cation via probabilistic classifier chains. In Proceedings of the 27th ICML International Conference on Machine Learning, pages 279-286, Haifa, Israel, 2010.
Yu- Tu-Ting Chou, Gang Niu, Hsuan-Tiee Lin, and Masashi Sugiyama. Unbiased risk estimators can mislead: A case study of learning with complementary labels. In Proceedings of the 37th ICML International Conference on Machine Learning, pages 1929-1938, Virtual Event, 2020.
Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple complementary labels. In Proceedings of the 37th ICML International Conference Machine Learning, pages 3072-3081, Virtual Event, 2020.
Johannes Fürnkranz, Byke Hüllermeier, Eneldo Loza Menefa, and Klaus Brinker. Multilabel classifi- cation via calibrated label ranking. Machine Learning, 73:133-153, 2008.
Wei Gao and Zhi-Hua Zhou. On the consistency of multi-label learning. Artificial Intelligence, 199-200:341-358 2011.
Yi Gao and Min-Ling Zhang. Discriminative complementary-labbe learning with weighted loss, In Proceedings of the 38th ICML International Conference on Machine Learning, pages 3587-3597, Virtual Event, 2021.
Yi Gao, Miao Xu, and Min-Ling Zhang. Unbiased risk estimator to multi-labeled complementary label learning. In Proceedings of the 32nd IJCAI International Joint Conference on Artificial Intelligence, pages 3732-3740, Macao, China, 2023.
Yi Gao, Miao Xu, and Min-Ling Zhang. Complementary to multiple labels: A correlation-aware correction approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12): 9179-9191, 2024.
Yi Gao, Jing- Yi Zhu, Miao Xu, and Min-Ling Zhang. Multi-label learning with multiple complemen- tary labels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(9):8013-80) 8024, 2025.
Jun-Yi Yi Hang and Min-Ling Zhang. Partial multi-label learning with probabilistic graphical disam- biguation. Proceedings of the 37th NeurIPS Annual Conference on Neural Information Processing Systems, 36:1339-11333 2024.
Takashi Ishida, Gang NIu, Wei-Hua Hu, and Masashi Sugiyama. Learning from complementary labels. In Proceedings the 30th NeurlPS Annual Conference Neural Information Processing Systems, pages 5639-5649, Long Beach, CA, 2017.
Takashi Ishida, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. Complementarry-label learning for arbitrary losses and models. In Proceedings of the 36th ICML International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 2971-2980, Long Beach, CA, 2019.
11

---

Bin-Bin Jia, Jun- Ying Liu, Jun-Yi Hang. and Min-Ling Zhang. Learning label-specific features for decomposition- multi-class classification. Frontiers of Computer Science, 17(6))176348. 2023.
Zhi-Qiang Kou, Jing Wang, Yu-Heng Jia, Biao Liu, and Xin Geng, Instance-dependent inaccurate label distribution learning. IEEE Transactions on Neural Networks and Learning Systems, 36(1): 1425-1437, 2023.
Zhi-Qiang Kou, Jing Wang, Yuheng Jia, and Xin Geng. Inaccurate label distribution learning. IEEE Transactions on Circuits and Systems for Video Technology. 34(10):10237-1022 2024.
Huan Li, Xiao Yan Zhu, Wei-Chu Zhang, and Jia- Va-Yin Wang. A ranking- problem trans- formation method for weakly supervised multi-label learning. Puttern Recognition, 153:110500 2024.
Yun-Cheng Li, Yale Song, and Jie-Bo Luo. Improving pairwise ranking for multi-label image classification. In Proceedings of the 35th CVPR Conference on Computer Vision and Pattern Recognition, pages 1837-1845, Honolulu, HI, 2017.
Yi Liu, Rong Jin, and Liu Yang. Semi-supervised multi-label learning by constrained non-negative matrix factorization. In Proceedings of the 20th AAAI Conference on Artificial Intelligence. volume 6, pages 421 421-426, Boston, USA, 2006.
Xue-Song Niu, Hu Han, Shi-Guang Shan, and Xi-Lin Chen. Multi-label co-regularization for semi- supervised facial action unit recognition. In Proceedings of the 32th NeurlPS Anmual Conference on Neural Information Processing Systems, pages 907-917, Vancouver, Canada, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Ze-Ming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Jun-Jie Bai, and Soumith Chintala. Pytorch: An imperative style, tigh-performance deep learning library. In Proceedings of the 32th NeurlPS Annual Conference on Neural Information Processing Systems, pages 8024-8035, Vancouver, Canada, 2019.
Jiang-Xin Shi, Tong Wei, and Yu-Feng Li. Residual diverse ensemble for long-tailed multi-label text classification. Science China Information Sciences, 67(11):212100 2024.
Yu-Yin Yin Sun, Yin Zhang, and Zhi-Hua Zhou. Multi-label learning with weak label. In Proceedings of the 24th AAAI Conference on Artificial Intelligence, volume 24, pages 593-598, Atlanta, USA, 2010.
Yi Tang, Yi Gao, Yong-Gang Luo, Ju-Cheng Yang, Miao Xu, and Min-Ling Zhang. Unlearning from weakly supervised learning. In Proceedings of the 32nd IJCAI International Joint Conference on Artificial Intelligence, pages 5000-5008, Macao, China, 2023.
Deng- Bao Wang, Lei Feng, and Min-Ling Zhang. Learning from complementary labels via partial- output consistency regularization. In Proceedings of the 30th IJCAI International Joint Conference on Artificial Intelligence, pages 3075-3081, Virtual Event, 2021.
Bao- Yuan Wu, Zhi-Lei Liu, Shang- Fei Wang, Bao-Gang Hu, and Qiang Ji. Multi-label learning with missing labels. In Proceedings of the 22nd ICPR International Conference on Pattern Recognition, pages 1964-19688 Stockholm, Sweden, 2014.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards -nstance-dependent label noise. Proceedings of the 33th NeurlPS Annual Conference on Neural Information Processing Systems, 33:7597-7610, 2020.
Ming-Kuu Kun Xie and Sheng-Jun Huang. Partial multi-label learning. In Proceedings of the 32th AAAI Conference on Artificial Intelligence, volume 32, page $302-4309, 2018.
Ming-Kun Kun Xie and Sheng-Jun Huang. CCMN: A general framework for learning with class- conditional lulti-label noise. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):154-166, 2023.
12

---

Ming-Kun Kun Xie, Feng Sun, and Sheng-Jun Jun Huang, Partial multi-label learning with meta disambigua- tion. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, pages 1904-1912, 2021.
Xi-Yu Yu, Tong-Liang Liu, Ming-Ming Gong, and Da-Cheng Tao. Learning with biased complemen- tary labels. Proceedings of the 15th ECCV European Conference on Computer Vision, pages 68 03-83,22 2018.
Min-Ling Zhang and Jun-Peng Fang. Partial multi-label learning via credible label elicitation. IEEE Transactions on Puttern Analysis and Machine Intelligence, 43(10):3587-3599 2020.
Min-Ling Zhang and Zhi-Hua Zhou. A review on multi-label learning algorithms. IEEE Transactions on Knowledge and Data Engineering, 26(8):181-11877, 2014.
Min-Ling Zhang, Yu-Kun Li, Xu- Ying Liu, and Xin Geng. Binary relevance for multi Mabti-labelli learning: an overview. Frontiers Computer Science, 12(2):191-202 2018.
13

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
The datasets used in this paper are public, and their download links are offered in the paper. The code for this paper will be released after the paper is accepted.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
oliicy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle pwwppppguuuiieeeeep hutpc///uuudess/deeuuuubiiis SroodeSubiissi.e ssiiiioiicccyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental Setting can be found in the section 6 Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please see section
6
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conducted in the paper conform to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please see section 1
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

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

---

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

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
20

---

Appendix
A
Details of Datasets
Table 7 describes the datasets used the experiments of this paper, where #Instance represents the number of samples, #Features represents the sample feature dimension, #Label Classes represents the label space, #Cardinality represents the average number of relevant labels of the sample, and #Domain represents the data type.
Table Characteristics of datasets.
Datasets
#Instances
#Features
#Label Classes
#Cardinality
#Domain
scene
2407
294
6
1.07
images
yeast
2417
103
14
4.23
biology
1702
1001
53
3.38
Text
revl-s1
5815
944
101
2.88
Text
bibtex
7365
1836
159
2.40
images
bookmark
87856
2150
208
1.25
Text
nuswideBoW
269648
500
81
1.87
images
B
The Proof of Theorem 4.5
Theorem 4.5 URE under biased distribution: Given p(k T)(x) and R(g), the equality R(g)
R(g) Rg(g)
holds when
(g) Ep(a,))
Σ
YCYNEY
where itg belongs to the matrix L+ = |pxix and L+ is the Moore-Penront pseudoinverse of LT.
Proof. According Assumption 4.3 and Assumption 4.4 for & Y. p(u T Therefore,
p( 7)
Σ p(z,Y,0)
Σ YCY.EEY
p(æ, Y)pūT,,
YEY
Σ
p(x, Y). lvg
2
YCU.AYY
Set L D where Tyb lyr KEY
& y By expanding p(æ, and p(æ, Y) with respect to
0,
y and as marginal probabilities, we can obtain:
p(x, 7 = 1)
p(x, Y =Yi
plz, Y 12)
p( 7 k:)
IT
p(x, Y -DDi) 8lx1
p(x, g = K)
Kx1
21

---

When L" is full rank, there exists matrix L = [7*h Iixx, which is the Moore- Peorose pseudoin verse of LT, satisfies:
p(a, y 1)
pla, Y= = -1)
p(a, Y =V2)
L+
p(a, y = =k)
ppa, Y = =Y 12|x1
pp K)
Kx1
Therefore, we can have the relationship
K p(x,Y) Y)
Σ
(.p((, g).
5=1,0
where lyg is the y-th column of the row corresponding to in L+. Accordingly, the URE under Assumption 4.3 is:
Re(g) = Epta 1) (C(g.V)
= Σ
fig. Y)p(2, d)
YgV
Σ
Cig, Y My, g)dx
ygy
/ Σ
Σ
C(g, Mr d)d
Ep(z.8)
Σ
YEN.AY
C The Proof of Lemma 5.1
Lemma 5.1 Under ECR (g(x), 8). (ar) 2 gd (m) if and only if p(k T a/)r)) S p(j 5/a:)
Proof. Let AY, = {0, 1- E RR xI where the ÿ-th position is 1, the k-th position is -1, and other positions are 0, then:
K
(ca(g(x).0)
Σ
exp(g(x)AY
=
k= 1,1
Assume t exp(g(x) ). can obtain
R(g) = Ex 8) [cR(g(x). Ø)
f / (CR(g. V) p(z, 7) dx dy
/ Σ
Een(g, 17 p(x, dr
gey
Σ
Σ
o p( 7) da
jEy k= j=
K
ΣΣ
Σ
p( 1) dx
j=
22

---

K k
Σ
au p(yl)) p(a) dx
plk + y. = x) a4 p(x) dx.
Since the minimization is performed with respect to g, and æ does not affect the minimization, g" arg mingee R(g) can be converted to
g = arg min Rg)g)
ΣΣ k=1j=1
plk + n.J = 5)(e)a
gEG
When (g) reaches g" (xx), R(g) can reach g' (a:). derivative is
Let 3r p(k: + U.J 0 0/2:), thus the first-order
OR'
K K
Σ
0g k=
And the second derivative
R
K
B AYaa 2 Ox*K.
0g²
Therefore when the first derivative is equal to 0, (g) has the minimum. Let 8R' 8g
0, we have
K
K
BrAYoa
=
k=1j=1
K
B.AY exp (g)())) = 0
K
B&AY exp (x) - (x:)
(8)
k=1
Therefore, the first-order derivative O when
p(k = U.J 0.J x) p(k + D. 2z
exp (g) g (x))
because at this moment for each dimension in Eq.
plk = D.j + 5/ Σ ==1
Σ R=1
p(k = 0.J + 5/x) 0.
Then, we have
p(h ú.J x(x)
g/ (x) log
Ak.j E E
p(k + J.j 7z)
p(k ū.j = x)
gk (x) " (x) = log p(k= x)z)
Vk.j E y.
Therefore, gh (x) > g (x) if and only
2 p(k = J. + 5)æ) holds. That is, (x) > 93 (x) if and only if p(k p( /|
holds. Then, we have
p(k
.)p(k = 5|æ))
- ø.j + x))
+ lp(k + π/2) - p(k # Ø.j )))) 5/ [n] ) pli * J.k [px) g)x)
23

---

+ p(k + ]]))p( = - -l. = g/))
2 p + ()z)p(k f/ - , = g]
p(j = b/))= p(j = g)x)
p(k - p [,0
g(z)
PP - + gga)) 2 pk 9.j glo) (1)z) - * fz))
+ Ø|z) -1
+ 5)
This means if and only plk # 0) 2 p(j + y/)>) does the inequality hold. Therefore, gz(z) 2 0)
if and only if p(k * g| 2 p(j # Ø/ holds.
D The Proof of Theorem 5.2
Theorem 5.2 Bayes Consistency for ComRank: For both uniform and biased complementary label distributions, (x) 2 g'(x)) holds under (gR(g(()) 3) if and only if p(k E Y ()) Z p(j l)x)).
Theorem 5.2 1. Under Lcu(g(z), 0). (x) 2 g² (xx if and only if p(k E Y|x) 2 p(j E Y ()), for
Assumption 4.7
Proof. According to Lemma 5.1 ge (ax) 0j (a)) if and only if p(h: = ū)a=) S p(j = ū|
Based on Assumption 4.1 whenever k E ū and j & ø. it holds that p g|a) S pli a) Additionally, when & y and j E U. p(k y|æ> 2 p(j 7/
That is, g > g7 (z) if and only if p(k -/ 2 p(j e ū z), which satisfies Bayes consistency,
Theorem 5.2 Assumption
Under Lcn(g(z), 0), (x) 2 (x) if and only if E Y|x) 2 p(j Y)) for
Proof. According to Lemma 5.1 ge (x)) > 3 (x) if and only pf = 5|z) - p(j = 7 x)) According
to Assumption 4.3 when
S p(j = / )) there are two possible cases:
1. h E Y.J $ Y: In this case, we must have p(k E Y|=) 2 p(j E Y(z).
That is. 0% 2 (x) if and only if p(k F|x) 2 p(j E Y|z),, which satisfies Bayes consistency.
2. j.j $ Y: Since p(k: = ÿl x] = lya we obtain 1yk S lys
Since z is same, we have lyk 2 lvj.
:. lyk & p(k E Y|z), we have p(k Y|æ) 2 p0j E Y [z).
That is, (x > 93 (x) if and only if p(k Y|z) 2 p(j E Y (z)) which satisfies Bayes consistency.
E Comparison on Uniform Complementary Labels
Table g shows the comparison of ComRank against multiple methods in One Error, Ranking Loss and Coverage under uniform complementary labels. As we can see, ComRank demonstrates strong performance across all methods and achieves superior results on most datasets.
F Comparison on Biased Complementary Labels
Table shows the comparison of ComRank against multiple methods in One Error, Ranking Loss and Coverage under biased complementary labels. As we can see, ComRank shows competitive results among all methods and outperforms most datasets.
24

---

Table 8: Experimental results (te) on the training data with uniform complementary labels. The best performance of each dataset is shown in boldface, where indicates that smaller/larger values of metric are better performance.
Methods
L-UW
CCMN
PMLMD
PARD
MAE
GDF
Rg(
ComRank
Coveragel
437+.022
404+-021
.388+.033
.189+.020
.12--020
.157+.016
.172+.021
.143+-0033
yeast
5565+.016
6644-.08
.509+.033
.622+.066
.548=007
.5344.015
.5694.021
.520+10019
enron
.633-.059
.652+.030
106
.602-0052
.589-060
.470+.049
.6024.060
.458:-051
rev1-s1
.472+-042
.537+-034
.381-003
.297+-028
.395+.014
.305+0060
bibtex
.49=.014
.634.003
.4242.104
.299=.013
.38=.016
.2182.017
.322.0188
.1952.015
bookmark
289==007
.395+.022
.69-..028
275=-007
-099-007
.10++0005
.944:.009
.199:.005
nuswideBoW
425=.010
.433.0037
.3854.036
001
-09=.010
.334.011
.3094.012
.2881.011
Ranking Loss
scene
.5234-021
466
467-1.048
.172-.033 033
488-0023
.153+.009
.175:.011
.136:-001
yeast
245=:013
.24+:0022
.221=.018
.355=.115
.211=014
.219t.014
.50+::015
.215::013
.38++028
.811+0034
.262+003
.300-081
.387-034
.231+0029
.395+0024
.221+.029
revl-sl
.27220032
3444.044
4474.044
.299
.30=-030
.2752.058
.3992.017
.267:.081
bibtex
491+-009
.79+-0031
160+..102
280==003
.26=.009
.20++.013
.388:.014
.180:-0012
bookmark
2802.007
3682.032
.6111.024
269-000
206
.1621.005
280.1.088
.1871.007
nuswideBoW
2872.005
.40
.2744.026
317=.094
275=0005
.06
.19:2.006
.1222.006
One Frmol
scene
.81120017
.58+.0035
.7924.057
411=.021
803=.024
.384..020
418+.022
.352+.014
yeast
252+-024
261++035
270++0038
.324 +
251--023
229++002
277++0017
2499-025
enron
.723:.060
.7812.058
5394.116
-888-004
.647=.075
.3602.116
.6841.074
.308:-114
revi-sl
.708#.024
.78+
.750+t002
.624=.144
.702-003
.652+.085
.7774.031
.609-.1144
bibtex
915-.010
8941.024
8811.033
.7202.025
.811-015
.8011.033
.7441.018
.4181.021
bookmark
611=.011
.745+.040
92741.016
550=-011
.600=001
483+.0088
.08:2.007
474
miswideBoW
.44---019
.110=0040
.690+.066
.630=.044
.629-0033
.540+.023
488+-001
.500+:024
Table 9: Experimental results (mean on the training data with biased complementary labels. The best performance of each dataset is shown in boldface, where / indicates that smaller/larger values of metric are better performance.
Methods
L-UW
CCMN
PMLMD
PARD
MAE
GDF
Ra(g)
ComRank
Coveragel
scene
450=.018
402+.019
405+.0039
.160=.028
.22=.020
.144#.008
.162+.009
.130=-0110
yeast
.575+.018
668++.055
.14+-0029
.712+0081
.557=0019
.540+.021
.582+.025
.530+-019
enron
.6342.059
.6811.036
.4941.040
.5872.067
.600=.062
.4672.060
.6034.060
.4561.058
revi-sl
348:.049
.425#.038
.524:.049
.397-0047
334=-042
.354+.050
.411:008
.350:..06
bibtex
4972.012
4851.026
163
300-.011
437=-012
.2301.015
3274.017
.2061.0144
bookmark
2992.007
3811.029
6554:.02
289
307
2194.006
300:1.088
.210:1008
nuswideBoW
4042.011
.499..020
.3841.037
155
.391-0011
.133.0011
.3071.012
.2981.011
Ranking Loss)
scene
506++.025
.466+.025
.447+0399
-008 022
476=.024
.171+.016
.188+.024
.154:.014
yeast
2402:011
2981.000
.2161.026
2774
228=0011
.182.0111
2411:011
212:1.011
enron
439=-029
.52+.004
250++0055
386--039
337=-034
.233+.029
396+.030
.221--024
rovl-sl
2711:018
3834.033
.5241.036
321-.103
305=-027
.2234.035
.3331.026
.23011070
bibtex
4932.012
A55+.033
.234.1155
.788-0111
.27=-013
.1942.015
.30310016
.1701.013
bookmark
270-1007
3861.025
.6771.028
2552.007
207
.8611.005
2741.009
.175..005
BuswideBoW
3094.005
.634.000
.2741.024
.2562.010
203
208110066
200-1.006
.1931.006
One Emort]
scene
8822..06
7494..03
8074.052
4822.031
820=.018
.435..030
4474.036
402-i.024
yeast
254=:024
254
2674.003
293 127
222-0025
253+:0024
265:t.025
225
enron
.727+.058
.74++-073
1493+.108
.632+.104 104
-627-0079
131++.16
.669+-068
.344-1144
rovi-sl
.6932.032
.744..000
.7374.085
5682.125
.716-0053
.6111.038
72441.068
.5611.150
bibtex
917=-011
886+:033
8114.126
7177-004
.873-014
.61+.005
7474.019
.414
bookmark
58921006
.7554.040
926:1.013
5462.111
582-.011
.69410088
.6041.016
.448:1009
muwwideBoW
.6492.018
.7192.058
.6681.055
.008-0066
.636-0021
.5374.027
.4001.017
.4961.023
25

---

Gne
053
035
1-1W
0.00
CCMN
043
080
0.
ConRank
625
(30
412
25
20
100
125
150
175
300
130
150
275
38
035
306
Epoadss
Epochs
Epocha
(a) Coverage on bibtex
(b) Coverage on seene
(c) Ranking Loss on bibtex
0.40
4.00
010g
Epochs
Epochs
Epochs
(d) Ronking Loss on
(c) One Error bibtex
(f) One Error scene
Figure 2: Coverage, Ranking Loss and One Error on various datasets with uniform complementary labels.
0.50
080
1-UW
055
0.2
CCMN
045
042
04-
CouRaak
6.0
025
0.2
0.37
0
25
20
150
135
150
125
330
0.3
130
120
3
20C
Epochss
Epochs
Epochs
(a) Coverage on bibtex
(b) Coverage on scene
(c) Ranking Loss on bibtex
0.32
0.0
Buslang
020
415
Epache
Epoche
Epocha
(d) Ronking Loss on (e) One Error bibtex
(1) One Error
Figure 3: Coverage, Ranking Loss and One Error on various datasets with biased complementary labels. Dark lines show the mean of testing results, where light shadows correspond the std.
G Figure
Figure 2 and Figure illustrate the epoch-wise trends of Coverage, Ranking Loss and One Error for CCMN, L-UW, GDF, (g). and ComRank, for both uniform complementary labels and biased complementary labels. As observed, ComRank consistently outperforms other methods, displaying the most rapid and least pronounced decline in Coverage, One Error and Ranking Loss. Notably, GDF, R., (g), and CCMN exhibit slight instability, with fluctuations emerging either at the initial stages or towards the end of the descent. In contrast, ComRank maintains remarkable stability, underscoring its effectiveness the gradient descent process whenever complementary labels are selected uniformly or biasedly.
26

---

H
Surrogate Loss Ablation.
The Table reports the Average Precision from an ablation study on different surrogate losses under uniform complementary labels. The surrogate losses include:
Log loss: L(g(z), 0) = Ek= log (1 + (g (x) (x(x)))
Sigmoid loss: (x) v) -k=1A (g (z) (r()) Since the predicted probability g in MLL already produced through an output sigmoid function to keep g in [0.1], we directly use the difference between values.
Softmax loss: C(g(z), E
sof fmma (z) Here, go refers to (g (x) 9k
1,bg -k= the version of where the output function is changed from sigmoid to softmax.
Our method achieves competitive performance in most cases, validating its effectiveness and Bayes consistency.
Table 10: Average Precision of different surrogate losses with uniform complementary labels.
Surrogate loss
Log
Sigmoid
Softmax
ComRank
scene
0.419
0.687
0.677
0.785
yeast
0.712
0.732
0.720
0.729
enron
0.547
0.591
0.567
0.627
r-vl-s1
0.263
0.475
0.280
0.605
bibtex
0,453
0.649
0.450
0.677
bookmark
0.197
0.629
0.586
0.618
nuswideBoW
0,485
0.490
0.488
0.583
27


Reviews:
[{"review_id": "NpRCJaAUFB", "reviewer": "Reviewer_eDzB", "summary": "The paper addresses multi-label complementary label learning. It identifies limitations in existing methods relying on unbiased risk estimators, which assume uniform distribution of complementary labels—an assumption often violated in real-world scenarios with annotation biases, and these methods also underutilize label correlations.To tackle this, the paper proposes ComRank, a ranking loss framework that encourages complementary labels to be ranked lower than non-complementary ones, capturing pairwise label relationships.\nExperiments show ComRank outperforms existing methods on various datasets with both uniform and biased complementary labels. Its contributions include: analyzing why URE-based methods fail under biased distributions; introducing ranking loss to MLCLL via ComRank, which has theoretical guarantees under both uniform and biased cases and shows strong experimental performance.", "questions": "(1)Is there an error in defining a sample of Cartesian product used in MLL in the Preliminaries of Part 3? According to the definition in the text, it is a single label sample. Is it more accurate to define Y={1,2,..., K} as Y ∈ {0,1} ^ K .\n(2)The paper claims ComRank “directly captures label correlation information from rankings”, but this mechanism is not explicitly validated. Maybe you clarify it by Comparing ComRank’s performance on datasets with strong vs. weak label correlations. If correlation strength correlates with ComRank’s improvement over baselines, it would validate the claim.", "limitations": "The paper only mentions that ComRank is restricted to the single complementary label setting, with extending to multiple complementary labels noted as future work. It fails to discuss other critical limitations, such as the sensitivity to the choice of surrogate loss (the paper uses an exponential function without exploring alternatives like logistic loss) and scalability issues with large label spaces, where the pairwise comparisons in the loss function could lead to high computational costs.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n(1) Strong theoretical foundation: Comprehensively analyzes URE limitations and proves Bayes consistency of ComRank under both uniform and biased complementary label distributions.\n(2) Advances MLCLL: Introduces ranking loss to model label correlations, filling gaps in URE-based methods.\n(3) Rigorous experiments: Uses diverse datasets with uniform/biased labels, outperforming baselines across metrics like Average Precision and Ranking Loss.\nWeaknesses\n(1) Lacks computational complexity analysis, critical for scaling to large datasets.\n(2) Neglect label sparsity effects: Multi-label data often has sparse labels, but the paper doesn't test ComRank under varying sparsity. With extreme sparsity, few non-complementary labels may undermine its ranking logic, leaving its stability in such common real-world scenarios unproven.", "was_revised": true, "final_justification": "Given the original quality of the paper and the response experiments, this paper could be accepted.", "rebuttal": "Thank you for the time and effort you devoted to reviewing our paper. The error in Q1 will be modified in the revision. Below we provide our responses to other weaknesses and questions.\n\n**W1 & L2: Lacks computational complexity analysis, critical for scaling to large datasets. Fail to discuss scalability issues with large label spaces, where the pairwise comparisons in the loss function could lead to high computational costs.**\n\n> In this paper, each instance is assigned a single complementary label, resulting in a computational complexity of $O(n(K-1))$ for the proposed ComRank method, where $n$ and $K$ are the number of instances and classes, respectively. Indeed, the computational complexity increases with the number of complementary labels. However, our implementation can avoid high computational costs caused by pairwise comparisons in the loss function. The loss can be computed using matrix operations and masking, which makes it efficient for large label spaces. To empirically validate its efficiency, we provide the running time (in 10² seconds) across datasets with large label spaces, where each instance is associated with $K/2$ complementary labels. As shown in the table below, ComRank achieves comparable or superior speed to most baselines, indicating scalability.\n>\n> | Dataset       | #Label Classes | CCMN  | L-UW  | GDF   | MAE   | $R_u(g)$ | ComRank |\n> | ------------- | -------------- | ----- | ----- | ----- | ----- | ---------- | ------- |\n> | enron         | 53             | 2.94  | 3.22  | 3.79  | 3.72  | 3.14       | 3.15    |\n> | rcv1-s1       | 101            | 4.13  | 3.67  | 4.12  | 3.56  | 3.76       | 3.64    |\n> | bibtex        | 159            | 5.11  | 3.76  | 4.07  | 3.69  | 3.89       | 3.91    |\n> | bookmark      | 208            | 33.25 | 17.11 | 17.18 | 18.68 | 17.23      | 17.19   |\n> | **avg** | -              | 11.36 | 6.94  | 7.29  | 7.41  | 7.01       | 6.97    |\n\n**W2: Neglect label sparsity effects: Multi-label data often has sparse labels, but the paper doesn't test ComRank under varying sparsity. With extreme sparsity, few non-complementary labels may undermine its ranking logic, leaving its stability in such common real-world scenarios unproven.**\n\n> To verify the effect of ComRank on the data with sparse labels, we conduct experiments on datasets with varying label densities. In the table below, the '#Density' column represents the label density of each dataset, where smaller values indicate higher sparsity. We report the average precision of different methods, which is also shown in Table 1 of the paper. ComRank achieves the best performance in all cases, with densities ranging from 0.082 to 0.303, which indicates its stability under sparse labeling. The reason lies in the pairwise ranking design, which relies on relative comparisons between complementary and non-complementary labels, rather than absolute label counts. We will include this analysis in the revised version.\n>\n> | Dataset  | #Density | L-UW  | CCMN  | MAE   | GDF   | $R_u(g)$ | ComRank         |\n> | -------- | -------- | ----- | ----- | ----- | ----- | ---------- | --------------- |\n> | scene    | 0.179    | 0.395 | 0.458 | 0.432 | 0.759 | 0.734      | **0.780** |\n> | yeast    | 0.303    | 0.685 | 0.646 | 0.698 | 0.712 | 0.679      | **0.715** |\n> | enron    | 0.189    | 0.375 | 0.337 | 0.427 | 0.620 | 0.411      | **0.634** |\n> | rcv1-s1  | 0.111    | 0.445 | 0.409 | 0.427 | 0.471 | 0.363      | **0.491** |\n> | bibtex   | 0.082    | 0.237 | 0.259 | 0.287 | 0.614 | 0.413      | **0.658** |\n> | bookmark | 0.083    | 0.506 | 0.397 | 0.506 | 0.619 | 0.512      | **0.628** |\n\n**Q2: \"directly captures label correlation information from rankings\" is not explicitly validated. Maybe you clarify it by Comparing ComRank's performance on datasets with strong vs. weak label correlations. If correlation strength correlates with ComRank's improvement over baselines, it would validate the claim.**\n\n> We agree that comparing performance across datasets with different label correlation strengths is intuitive. However, this approach might be confounded by uncontrolled factors such as feature difficulty, sample size, and label distribution. Specifically, label correlations are inherent properties of each dataset and cannot be adjusted or isolated within the same dataset for controlled comparison. Comparing across datasets with varying correlation strengths may thus lead to unfair or misleading conclusions.\n>\n> To address this issue in a fair and interpretable way, we instead measure the ability of each method to preserve label correlations. We compute the *Pearson correlation matrix*[1], which can reflect the overall level of inter-label correlation. We compute it for (1) the test label sets and (2) their prediction scores of each method, and measure their difference using Frobenius norm distance (**lower is better**), shown in the following table. All experimental settings remain the same as the paper, i.e., training on data with uniform complementary labels. ComRank shows better correlation preservation than most baselines, indicating that the ranking-based design in ComRank still helps retain meaningful label dependencies.\n>\n> Notably, ComRank achieves the lowest Frobenius distance on the scene dataset, which aligns with its highest average precision score in Table 1 of the paper. This suggests that preserving label correlation is not only theoretically desirable but also empirically linked to better predictive performance. We will add this analysis in the revised version.\n>\n> | Dataset    | CCMN  | L-UW  | GDF   | MAE   | $R_u(g)$ | ComRank |\n> | ---------- | ----- | ----- | ----- | ----- | ---------- | ------- |\n> | scene      | 6.44  | 6.38  | 1.83  | 6.42  | 1.36       | 1.82    |\n> | yeast      | 4.45  | 4.68  | 5.79  | 5.92  | 3.70       | 6.34    |\n> | enron      | 14.92 | 12.88 | 14.33 | 14.84 | 3.33       | 3.65    |\n> | rcv1-s1    | 12.42 | 15.06 | 11.32 | 15.04 | 3.20       | 4.95    |\n> | bibtex     | 15.18 | 14.98 | 13.69 | 15.22 | 1.80       | 2.71    |\n> | bookmark   | 13.38 | 15.09 | 11.38 | 15.09 | 1.27       | 11.26   |\n> | nuswideBoW | 14.52 | 14.45 | 9.22  | 14.58 | 4.93       | 8.96    |\n\n**L1: Fail to discuss the sensitivity to the choice of surrogate loss**\n\n> In response, we conducted experiments on different surrogate losses, including\n>\n> * **Log loss**: $\\bar{\\mathcal{L}}(g( x), \\bar{y}) = \\sum_{k=1, k \\ne \\bar{y}}^{K} log\\left(1 + \\left(g_{\\bar{y}}(x) - g_k(x)\\right)\\right)$.\n> * **Sigmoid loss**: $\\bar{\\mathcal{L}}(g( x), \\bar{y}) = \\sum_{k=1, k \\ne \\bar{y}}^{K} \\left(g_{\\bar{y}}( x) - g_k( x)\\right)$. Since predicted probability $g$ in MLL is already produced through an output sigmoid function to keep $g$ in [0,1], we directly use the difference between $g$ values.\n> * **Softmax loss**: $\\bar{\\mathcal{L}}(g( x), \\bar{y}) = \\sum_{k=1, k \\ne \\bar{y}}^{K} \\left(g^{softmax}_{\\bar{y}}( x) - g^{softmax}_k( x)\\right)$. Here, $g^{softmax}$ refers to the version of $g$ where the output function is changed from sigmoid to softmax.\n>\n> The following table shows the average precision of different surrogate losses on the dataset with uniform complementary labels. Our proposed method, ComRank, achieves comparable perfomance in most cases, which also validates its effectiveness.\n>\n> | Surrogate loss | Log   | Sigmoid         | Softmax | ComRank         |\n> | -------------- | ----- | --------------- | ------- | --------------- |\n> | scene          | 0.419 | 0.687           | 0.677   | **0.785** |\n> | yeast          | 0.712 | **0.732** | 0.720   | 0.729           |\n> | enron          | 0.547 | 0.591           | 0.567   | **0.627** |\n> | rcv1-s1        | 0.263 | 0.475           | 0.280   | **0.605** |\n> | bibtex         | 0.453 | 0.649           | 0.450   | **0.677** |\n> | bookmark       | 0.197 | **0.629** | 0.586   | 0.618           |\n> | nuswideBoW     | 0.485 | 0.490           | 0.488   | **0.583** |\n\n**Reference**\n\n[1] Pearson et al., Mathematical contributions to the theory of evolution. III. Regression, heredity, and panmixia, Philosophical Transactions of the Royal Society of London. Series A, 1896."}, {"review_id": "Ghmt7OJD4V", "reviewer": "Reviewer_dbnV", "summary": "This paper proposed a ranking loss framework for Multi-label complementary label learning under both uniform and biased cases. The theoretical analysis is satisfying.", "questions": "Please see the weaknesses which need for more evidences and explanations.\n\nAdditionally, please answer the following questions:\n\n1. The author should provide more empiricial analysis to prove \"In MLCLL, based on the fact that complementary labels are known to be irrelevant, while non-complementary labels may include relevant ones, it is generally desirable for the predicted probabilities of complementary labels to rank lower than those of non-complementary labels.\"\n\n2. I hope to see more experiment results on more challenging MLL benchmark datasets, including VOC and COCO, to strengthen the empirical evaluation.\n\n3. Since the author used the exponential function as the surrogate loss, I expect to see more ablation studies about the impact of selecting different forms of surrogate loss, including log loss, sigmoid loss, and softmax loss.", "limitations": "The relationship between Theorem 4.5 (URE under biased distribution) and the proposed ComRank requires deeper explanation. The author should explicitly state the theoretical connections.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n1. The paper presents a well-organized structure with clear logical flow and professional presentation, meeting the high standards of academic writing in this field.\n2. The theoretical analysis demonstrates particular rigor, offering valuable insights into the limitations of Unbiased Risk Estimator (URE) within the MLCLL context. This contribution significantly enhances our theoretical understanding of the problem.\n3. The work introduces a novel weakly supervised multi-label learning paradigm that addresses an important gap in current research, with demonstrated practical relevance to real-world applications.\n\n**Weaknesses:**\n1. The assertion that the proposed framework can directly capture label correlation information from rankings (Lines 45-46) requires stronger empirical validation. Including results or analyses that explicitly demonstrate this capability would strengthen the paper’s validity.\n2. The relationship between Theorem 4.5 (URE under biased distribution) and the proposed ComRank requires deeper explanation. The author should explicitly state the theoretical connections.\n3. The formulation of Assumption 4.4 (instance-dependent assumption) requires further clarification to ensure rigorous theoretical grounding.", "was_revised": true, "final_justification": "This paper have provided a novel weakly supervised multi-label learning paradigm that addresses an important gap in current research, with demonstrated practical relevance to real-world applications. However, the discussion on the introduce of noise in the proposed instance-dependent setting is far from satisfactory to me. To my knowledge, the instance-dependent setting in complementary label learning is quite hard to feature, most of which will turn out to be a simple biased setting. As a result, I will keep my initial score.", "rebuttal": "Thank you for your meticulous and insightful review of our paper. Below are our responses to the weaknesses and other questions.\n\n**W1: The assertion that the proposed framework can directly capture label correlation information from rankings (Lines 45-46) requires stronger empirical validation.**\n\n> To claims this assertion, we measure the ability of each method to preserve label correlations. We choose to compute the *Pearson correlation matrix*[1], which can reflect the overall level of inter-label correlation. We compute it for (1) the test label sets and (2) their prediction scores of each method, and measure their difference using Frobenius norm distance (**lower is better**), shown in the following table. All experimental settings remain the same as in the paper, training on data with uniform complementary labels. ComRank shows better correlation preservation than most baselines, indicating that the ranking-based design in ComRank still helps retain meaningful label dependencies.\n>\n> Notably, ComRank achieves the lowest Frobenius distance on the scene dataset, which aligns with its highest average precision score in Table 1 of the paper. This suggests that preserving label correlation is not only theoretically desirable but also empirically linked to better predictive performance. We will add this analysis in the revised version.\n>\n> | Dataset    | CCMN  | L-UW  | GDF   | MAE   | $R_u(g)$ | ComRank |\n> | ---------- | ----- | ----- | ----- | ----- | ---------- | ------- |\n> | scene      | 6.44  | 6.38  | 1.83  | 6.42  | 1.36       | 1.82    |\n> | yeast      | 4.45  | 4.68  | 5.79  | 5.92  | 3.70       | 6.34    |\n> | enron      | 14.92 | 12.88 | 14.33 | 14.84 | 3.33       | 3.65    |\n> | rcv1-s1    | 12.42 | 15.06 | 11.32 | 15.04 | 3.20       | 4.95    |\n> | bibtex     | 15.18 | 14.98 | 13.69 | 15.22 | 1.80       | 2.71    |\n> | bookmark   | 13.38 | 15.09 | 11.38 | 15.09 | 1.27       | 11.26   |\n> | nuswideBoW | 14.52 | 14.45 | 9.22  | 14.58 | 4.93       | 8.96    |\n\n**W2&L: The relationship between Theorem 4.5 (URE under biased distribution) and the proposed ComRank requires deeper explanation.**\n\n> Theorem 4.5 serves as the motivation for designing ComRank. It reveals that the URE under a biased complementary label distribution is inherently different from the URE derived under the uniform distribution assumption. Since all existing URE-based methods rely on the uniform complementary label assumption, their theoretical guarantee of unbiasedness breaks down when the label distribution is biased. This significantly limits the generality and robustness of URE-based approaches in real-world applications, where biased label distributions are common.\n>\n> To avoid strong dependency on the complementary label distribution, we propose ComRank inspired by ranking-based learning. ComRank directly encourages the model to assign lower scores to complementary labels. As shown in Theorem 5.2, this approach achieves Bayes consistency under both uniform and biased distributions. We will include this analysis in the revised version.\n\n**W3: Assumption 4.4 (instance-dependent assumption) requires further clarification to ensure rigorous theoretical grounding.**\n\n> Assumption 4.4 aims to reflect the practical setting where annotators lack access to the relevant label set $Y$ when selecting complementary labels, and base their decisions solely on the observed instance $x$. This aligns with typical weakly supervised scenarios, where annotations rely on salient or dominant features rather than full label information[2,3,4]. While instances like images containing multiple objects may challenge annotators' ability to exclude all relevant labels, empirical evidence suggests that they can reliably eliminate clearly irrelevant labels (e.g., excluding “building” from an image of animals) by inspecting the instance alone. This supports modeling $\\bar{y}$ as conditionally independent of $Y$ given $x$.\n\n**Q1: Need more empiricial analysis to prove \"In MLCLL, based on the fact that complementary labels are known to be irrelevant, while non-complementary labels may include relevant ones, it is generally desirable for the predicted probabilities of complementary labels to rank lower than those of non-complementary labels.\"**\n\n> By encouraging complementary labels to rank lower than non-complementary labels, the model learns useful information, which eventually can translate into encouraging irrelevant labels to rank lower than the relevant labels. Additionally, to support our claim, we reported the metric of *ranking loss* [5] for all methods in test sets which measures **the proportion of relevant labels that are ranked lower than irrelevant labels** (smaller values indicate better performance). Notably, ComRank consistently achieves the lowest scores, which provides strong support for the hypothesis. Considering ComRank shows best performance in our paper, the above results confirm that such a ranking structure is not only intuitively desirable but also empirically realizable by well-trained models. We will include this analysis in the revised version to strengthen the empirical analysis.\n>\n> | Dataset    | L-UW  | CCMN  | PMLMD | PARD  | MAE   | GDF   | $R_u(g)$ | ComRank         |\n> | ---------- | ----- | ----- | ----- | ----- | ----- | ----- | ---------- | --------------- |\n> | scene      | 0.523 | 0.466 | 0.467 | 0.172 | 0.488 | 0.153 | 0.175      | **0.136** |\n> | yeast      | 0.245 | 0.294 | 0.221 | 0.355 | 0.231 | 0.219 | 0.250      | **0.215** |\n> | enron      | 0.438 | 0.481 | 0.262 | 0.370 | 0.387 | 0.231 | 0.395      | **0.221** |\n> | rcv1-s1    | 0.272 | 0.344 | 0.447 | 0.299 | 0.307 | 0.275 | 0.369      | **0.267** |\n> | bibtex     | 0.491 | 0.479 | 0.460 | 0.280 | 0.426 | 0.206 | 0.308      | **0.180** |\n> | bookmark   | 0.280 | 0.368 | 0.661 | 0.269 | 0.287 | 0.196 | 0.280      | **0.187** |\n> | nuswideBoW | 0.287 | 0.340 | 0.274 | 0.317 | 0.274 | 0.206 | 0.196      | **0.192** |\n\n**Q2: More experiment results on more challenging MLL benchmark datasets, including VOC and COCO, to strengthen the empirical evaluation.**\n\n> Due to time limitations, we conducted experiments on the VOC dataset with uniform complementary labels, where the results of average precision are shown below. ResNet18 is used to classify and experimental settings are the same as in the paper. The average precision of our method surpasses all baselines, demonstrating the effectiveness of ComRank. We will update it and COCO in the revised version.\n>\n> | Method | L-UW  | CCMN  | MAE   | GDF   | $R_u(g)$ | ComRank         |\n> | ------ | ----- | ----- | ----- | ----- | ---------- | --------------- |\n> | VOC    | 0.327 | 0.390 | 0.314 | 0.432 | 0.431      | **0.436** |\n\n**Q3: Ablation studies about the impact of selecting different forms of surrogate loss, including log loss, sigmoid loss, and softmax loss.**\n\n> The following table reports the average precision from an ablation study on different surrogate losses under uniform complementary labels. The surrogate losses include:\n>\n> * **Log loss**: $\\bar{\\mathcal{L}}(g( x), \\bar{y}) = \\sum_{k=1, k \\ne \\bar{y}}^{K} log\\left(1 + \\left(g_{\\bar{y}}( x) - g_k(x)\\right)\\right)$.\n> * **Sigmoid loss**: $\\bar{\\mathcal{L}}(g( x), \\bar{y}) = \\sum_{k=1, k \\ne \\bar{y}}^{K} \\left(g_{\\bar{y}}( x) - g_k( x)\\right)$. Since predicted probability $g$ in MLL is already produced through an output sigmoid function to keep $g$ in [0,1], we directly use the difference between $g$ values.\n> * **Softmax loss**: $\\bar{\\mathcal{L}}(g( x), \\bar{y}) = \\sum_{k=1, k \\ne \\bar{y}}^{K} \\left(g^{softmax}_{\\bar{y}}( x) - g^{softmax}_k( x)\\right)$. Here, $g^{softmax}$ refers to the version of $g$ where the output function is changed from sigmoid to softmax.\n>\n> Our method achieves competitive performance in most cases, validating its effectiveness and proven Bayes consistency.\n>\n> | Surrogate loss | Log   | Sigmoid         | Softmax | ComRank         |\n> | -------------- | ----- | --------------- | ------- | --------------- |\n> | scene          | 0.419 | 0.687           | 0.677   | **0.785** |\n> | yeast          | 0.712 | **0.732** | 0.720   | 0.729           |\n> | enron          | 0.547 | 0.591           | 0.567   | **0.627** |\n> | rcv1-s1        | 0.263 | 0.475           | 0.280   | **0.605** |\n> | bibtex         | 0.453 | 0.649           | 0.450   | **0.677** |\n> | bookmark       | 0.197 | **0.629** | 0.586   | 0.618           |\n> | nuswideBoW     | 0.485 | 0.490           | 0.488   | **0.583** |\n\n**References**\n\n[1] Pearson et al., Mathematical contributions to the theory of evolution. III. Regression, heredity, and panmixia, Philosophical Transactions of the Royal Society of London. Series A, 1896.\n\n[2] Xia et al., Beyond class-conditional assumption: A primary attempt to combat instance-dependent label noise, AAAI, 2021.\n\n[3] Xia et al., Part-dependent label noise: Towards instance-dependent label noise, NeurIPS, 2020.\n\n[4] Yao et al., A second-order approach to learning with instance-dependent label noise, CVPR, 2021.\n\n[5] Zhang et al., A review on multi-label learning algorithms, IEEE TKDE, 2014"}, {"review_id": "nTumRsNQcj", "reviewer": "Reviewer_ns2z", "summary": "This paper proposes a novel algorithm for multi-label complementary label learning (MLCLL), supported by solid theoretical analysis and strong empirical results.\n\nHowever, it suffers from certain conceptual inconsistencies (see Issue 1–2), incomplete consideration of related work (see Issue 3), and potential flaws in the experimental design (see Issues 4–5).\n\nOverall, although I raised a lot of issues, the merits outweigh the flaws. I suggest a weak accept.", "questions": "See above weaknesses (especially 1–5) for necessary revisions or clarifications. The overall direction is promising, but the paper would benefit from addressing the above concerns to improve its clarity, fairness, and theoretical rigor.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. Clear motivation. Due to practical concerns such as privacy protection, MLCLL is an important problem to study. This paper is among the first to point out that in real-world scenarios, complementary labels are not sampled uniformly at random, but tend to be semantically opposed to true labels.\n\n2. Strong theoretical foundation. The proposed method is proven to be Bayes-consistent, which is a desirable theoretical property.\n\n3. Extensive experiments. The paper provides a comprehensive empirical evaluation across a wide range of baselines, datasets, metrics, and ablation analyses.\n\nWeaknesses\n1. Potential contradiction in modeling assumptions. Although Assumption 4.4 (instance-dependence of complementary labels) facilitates tractable loss construction and avoids unobservable dependencies on the true label set Y, it potentially conflicts with the authors' earlier intuition that complementary labels are selected with semantic exclusion from the true labels—e.g., “desert” being chosen over “lake” when the true label is \"water\". This highlights a fundamental tension between model identifiability and the realism of annotator behavior modeling.\n\n2. Theoretical comparison with URE is insufficient. While the proposed ComRank loss is theoretically proven to be Bayes-consistent in preserving the ranking order of label posterior probabilities, it does not offer an unbiased estimation of the original classification risk E[L(g(x),Y)] as URE does under the uniform assumption. Therefore, the theoretical advantage of ComRank is conditional and context-specific, and it does not universally dominate URE in terms of consistency with classification-oriented loss functions. To summarize, the paper criticizes URE for its bias but praises ComRank for its consistency. However, consistency alone does not imply superiority. Could the authors provide analysis or evidence regarding the (lack of) unbiasedness of ComRank?\n\n3. Missing discussion on related ranking-based multi-label learning (MLL) methods.\nThe paper lacks a discussion of prior work on ranking-based approaches in MLL, which may lead to an overstatement of novelty. For example:[1] shows that in probabilistic MLL (PML), ranking between positive and negative labels can help disambiguate false positives. [2] shows that in MLML settings, missing labels can be assumed to rank between positive and negative labels. I suggest the authors add a paragraph in the related work section discussing ranking-based MLL methods.\n\nAdditionally, Section 3 (Preliminaries) is somewhat redundant. It uses two equations to explain what is essentially standard background. I recommend simplifying this section by presenting only one general MLL risk minimization formula and using a comparative table to illustrate the differences between MLL and MLCLL in terms of labels, learners, and loss definitions—along with symbol definitions.\n\n4. Unrealistic experimental assumption about complementary labels.\nThe experiments assume that each instance has exactly one complementary label. This may not reflect realistic scenarios and could bias the evaluation in favor of the proposed method.\nSpecifically, the proposed method relies on pairwise ranking between positive and complementary labels. With only one complementary label, the computational cost is O(K−1), but if the number of complementary labels grows to K/2, the complexity increases to O(K^2/4). Please clarify the implications of this.\n\n5. Evaluation metrics are incomplete.\nThe experiments rely solely on ranking-based metrics, while classification-based metrics are not reported. Some baselines are designed for MLL or PML, which may not be directly comparable with the proposed method. If including these baselines is necessary, more recent and ranking-aware baselines should be included to ensure fairness and meaningful comparison.\n\n6. Minor issues in Appendix A. The #Domain refers to data source rather than the data type, all datasets used are tabular data. The #Domain of BibTeX should be Text rather than Images. \n\n[1] Partial multi-label learning, AAAI, Vol. 32, 2018.\n\n[2] A ranking-based problem transformation method for weakly supervised multi-label learning, PR, 2024", "was_revised": true, "final_justification": "My concerns have been resolved. The paper is technically acceptable.", "rebuttal": "Thank you for reviewing our paper and providing valuable insights. We will reorganize the preliminaries section and address the issues in Appendix A. Below, we respond to the remaining concerns raised in the review.\n\n**W1: Potential contradiction in modeling assumptions.**\n\n> We are glad to have the opportunity to clarify that Assumption 4.4 does not contradict our earlier intuition regarding semantic exclusion. In fact, both true and complementary labels are selected by annotators based on the same source of information, the observed instance $ x$. Annotators assign true labels by identifying what is clearly present in the instance, and assign complementary labels by excluding what seems clearly absent. Since both decisions depend on the same features of $ x$, an implicit semantic exclusion naturally arises between complementary and true labels, even though the annotator may not know the full true label set $Y$.\n>\n> For example, if an image contains water, an annotator may not know whether the true label is 'river' or 'lake', but they can still confidently exclude 'desert' as a complementary label based on visual cues. This illustrates that semantic exclusion behavior can emerge indirectly due to shared dependence on instance features—precisely what Assumption 4.4 formalizes. This assumption provides a practical foundation for modeling complementary label selection without requiring access to $Y$.\n\n**W2: Theoretical comparison with URE is insufficient. ... Could the authors provide analysis or evidence regarding the (lack of) unbiasedness of ComRank?**\n\n> We would like to clarify that ComRank is not intended to derive URE, nor to serve as a risk estimator. Therefore, it is not applicable to analyze ComRank in the same manner as URE-based methods, i.e., deriving unbiasedness of ComRank. In fact, ComRank and URE-based methods reflect different learning paradigms. While URE-based methods follow a risk-recovery framework that reconstructs classification risk via surrogate losses and distributional assumptions, ComRank directly optimizes a pairwise ranking loss induced by complementary labels, without relying on such assumptions. Additionally, our goal is not to claim that ComRank universally dominates URE, but to highlight a limitation of URE: it may suffer from inconsistency when complementary labels are biased. In contrast, ComRank remains Bayes consistent without requiring strong assumptions on the label distribution. We will include this discussion in the revised version.\n\n**W3: Missing discussion on related ranking-based multi-label learning (MLL) methods.**\n\n> Thank you for the insightful comment. We will add the related work of ranking-based MLL methods in the revised version. Specifically, both [1,2] you suggested show how ranking can serve as an effective inductive bias under weak supervision. Beyond these, ranking losses have also been explored in standard supervised MLL settings. For example, [3] and [4] studied ranking-based surrogate losses with theoretical consistency guarantees. [5] applied calibrated label ranking for multi-label prediction, and [6] investigated pairwise ranking formulations for label dependencies. We will revise the related work section to include the above discussions.\n\n**W4: The experiments assume that each instance has exactly one complementary label. This may not reflect realistic scenarios and could bias the evaluation in favor of the proposed method. If the number of complementary labels grows to K/2, the complexity increases to O(K^2/4).**\n\n> In response to this concern, we conducted additional experiments where each training instance is uniformly assigned $K/2$ complementary labels. Indeed, the computational complexity increases with the number of complementary labels. However, our implementation can avoid explicit pairwise loops to reduce the impact of the $O(K^2/4)$ complexity. The loss can be computed using matrix operations and masking, which makes it efficient even for large label spaces. To empirically validate its efficiency, we provide the **running time**(in 10² seconds) across datasets for large label spaces. As shown in the table below, ComRank achieves comparable or superior speed to most baselines, indicating strong scalability.\n>\n> | Dataset       | #Label Classes | CCMN  | L-UW  | GDF   | MAE   | $R_u(g)$ | ComRank |\n> | ------------- | -------------- | ----- | ----- | ----- | ----- | ---------- | ------- |\n> | enron         | 53             | 2.94  | 3.22  | 3.79  | 3.72  | 3.14       | 3.15    |\n> | rcv1-s1       | 101            | 4.13  | 3.67  | 4.12  | 3.56  | 3.76       | 3.64    |\n> | bibtex        | 159            | 5.11  | 3.76  | 4.07  | 3.69  | 3.89       | 3.91    |\n> | bookmark      | 208            | 33.25 | 17.11 | 17.18 | 18.68 | 17.23      | 17.19   |\n> | **avg** | -              | 11.36 | 6.94  | 7.29  | 7.41  | 7.01       | 6.97    |          |\n>\n> Additionally, the following table reports the average precision of methods under $K/2$ complementary labels, where ComRank achieves better performance than most baselines. While the complexity increases with more complementary labels, the performance gains we observe make this trade-off both acceptable and worthwhile. We will update the manuscript to include these analyses.\n>\n> | Method   | L-UW  | CCMN  | GDF   | MAE   | $R_u(g)$ | ComRank         |\n> | -------- | ----- | ----- | ----- | ----- | ----- | --------------- |\n> | scene    | 0.481 | 0.550 | 0.845   | 0.573 | 0.849 | **0.849** |\n> | yeast    | 0.715 | 0.691 | **0.751**   | 0.728 | 0.750 | 0.749|\n> | enron    | 0.481 | 0.491 | 0.666   | 0.625 |0.652 | **0.673** |\n> | rcv1-s1  | 0.450 | 0.443 | 0.655   | 0.606 | 0.687 | **0.690** |\n> | bibtex   | 0.455 | 0.504 | 0.795   | 0.693 | 0.783 | **0.799** |\n> | bookmark | 0.622 | 0.524 | 0.709   | 0.710 | 0.714 | **0.731** |\n\n **W5.1: Classification-based metrics are not reported.**\n\n> We add hamming loss as a classification-based evaluation metric for experiments, where each instance is associated with a single complementary label that is uniformly sampled. To ensure fairness, we selected the optimal 0-1 threshold from prediction scores to prediction labels. As shown in the table below, our method achieves the best performance across all datasets, demonstrating that it also performs well under classification-oriented metrics.\n>\n> | Dataset    | CCMN  | L-UW  | MAE   | GDF   | $R_u(g)$ | ComRank         |\n> | ---------- | ----- | ----- | ----- | ----- | ---------- | --------------- |\n> | scene      | 0.242 | 0.820 | 0.820 | 0.152 | 0.163      | **0.136** |\n> | yeast      | 0.315 | 0.685 | 0.685 | 0.580 | 0.304      | **0.227** |\n> | enron      | 0.546 | 0.210 | 0.556 | 0.340 | 0.198      | **0.165** |\n> | rcv1-s1    | 0.456 | 0.812 | 0.885 | 0.420 | 0.115      | **0.111** |\n> | bibtex     | 0.596 | 0.191 | 0.870 | 0.774 | 0.080      | **0.059** |\n> | bookmark   | 0.150 | 0.770 | 0.725 | 0.916 | 0.084      | **0.063** |\n> | nuswideBoW | 0.135 | 0.846 | 0.864 | 0.865 | 0.135      | **0.124** |\n\n**W5.2: Some baselines are designed for MLL or PML, which may not be directly comparable with the proposed method. If including these baselines is necessary, more recent and ranking-aware baselines should be included to ensure fairness and meaningful comparison.**\n> We selected the following recent MLCLL and ranking-aware methods for comparison. Their details are summarized below:\n>\n> - MLCL [7]: A recent method for multi-label complementary label learning.\n> - LogRank [3]: A log-based ranking loss inspired by surrogate risk formulations.\n> - SoftmaxRank: A baseline we design by applying softmax function over predicted label scores and comparing their pairwise differences.\n>\n> We conduct experiments on datasets with uniform complementary labels, where each instance is associated with a single complementary label, and the experimental settings follow those described in the paper. As shown by the average precision results below, our method, ComRank, achieves the best performance on most datasets, further validating its proven Bayes consistency. We will include this discussion in the revised paper.\n>\n> | New baselines | MLCL  | LogRank | SoftmaxRank | ComRank         |\n> | ------------- | ----- | ------- | ----------- | --------------- |\n> | scene         | **0.814** | 0.419   | 0.677       | 0.785           |\n> | yeast         | **0.731** | 0.712   | 0.720       | 0.729           |\n> | enron         | 0.435 | 0.547   | 0.567       | **0.627** |\n> | rcv1-s1       | 0.547 | 0.263   | 0.280       | **0.605** |\n> | bibtex        | 0.248 | 0.453   | 0.450       | **0.677** |\n> | bookmark      | 0.557 | 0.197   | 0.586       | **0.618** |\n> | nuswideBoW    | 0.530 | 0.485   | 0.488       | **0.583** |\n\n**References**\n\n[1] Xie et al., Partial multi-label learning, AAAI, 2018.\n\n[2] Li et al., A ranking-based problem transformation method for weakly supervised multi-label learning, Pattern Recognition, 2024.\n\n[3] Dembczyński et al., Consistent multilabel ranking through univariate losses, ICML, 2012.\n\n[4] Li et al., Improving pairwise ranking for multi-label image classification, CVPR, 2017.\n\n[5] Zhang et al., Binary relevance for multi-label learning: An overview, Frontiers of Computer Science, 2018.\n\n[6] Fürnkranz et al., Multilabel classification via calibrated label ranking, Machine Learning, 2008.\n\n[7] Gao et al., Complementary to multiple labels: A correlation-aware correction approach, TPAMI, 2024."}, {"review_id": "qDZfyHrCe4", "reviewer": "Reviewer_d4Rs", "summary": "This work introduces a ranking loss framework for multi-label complementary label learning (MLCLL). Different from existing methods that are based on the assumption that complementary labels follow a uniform distribution, the proposed framework considers the instance-dependent assumption and introduces a complementary ranking loss for the MLCLL task.", "questions": "Please refer to \"Strengths And Weaknesses\"", "limitations": "Please refer to \"Strengths And Weaknesses\"", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This work introduces a ranking loss framework for multi-label complementary label learning (MLCLL). Different from existing methods that are based on the assumption that complementary labels follow a uniform distribution, the proposed framework considers the instance-dependent assumption and introduces a complementary ranking loss for the MLCLL task.\n\nStrengths:\n\n1.\tThe writing of this work is clear and easy to follow.\n2.\tThe presented mathematical proofs are rigorous.\n3.\tThe motivation of this work is convictive and experimental results verify the effectiveness of the proposed complementary ranking loss.\n\nWeaknesses:\n\n1.\tMy main concern focuses on the section of \"Complementary Label Distribution\". Regarding the uniform distribution assumption, it’s limitations illustrated in this work are easy to follow and persuasive. However, the introduced biased distribution assumption in Eq. (5) is quite challenging to follow and interpret. From my understanding from Eq. (5), $p(k={\\overline y} | x)$ is inversely proportional to $p(k \\in Y | x)$. However, it is quite different from the biased distribution assumption. I wonder if there is a misunderstanding on my part. It would be helpful if the authors could offer a more detailed and intuitive explanation for Eq. (5).\n2.\tAnother concern of mine is about \"Assumption 4.4\". I think that Assumption 4.4 is not suitable for a multi-label learning setting, it is more suitable from the single-label learning setting. As the example provided on Page 4, Line 162, if there are more than on animals in an image, a complementary label provided by annotators cannot be solely based on the image’s features. However, Assumption 4.4 plays an important role in this work, I wonder if there is a misunderstanding on my part. It would be helpful if the authors could offer a more detailed and intuitive explanation for Assumption 4.4.\n\nI would be willing to give a higher score if the authors can address the above-mentioned concerns in the response.", "was_revised": true, "final_justification": "My concerns have been addressed, and the clarifications provided helped me better understand the contribution. Therefore, I have decided to raise my overall score.", "rebuttal": "Thank you for reviewing our paper and providing valuable insights. We appreciate your feedback and would like to respond to the weaknesses raised.\n\n**R1: My main concern focuses on the section of \"Complementary Label Distribution\". ... It would be helpful if the authors could offer a more detailed and intuitive explanation for Eq. (5).**\n> The core idea of Eq. (5) is to model a biased complementary label distribution. Specifically, it assumes that labels outside the relevant label set have non-uniform probabilities of being selected as complementary labels, in contrast to the uniform assumption where all irrelevant labels are equally likely to be chosen.\n>\n> Eq. (5) expresses the intuition that the probability of an irrelevant label being chosen as a complementary label depends on its correlation with the relevant labels: the more similar a label is to the relevant labels, the less likely it is to be selected as a complementary label [1]. Thus, the probability of selecting ans irrelevant label $k$ as a complementary label is modeled to be inversely proportional to its likelihood of being relevant, i.e., $p(k \\in Y \\mid  x)$. All the above motivates our assumption in Eq. (5):\n>\n> $$\n> p(k = \\bar{y} \\mid  x) \\propto \\frac{1}{p(k \\in Y \\mid  x)}, if k \\notin Y\n> $$\n>\n> For example, given an image of a body of water, \"desert\" (a semantically distant label) is more likely to be excluded than \"lake\" (which is similar to a possible true label like \"river\"). This example illustrates how label similarity influences complementary label selection, leading to a biased (non-uniform) distribution. We will revise the manuscript to clearly explain the assumption expressed in Eq. (5), and improve the intuitive explanation.\n\n**R2: Another concern of mine is about \"Assumption 4.4\". ... It would be helpful if the authors could offer a more detailed and intuitive explanation for Assumption 4.4.**\n\n> Assumption 4.4 aims to reflect a more realistic and relaxed generation mechanism in MLCLL, where annotators typically do not have access to the full relevant label set when assigning a complementary label. According to previous work [2,3,4], this aligns with typical weakly supervised scenarios, where annotations rely on salient or dominant features rather than full label information.\n>\n> In some scenarios—such as an image containing multiple animals—annotators may struggle to exclude all relevant categories based solely on features. However, our assumption is motivated by the observation that annotators often eliminate obviously irrelevant labels by inspecting the input instance (e.g., excluding \"building\" from an image showing animals), without needing to infer the full set of relevant labels. This behavior supports modeling $\\bar y$ as conditionally independent of $Y$ given $ x$.\n>\n> We adopt this assumption as a tractable approximation that reflects limited annotator knowledge and allows us to derive a theoretically sound risk estimator under biased complementary label distributions. We will revise the manuscript to more clarify this motivation.\n\n**References**\n\n[1] Gao et al., Complementary to multiple labels: A correlation-aware correction approach, TPAMI, 2024.\n\n[2] Chen et al., Beyond class-conditional assumption: A primary attempt to combat instance-dependent label noise, AAAI, 2021.\n\n[3] Xia et al., Part-dependent label noise: Towards instance-dependent label noise, NeurIPS, 2020.\n\n[4] Zhu et al., A second-order approach to learning with instance-dependent label noise, CVPR, 2021."}]

Author rebuttal:

Meta-review: This paper makes a solid contribution to the multi-label learning literature, particularly by highlighting theoretical deficiencies in prior work on using complementary labels and providing a new framework to address them. The theoretical analysis is well-motivated, and the paper raises important points that advance understanding in this area.

During review, some concerns were raised about the theoretical framework and the strength of certain assumptions (especially Assumption 4.4), as well as the connection between the theory and the eventual algorithm. While these concerns are valid discussion points, the authors provided strong and thoughtful responses that clarified their reasoning and addressed most of the issues. Incorporating these clarifications and discussion into the final version will further strengthen the contribution.
Decision: Accept (poster)