Rethinking Consistent Multi-Label Classification Under Inexact Supervision
Authors: Wei Wang
Tianhao Ma
Ming-Kun Xie
Gang Niu
Masashi Sugiyama
Venue: ICLR 2026 Poster (2026)
Keywords: Multi-label classification
partial multi-label learning
complementary multi-label learning.
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We propose a general and consistent framework for multi-label learning under inexact supervision.

Abstract: Partial multi-label learning and complementary multi-label learning are two popular weakly supervised multi-label classification paradigms that aim to alleviate the high annotation costs of collecting precisely annotated multi-label data. In partial multi-label learning, each instance is annotated with a candidate label set, among which only some labels are relevant; in complementary multi-label learning, each instance is annotated with complementary labels indicating the classes to which the instance does not belong. Existing consistent approaches for the two paradigms either require accurate estimation of the generation process of candidate or complementary labels or assume a uniform distribution to eliminate the estimation problem. However, both conditions are usually difficult to satisfy in real-world scenarios. In this paper, we propose consistent approaches that do not rely on the aforementioned conditions to handle both problems in a unified way. Specifically, we propose two risk estimators based on first- and second-order strategies. Theoretically, we prove consistency w.r.t. two widely used multi-label classification evaluation metrics and derive convergence rates for the estimation errors of the proposed risk estimators. Empirically, extensive experimental results on both real-world and synthetic datasets validate the effectiveness of our proposed approaches against state-of-the-art methods.

Published as a conference paper at ICLR 2026
RETHINKING CONSISTENT MULTI-LABEL CLASSIFI- CATION UNDER INEXACT SUPERVISION
Wei Wang 1,2#1 Tianhao Ma
Ming-Kun Xie
Gang Niu
Masashi Sugiyama 1.2
1 RIKEN, Japan
2 The University of Tokyo, Japan
(wei. wang,,anggg.. ming-kun. xie @riken. jp
/matianhao2120, gang. niu. ml) } gma i 1 com sugiēk.u ttt-kooooccc. ip
ABSTRACT
Partial multi-label learning and complementary multi-label learning two pop- ular weakly supervised multi-label classification paradigms that aim to alleviate the high annotation costs of collecting precisely annotated multi-label data. In partial multi-label learning, each instance is annotated with candidate label set, among which only some labels are relevant; in complementary multi-label learn- ing, each instance is annotated with complementary labels indicating the classes which the instance does not belong. Existing consistent approaches for the two paradigms either require accurate estimation of the generation process of candi- date or complementary labels or assume a uniform distribution eliminate the estimation problem. However, both conditions are usually difficult to satisfy in real-world scenarios. In this paper, we propose consistent approaches that do not rely on the aforementioned conditions to handle both problems in a unified way. Specifically, we propose two risk estimators based on first- and recond-order strategies. Theoretically, prove consistency w.r.t. two widely used multi-labe label classification evaluation metrics and derive convergence rates for the estimation errors of the proposed risk estimators. Empirically, extensive experimental re- sults on both real-world and synthetic datasets validate the effectiveness of our proposed approaches against state-of-the-arr methods.
INTRODUCTION
In multi-label classification (MLC), each instance associated with multiple relevant labels simul- taneously (Zhang & Zhou, 2014; Liu et al., 2022b). The goal of MLC is to induce multi-label classifier that can assign multiple relevant labels to unseen instances. MLC is more practical and useful than single-label classification, as real-world objects often appear together in single scene. The ability to handle complex semantic information has led to the widespread use of ML. in many real-world applications, including multimedia content annotation (Cabral et al., 2011), text clas- sification (Rubin et al., 2012: Liu et al., 2017). and music emotion analysis (Wu et al., 2014). However, annotating multi-label training data is more expensive and demanding than annotating single-label data. This because each instance can be associated with an unknown number of rel- evant labels (Durand et al., 2019; Cole al., 2021; Xie et al., 2023), making difficult to collect large-scale multi-label dataset with precise annotations.
To address this, learning from weak supervision has become prevailing way mitigate the bot- tleneck of annotation cost for MLC (Sugiyama et al., 2022). Among them, partial multi-label learning (PML) and complementary multi-label learning (CML) have become two popular MLC paradigms. In PML, each instance is annotated with a candidate label set, among which only some labels are relevant but inaccessible to the learning algorithm (Xie & Huang, 2018; Sun al., 2019; Gong et al., 2021). In CML, each instance is annotated with complementary labels, which indicate the classes to which the instance does not belong (Gao al., 2023; Zhu et al., 2025; Gao et al., 2026). Given that all relevant labels are included in the candidate label set, non-candidate labels
$ Equal contributions. 'Corresponding author: Wei Wang <wei wwwgei.wn@@rriii rike@@ii...jp....

---

Published as a conference paper at ICLR 2026
Table I: Comparison of COMES with existing consistent PML and CML approaches.
Uniform distribution
Generation process
Label
Multiple
Approach
assumption-free
estimation unnecessary correlation-wware complementary labels
CCMN (Xic & Huang. 2023)
X
CTL (Gao al., 2023)
X
x
X
MLCL (Gso et al., 2024)
/
X
V
X
GDF (Gao et al., 2025)
X
X
V
COMES-HL (Ours)
/
V
X
V
COMES-RL (Ours)
/
V
V
contain relevant labels and can be considered complementary labels, and vice versa. This sug- gests that the two problems are mathematically equivalent. Therefore, in this paper, we treat them as MLC under inexact supervision in a unified way. Figure shows example image annotated with inexact annotations. The label space contains ten labels in total. The candidate label set consists of four relevant labels (apple, plate, table, jug) and two false-positive ones (grapes, pear). By ex- cluding the candidate labels from the label space, the remaining four labels are (banana, cup, knise, flower), which can be considered complementary labels. PML and CML do not require precise determination of all relevant labels during annotation, which demonstrates their great potential for alleviating annotation challenges in MLC.
In this paper, we investigate consistent ap- proaches for MLC under inexact supervision. Here, consistency means that classifiers learned with inexact supervision are theoretically guar- anteed to converge to the optimal classifiers when infinitely many training samples are pro- vided (Wang et al., 2024). The remedy began with Xie & Huang (2023), which treated PML. special case of MLC with class-conditional label noise (Li et al., 2022; Xia et al., 2023), where irrelevant labels could flip relevant la-
Condidate Label Set:
Apple Plate
Table Jug
Pear
Complementary Labels
Banana
Cup
Knife
Flower
Figure 1: A multi-label image with inexact anno- tations. Source: Paul Cézanne, Still Life, Jug and Fruit on Table (1894), public domain.
bels but not vice versa. However, the flipping rate for each class is unknown and must be estimated using anchor points, i.e., instances belonging to specific class with probability one (Liu & Tao, 2015; Xie & Huang, 2023). Similar to PMI,, CML assumes that complementary labels are generated by a certain flipping process (Yu et al., 2018b). Gao et al. (2023) proposed the uniform distribution assumption that label outside the relevant label set sampled uniformly to be the CL. Then, Gao al. (2024) generalized the data generation process with a transition matrix, but estimating the data generation process is still nec- essary. Recently, Gao et al. (2025) extended the uniform distribution assumption to handle multiple complementary labels.
In summary, all existing consistent PML and CML approaches either estimate the generation process of the candidate label set or complementary labels, adopt the uniform distribution assumption to eliminate the estimation problem. However, both conditions are difficult to satisfy in rorl-world scenarios. On the one hand, estimating the flipping rate heavily relies on accurate estimation of noisy class posterior probabilities of anchor points (Xia et al., 2019; Yao et al., 2020; Lin et al., 2023). However, estimating noisy class posterior probabilities is more difficult because their entropy is usually higher than that of clean labels (Langford, 2005). This difficulty is further amplified when using deep neural networks, where the over-confidence phenomenon typically occurs (Zhang al., 2021; Wei et al., 2022). The model outputs of deep neural networks are usually one-hot encoded, which means they cannot yield reliable probabilistic outputs (Guo et al., 2017). On the other hand, the uniform distribution assumption treats different candidate label sets indiscriminately, which is too simple to be truly in accordance with imbalanced classes in real-world scenarios (Wang et al., 2025). Additionally, many approaches model different labels independently and directly ignore label correlations existing in multi-label data (Gao et al., 2025). This prevents them from exploiting the rich semantic relationships of label correlations (Zhu al., 2017: Mao et al., 2023).
To this end, we propose a novel framework named COMES, i.c., COnsistent Multi- classifica- tion under inExact Supervision. Based data generation process that does not transition ma-
2

---

Published as a conference paper at ICLR 2026
trices, we introduce two instantiations with risk estimators w.r.t the Hamming loss and ranking loss, respectively. Table I compares our approach with existing consistent PML and CML approaches. Our contributions are summarized follows:
We propose a consistent framework for multi-label classification under inexact supervision that neither requires estimating the generation process of candidate complementary labels nor relies on the mniform-distribttin assumption.
We introduce risk-correction approaches to improve the generalization performance of the pro- posed risk estimators. We further prove consistency w.r.t. two widely used metrics and derive convergence rates of estimation errors for the proposed risk estimators.
Our proposed approaches outperform state-of-the-ae baselines on both real-world and synthetic PMI. and CMI. datasets with different label generation processes.
PRELIMINARIES
In this section, we introduce the background of MLC and MILC under inexact supervision.
2.1 MULTII-LABIL CLASSIFICATION
Let X' = Rd denote the d-dimensional feature space and y (1, the label space consisting of q class labels. A multi-lahel example is denoted as (ar, Y). where x E X' is feature vector and Y S y is the set of relevant labels associated with [y1, 1/,1.,2..... yy] E {0, 11. to denote the vector representation of Y. where Yj 1 if j Y and YA 0 otherwise. Let p(x, Y) denote the joint density of æ and Y. Let p(æ) denote the marginal density, and x = p = 1) the prior of the j-th class. The task of MLC is to learn prediction function f X' - 2d We use f, to denote the j-th entry of f. where fz(z) = 1 indicates that otherwise. Since learning f directly is often difficult, we use real-valued decision function g X' - IR9 to represent the model output. The prediction function f can be derived by thresholding g. We use 9j to denote the j-th entry of g. which indicates the model output for class j.
introduce For ease of notation,
the model predicts class j to be relevant to æ and fz)
Many evaluation metrics have been developed to calculate the difference between model predictions and true labels to evaluate the performance of multi-label classifiers (Zhang & Zhou, 2014; Wu & Zhou, 2017). In this paper, we focus primarily on the Hamming loss and ranking loss, the two most common metries in the literature.' Specifically, the Hamming loss calculates the fraction of misclassified instance-label pairs, and the risk of f w.r.t. the Hamming loss is
| E I(f(x) + v1)
R (f) (f) = Ep(m,
(1)
Here, I denotes the indicator function that returns the predicate holds; otherwise, returns O. Since optimizing the 0-1 loss is difficult, a surrogate loss function é is often adopted. The E-risk w.r.t. the Hamming loss is
( (0) (z) ト (
RE = Bp(err)
where l is a non-negative binary loss function, such as the binary cross-entropy loss. It is important to note that the Hamming loss only considers first-order model predictions and cannot account for label correlations. The ranking loss explicitly considers the ordering relationship between model outputs for a pair of labels. Specifically, the risk of f w.r.t. the ranking loss is?
R = Ep(arr) Enereker I(U; < uk) (I03)00) > fa(x)) + [[((()) = fb(x)))
+ +T( yk) (I(((()) < sc(x)) + + = [((a))
I We will address use of other metrics in future work.
2To facilitate the analysis in this paper, we consider the coefficients of the losses for different label pairs to he (Gao& & Zhou, 2013; Xie Huang, 2021; 2023).
3

---

Published as a conference paper at ICLR 2026
Similarly, when using surrogate loss function to replace the 0-1 loss, the f-risk w.r.t. the ranking loss is
(g) Bp Eiejaken I(y; + va)e 91(2)) gl(xx), Mj yk +
(4)
Notably, minimizing the Hamming loss does not consider label correlations and can be considered
a first-order strategy. In contrast, minimizing the ranking loss considers label-ranking relationships and can be considered second-order strategy.
2.2 MULTI-LABEL CLASSIFICATION UNDER INEXACT SUPERVISION
In PML, each example is denoted as (x, where S is the candidate label set associated with æ. The basic assumption set, i.e., y S. Let 5 VMS denote the absolute complement of S. Since SUY Ø. S can be regarded as the set of complementary labels associated with æ. Therefore, PML and CML are mathematically equivalent, as partial multi-label data can equivalently be transformed into comple- mentary multi-label data and vice versa. Without loss of generality, this paper mainly considers partial multi-label data. For ease notation, we use s [$1. $2, ......,......................... sy] to denote the vector repre- sentation of S. Here, 8j indicates that the j-th class label is a candidate label of æ, and sj 0 otherwise. Let p(x, S) denote the joint density of x and the candidate label set S. The goal of PMI. or CML is to learn prediction function X - 2 that can assign relevant labels to unseen instances based on a training set D {a., 5 /_ sampled i.i.d. from p(x: S).
PML is that all relevant labels are contained within the candidate label
3 METHODOLOOGY
In this section, we first introduce our data generation process. Then, we present the first- and second- order strategies for handling the PML problem and their respective theoretical analyses.
3.1 DATA GENERATION PROCESS
In this paper, we assume that the candidate labels are generated by querying whether each instance is irrelevant to a class in turn. Specifically, if the j-th class is irrelevant to æ, we assume that the j-th class label is assigned as non-candidate label æ with constant probability Pj. i.c., (i $ S|æ,j $ Y) Py. Otherwise, if the j-th class is relevant to æ, we consider it as candidate label. The candidate label set can then be obtained by excluding the non-candidate labels from the label space. Notably, all relevant labels are included in the candidate label set, as well as some irrel- evant labels. This data generation process coincides well with the annotation process of candidate labels. For example, when asking annotators to provide candidate labels for image dataset, we can show them an image and a class label and ask them to determine whether the image irrelevant to that class. This is often easier question answer than directly asking all relevant labels, since it is less demanding to exclude some obviously irrelevant labels. If so, we assume that the image will be annotated with this label as a non-candidate label with a constant probability. Based this data generation process, we have the following lemma.
Lemma Assume that p(s, = 0|2 yj = 0) = Pj. where Pj a constant. Then, we have p(z 0) p(æly, 0).
The proof can be found in Appendix B.I. According to Lemma 1, the conditional density of in- stances where the j-th class is considered a non-candidate label is equivalent to the conditional density of instances where the j-th class is irrelevant. Notably, our data distribution assumption differs from both the uniform distribution assumption and the use of a transition matrix to flip the la- bels. Since the conditional probabilities of different candidate label sets can be different, our setting is more general than the uniform distribution assumption (Gao et al., 2023; 2025).
3.2 FIRST-ORDER STRATEGY
common strategy used in MLC is to decompose the problem into a number of binary classification problems by ignoring label correlations. This goal can be achieved by minimizing the E-risk w.r.t. the
4

---

Published as a conference paper at ICLR 2026
Hamming loss in Eq. (2). We show that the E-risk w.r.t. the Hamming loss can be equivalently expressed with partial multi-label data.
Theorem 1. By the assumption in Lemma 1, the l-risk war. the Hamming loss in Eq. (2) can be equivalently expressed as
R(((g) = BBp(a)
Σ eays (2)), (z)).
19
19 أ E pp
| [
Ti
(m), (a),
(5)
The proof can be found in Appendix B.2. Theorem shows that the t-risk w.r.t. the Hamming loss can be expressed as the expectation w.r.t. the marginal and conditional densities where the j-th class candidate label. Since Eq. (5) cannot be calculated directly, we perform
label not considered empirical risk minimization (ERM) by approximating Eq. (5) using datasets Du and Dj e y) this paper, we consider generating these datasets by duplicating instances from D. Specifically, we first treat the duplicated instances of D as unlabeled data sampled from p(æ) and add them to Dy. Then, if an instance does not treat the j-th class label as a candidate label, treat its duplicated instance being sampled from p(a |8 = 0) and add it to Dj. These processes can be expressed as follows:
sampled from densities p(æ:) and y(ar 8 0). respectively.
Du {- U1" Ji- = (a. (a,, Si) D), Dj - (mr) "
(a. St) E D, $ S:) E y (6)
Then, an unbiased risk estimator can be derived to approximate Eq. (5) using datasets Du and Dj:
(g) Σ"
ng i-- E j-1
e (gs (z.))
1- Tj 2 2==1 gny
1 (e (e(9) x (2)) -2 (0) (
(z)) (z.).11 .1).
When deep neural networks are used, the negative terms in the loss function can often lead to overfit- ting issues (Kiryo et al., 2017; Sugiyama et al., 2022). Therefore, we use an absolute value function to wrap each potentially negative term Lu et al. (2020); Wang et al. (2023). The corrected risk estimator is defined as
(g) =
19
Σ" 1-
e (gs (2 1) 1- En e (9)
(x)) .e)..)
j-1
ny
My Σm (9) ( (z))).).
+
- qu
(8)
Notably, our framework is very flexible so that the minimizer can be obtained using any network architecture and stochastic optimizer. The algorithmic details are summarized in Algorithm 1. The class prior πy can be estimated by using off-the-shelf class prior estimation approaches only using candidate labels (see Appendix A.2).
We establish the consistency and estimation error bounds for the risk estimator proposed Eq, (8). First, we demonstrate that the corrected risk estimator in Eq. (8) is biased yet consistent w.r.t the l-risk w.r.t. the Hamming loss in Eq, (2). The following thcorem holds.
Theorem 2. Assume that there exists constant Cg such that sup 1gglec & CG and a constant Ce such that sup &Cg {(2, y) & Ce. where G is the model class. We assume that there exists a positive constant such that Vj V, Ty Ty =1) [e (gz (æ) 1)] > a. Then, the bias of the expectation of the corrected risk estimator w.E.. the E-risk w.r.. the Hamming loss has the following lower and upper bounds:
0 E R
R((()) & (4 2 -
where Aj exp 202 / (Ct/ + +1 (1-,,)²²? (02//n)) /n))) Furthermore, for any 8 > 0, the following inequality holds with probability at least 8:
(((0)) R(((o)
& 9
1 E
(4- (
+ (2-2x,)C.
In (2/0)
+ CCN
In (2/8)
9
2nj
2n
(10)
5

---

Published as a conference paper at ICLR 2026
The proof can be found in Appendix B.3. Notably, the bias of the corrected risk estimator from the original E-risk exists since it is lower bounded by zero. However, as n - s0, we have that [g) - H (g). meaning that it is still consistent.
Let ÒH = arg |sg (g) and Iú = arg min 10 (g) denote the minimizer of the corrected risk estimator and the E-risk w.r.t. the Hamming loss, respectively. Let Rn.p(9) and Rny.ps sy (9) denote the Rademacher complexities defined in Appendix B.4.
Theorem 3. Assume that the loss function f(z y) is Lipschitz continuous in z with a Lipschitz constant Le. By the assumptions in Theorem 2, for any 8 > 0, the following inequality holds with probability at least 1 - 8:
(gH) (9f & 8L1 E Rm (9)
16(1 - TT) I
2 Rny.p (9)
q
q
In (1/8)
(4 31-40 4x,)
IIn (1/6) 2ng
q - (4 (4-2,) + 2CNV
(11)
2n 5ー
The proof be found in Appendix B.4. Theorem shows that, as n 00, Reg Ri (gn)
since Aj - 0, (9) - 0, and Ra,.,, (9) - 0 for all parametric models with a bounded norm (Mohri al., 2012). This means that the minimizer of the corrected risk estimator will ap- proach the desired classifier that minimize the E-risk w.r.t. the Hamming loss.
Let R inf,, Rig(() and Rt i (f) denote the minima of the l-risk and the risk w.r.t. the Hamming loss, respectively. Then, the following corollary holds.
Corollary 1. If é is convex function such that Vy, (',, y) then the l-risk w.r.. the Hamming loss in Eq. (5) is consistent with the risk w.r.t. the Hamming loss in Eq. (1). This means that, any any sequence of decision functions {ge) with corresponding prediction functions (ft), if R (g) R Rt
then R2 (fr)
The proof can be found in Appendix B.5. If the model is flexible enough to include the optimal classifier, according to Theorem 3, we have (ān) - R Then, Corollary I demonstrates that " - Ri where fH is the corresponding prediction function of ÒH. This indicates that the prediction function obtained by minimizing the corrected risk estimator Eq. (8) achieves the Bayes risk.
3.3 SECOND-ORDER STRATEGY
The first-order strategy is straightforward but does not consider label correlations, which may be incompatible with multi-label data that exhibit semantic dependencies. Therefore, we explore the ranking loss to model the relationship between pairs of labels. The following theorem applies.
Theorem 4. When the binary loss function & is symmetric, i.e., l(z, -) + ((-2,-)- M where M is a neg-tigative constant, then under the assumption in Lemma 1, the l-risk wart. the ranking loss in Eq. (4) can be equivalently expressed as
(g) = EEEsekke ((1 Ty T,) Blalss -0)
gh (]]
+(1 B =0) Le (gj (x) gu (x), 1)] Mplu; = 0, yk 0))
(12)
The proof can be found in Appendix B.6. Here, the symmetric-loss assumption is often used to ensure statistical consistency of the ranking loss for MIC (Gao Zhou, 2013). According to The- orem 4, the t-risk w.r.t. the ranking loss can be expressed density where the j-th class label is not regarded as a candidate label. Notably, Mp(U, = 0, y = 0) in Eq. (12) is constant that does affect training the classifier, it be neglected. Similar to the first-order strategy, an unbiased risk estimator can be obtained using Dy:
the expectation w.r.t. the conditional
(1-10) Enh e (0)(xr)) - 9x( (x(x=)))))
kg(9)
Σ Liggeken
n3
===
1 -
1nk i-
E (g)(2,))) go oo(wt)))))
(13)

---

Published as a conference paper at ICLR 2026
To improve generalization performance, we use the flooding regularization technique (Ishida et al., 2020; Liu et al., 2022a; Bac et al., 2024) to mitigate overfitting issues:
(g) (g) 3 + +
(14)
where 3 > 0 is hyper- ppeem-prreeter that controls the minimum of the loss value. Then, we can perform ERM by using Eq. (14). The algorithmic details are summarized in Algorithm 1. We also establish consistency and estimation error bounds for the proposed risk estimator in Eq. (14). The following theorem then holds.
Theorem 5. We assume that there exists positive constant y such that Rg(g) % We also assume that B is chosen such that 3 < Lisjekey Mply; = O. yk = Ojz. By the assumptions in Theorem 2, the bias of the expectation of the corrected risk estimator w.r.t. the ranking loss has the following lower and upper bounds:
0 < E RR(g) - -E,ec
Mplu; = 0. = =0) -R)g) < (28+20
1) Σÿ (1 x3)) D',
(15)
where A' = exp
(
Furthermore, for any 8 > 0, the follow-
ing inequality holds with probability at least 1 1 8:
(l((9) - -E,e Mp(uj = 0, yk = 0) - (9) < Σ (1 (1-,(1- 1
(2/8)
2ng
+ -(23+ 2C8+2C0l9 - Σ3 (1 my)) A..
(16)
The proof can be found in Appendix B.7. According to Theorem 5, as n1 cc, the bias between the corrected risk estimator in Eq. (14) and the ê-risk of ranking loss will become a constant. This implies that the minimizer of the corrected risk estimator equivalent to the desired classifier that minimizes the l-risk w.r.t. the Hamming loss.
arg min ( JCG R (g) and gh arg (2) J=g (g) denote the minimizers of the corrected risk estimator and the f-risk w.r.t. the ranking loss, respectively.
Let OR- =
Theorem 6. By the assumptions in Theorem 3 and 5, for any > O, the following inequality holds with probability at least 1 6:
(ğn) (g( < (23 20d( - En (1 1-:m;)) A
In (1/6) n2
+ 9 (1- 1 1)
E 4Le(9 1)(1-1r)))))
- RRy),nn (9). (17)
The proof can be found in Appendix B.S. Theorem 6 shows that n 00, Rf (āR) Rt (g since A' - O and Rm,,,, (9) - 0 for all parametric models with bounded norm (Mohri et al., 2012). This means that the minimizers of Eq. (14) will approach the desired classifiers of the l- risk w.r.t. the ranking loss when the number of training data increases. Let 1Ht inf, R2g (g) and R = inf, f (f)) denote the minima of the f-risk and the risk w.r.t. the ranking loss, respectively. Then we have the following corollary.
Corollary 2. Ifl is differentiable, symmetric, and non-increasing function such that Vy, (0. < O and f(2, y) + E((22.)) = M, then the l-risk w.r.. the ranking loss in Eg. (12) is consistent with the risk w.r.t. the ranking loss in Eg. (3). This means that for any sequences of decision functions {g:} with corresponding prediction functions (fe). if R(gge) + R then RR (ft) + R
The proof can be found in Appendix B.9. If the model is very flexible, we have R (ğR) 12 according to Theorem 6. Then, Corollary 2 demonstrates that RR- (fR) - R where fR is the corresponding prediction function of ğR. This indicates that the prediction function obtained by minimizing Eq. (14) achieves the Bayes risk.
EXPERIMENTS
In this section, we validate the effectiveness of the proposed approaches with experimental results.
7

---

Published as a conference paper at ICLR 2026
Table 2:
Experimental results on real-world benchmark datasets. Lower is better for the ranking loss, one error, Hamming loss, coverage; higher is better for the average precision.
Ranking Loss 1
Approach
mirllickr
Dasic_emotion
music_ste style
yeastBP
yeasiCC
yeastMI
BCB
0,106 = 0.008
0.244 = 0.007
0.137 + 0.009
0.328 + 0.013
0.206
0.011
0.251 + 0.010
CCMN
0.106 + 0.011
0.224 + 0.007
0.155 +: 0.012.
0.328 + 0.011
0.210
0.013+
0.245 + 0.011
GDF
0.159 = 0.007
0.278
0.010=
0.160 0.008
0.501 1: 0.009
0.504
0.016
0.495 1: 0.029
CTL
0,130
0.006
0.266
0.010
0.179 + 0.008
0,498 = 0.007
0.467
0.014
0,471
+ 0.026
MLCL
0.498
0.035
0.470
0.046
0.130 + 0.010
0.453 + 0.033
0.222
0.047
0.231 + 0.077
COMES HI.
0.095
0.009
0.214 = 0.005
0.132 +: 0.010
0.154 + 0.010
0.124
0.011
0.173 +: 0.021
COMES-RL
0.106
0.006
0.213
0.003
0.147 0.013
0.166 i 0.010
0.117
0.009
0.151 1 0.014
One Error
Approach
mirtlickr
music_enme _esiiceettion
music_style
yeastBP
yeastCC
yeastMF
BCE
0.275 :: 0.021
0.462 = 0.015
0.345 0.019
0,871 +: 0,008
0.814
0.019
0.886 t: 0.020
CCMN
0.282 + 0.030
0.385 = 0.018
0.346 + 0.017
0.878 + 0.016.
0.823
0.016
0.882 + 0.012
GDF
0.409 + 0.027
0.531
0.012
0.367
0.018
0.976 + 0.006
0.971
0.008
0,972 4 0.007
CTL
0.366 : 0.017
0.469
0.019
0.394 + 0.022
0.970 + 0.006
0.964
0.004.
0,963 1 0.010
MLCL
0,810
0.066.
0.793 = 0.041
0.405 + 0.068
0.961 + 0.038
0.862
0.066.
0.887 1 0.066
COMES HL.
0.171 :: 0.019
0.382 = 0.015
0.333 1 0.012
0.641 : 0.030
0.744
0.020
0.800 : 0.023
COMES-RL
0.206 = 0.036.
0.409 = 0.015
0.351 + 0.021
0.808 + 0.016.
0.754
0.022
0.805 + 0.020
Hamming Loss
Approuch
mirllickr
music_emotion
music_style
yeastBP
yeastCC
yeastMIF
BCE
0.220 + 0.007
0.307 = 0.007
0.186 + 0.005
0.148
0.007
0.162 0.007
0.153 + 0.006
CCMN
0.220 + 0.006
0.284
0.013
0.239 + 0.020
0.151 + 0.007
0.163 + 0.008
0.150 + 0.005
GDF
0.277 1 0.007
0.374
= 0.009
0.251 : 0.008
0.499 1 0.016
0.489 1 0.026
0.497 1 0.030
CTL
0.237 0.006
0.349
= 0.006
0.298 + 0.008
0.493
0.009
0.499
0.007
0.496 = 0.006
MLCL
0.601 1 0.020
0.480
0.025
0.246
1 0.019
0,881 I 0.096.
0.845 1 0.051
0.837 1 0.024
COMES-HI HI.
0.164 + 0.003
0.247
0.005
0.120 + 0.006
0.073 + 0.008
0.119 + 0.015
0.101 + 0.005
COMES RL
0.186 1 0.008
0.278
0.005
0.210 + 0.008
0.051 : 0.001
0.045
0.004
0.048 : 0.003
Coverage
Approach
mirflickr
music_ _ectiieemoionnnn
music_style
yeastBP
yeastCC
yeastMF
BCE
0.212 + 0.009
0.408
0.010
0.197
0.011
0.437 i 0.021
0.123
0.010.
0.125 + 0.011
CCMN
0,212 0.012
0.392
0.010
0.216 + 0.015
0,436 : 0.022
0.125
0.012
0.123 + 0.012
GDF
0.254 + 0.006*
0.440
+ 0.010
0,220 +: 0.010
0.569 + 0.019
0.273
0.018+
0.242 + 0.022
CTL
0.229 + 0.008
0.441
0.014
0,240
0.011
0.567
1 0.016.
0.259
0.017
0.231
1 0.015
MLCL
0.492
0.036.
0.596
0.047
0.177
0.013
0,530 1 0.072
0.137
0.045
0.099 1 0.032
COMES HI.
0,211
0,008
0.379
0.008
0.192 1 0.012
0.229 + 0.016
0.070
0.008
0.085 1 0.006
COMES-RL
0.224 0.008
0.377 0.006
0.208 1 0.015
0.219 + 0.015
0.070 0.006
0.073 1 0.005
Average Precision
Approach
mirflickr
music_emotion eemotiotti
music
music_style
yeastBP
yeastCC
yeastMF
BCE
0,813 + 0.011
0.616 = 0.009
0.738 : 0.013.
0.150 : 0.013
0.487
0.016.
0.379 + 0.019
CCMN
0.811 + 0.016.
0.660 0.010
0.728
0.013+
0.150
0.012
0.479
0.016.
0.386 + 0.02]
GDF
0.742 : 0.013
0.574 = 0.008
0,711
+: 0.011
0.057 1 0.002.
0.135
0.010.
0.144 1 0.016
CTL
0.772 = 0.009
0.600
= 0.011
0.692
:: 0.012
0.060 : 0.002
0.154
0.004
0.165 1 0.013
MLCL
0.446 = 0.038
0,381
0.029
0.719 0.035
0.082 + 0.015
0.402
0.080
0.375 + 0.124
COMES-HL
0.843
0.013
0.665
0.009
0.749
0.010
0.458 + 0.029
0.657
0.020
0.552 + 0.023
COMES RL.
0.818 : 0.011
0.665
0.006
0.732 1 0.013
0.315 : 0.015
0.023 0.651
0.549 1: 0.019
4.1 EXPERIMENTAL SETUP
We conducted experiments on both real-world and synthetic PML benchmark datasets. For real- world datasets, we used mirflickr (Huiskes & Lew, 2008), music_emotion (Zhang & Fang, 2020). music_style yeastBP (Yu et al., 2018a), yeastCC and yeastMF; for synthetic datasets, we used VOC2007 (Everingham et al., 2007). VOC2012 (Everingham et al., 2012), CUB (Wah et al., 2011) and COC02014 (Lin et al., 2014), where candidate labels were generated by two different data generation processes. Full experimental details given in Appendix C. Following standard prac- tice (Liu et al., 2023), we evaluated with ranking loss, one error, Hamming loss, coverage and average precision on real-world sets, and with mean average precision (mAP) on synthetic datasets.
For real-world datasets. we used an MLP encoder for all baselines, trained for 200 epochs with a learning rate of 5e-3, weight decay of le-4, and the SGD optimizer with cosine decay. For synthetic
8

---

Published as a conference paper at ICLR 2026
Table 3: Classification performance in terms of mAP synthetic benchmark datasets.
VOC2007
VOC2012
CUB
COC02014
Approach
Case-a
Case-b
Care-a
Case-b
Case-n
Case-b
Case-a
Case-b
0.14e
CCMN
4.98
1:22e
16.51
0.25
0.90
25.24
26.79
1.23
GDF
21.27 1: 1.03+
20.19
0.43+
23.58
2.55+
22.96
2.87
12.83
1: 0.15m
12.77
1 0.10=
17.32
0.62
15.86
0.35
CTL
17.05 + 0.90
18.87
+: 1.86
19.38
0.81
18.51
0.71
11.94
+ 0.23*
11,94
+ 0.23*
6.31
+ 0.30
6.34
2 0.1/
MLCL
23.42
1: 1.66e
17.78
1.18
15.02
4.68
15.00
2 3.54
16.80
1 0.04
17.92
1 0.10a
10.59
1 0.63+
10.67
0.81
COMES-HL
42.33
1.74
42.43
4.17
48.72
1.08
47.93
1.05
18.94
0.30
32.76
1.45
COMES-RI.
$1.46 + 3.09
49.42
4.27
53.26
0.74
52.29
4.15
17,50
+ 0.33
17:34 + 0.03
27.98
+ 0.30
28.69
1.62
COMES-HE Averaga Precision
COMES-AL Banking Lous
Averuga Precision
Banking Loss
0.71
0.20
0.179
03
0.15
0.129
0.4
0.100
0.050
0.05
011
MAROC
0.1
0.00
Standard Deviationn-15
Standard Deviationt
"|
Standard Deviationt= ")
Standard Deviation(1101)
Figure 2: Classification performance with inaccurate class priors different datasets.
Ranking Loss
Average Precision
One Error
Coverage
0.25
0.30
0.275
0.35
0.20
0.250
0.15
0.75
0.25
0.10
0.200
10
15
Figure Sensitivity analysis w.r.t. on the mirflickr dataset.
image datasets, adopted a ResNet-50 backbone pretrained ImageNet (Deng al., 2009), trained for 30 epochs with a learning rate of le-4 using the Adam optimizer. For fair comparisons, used the same setup across all baselines. We assumed that the class priors were accessible to the learning algorithm. We instantiated & with the binary cross-entropy loss for COMES-H and the sigmoid loss for COMES-RL. We performed ten-fold cross-validation on real-world datasets. This means we used nine folds for training and one fold for testing. Then, we recorded the mean accuracy and standard deviation. For the synthetic datasets, we generated synthetic labels three times and recorded the mean accuracy and standard deviation. Finally, we conducted paired t-tests at a 0.05 significance level.
4.2 EXPERIMENTAL RESULTS
Tables 2 and 3 summarize results real-world and synthetic datasets, respectively. Here indicates that the best method is significantly better than its competitor (paired (-test at 0.05 significance level). We observe that both instantiations of COMES consistently outperform other baselines across various datasets, clearly validating the effectiveness of our proposed approaches. We attribute this to: (1) our data generation assumptions are more realistic and better match statistics of real- world datasets; (2) our risk correcoonn approaches effectively mitigates overfitting, an issue overlooked by previous unbiased methods (Xie & Huang, 2023).
4.3 SENSITIVITY ANALYSIS
Influence of Inaccurate Class Priors. To investigate the influence of inaccurate class priors, added Gaussian noise e ~ (O0 o²) to each class prior k.. The experimental results are shown in Figure 2. We observe that COMES-HL is more sensitive to inaccurate class priors. Overall performance remains stable within a reasonable range of class priors, but may degrade when the priors become highly inaccurate.

---

Published as a conference paper at ICLR 2026
Influence of B. We also investigated the influence of the hyperparameter / for the flooding regu- larization used COMES-RL. From Figure 3, we observe that the performance of COMES- RL is rather stable when is set within reasonable range the mirflickr dataset. During ments, we found that the performance was already competitive by setting / 0 on many datasets. However, the performance may degrade when 8 is set to a large value. This also matches our theo- retical results in Theorem 5, where consistency holds when 3 is not too large.
experi-
CONCLUSION
In this paper, we rethought MLC under inexact supervision by proposing a novel framework. We proposed two instantiations of risk estimators w.r.t. the Hamming loss and ranking loss, two widely used evaluation metrics for MLC, respectively. We also introduced risk-correction approaches to improve generalization performance with theoretical guarantees. Extensive experiments ten real- world and synthetic benchmark datasets validated the effectiveness of the proposed approaches. A limitation of this work is that consider the generation process to be independent of the instances. In the future, it is promising to extend our proposed methodologies to mestance-dependent settings.
ACKNOWLEDGMENTS
WW was supported by the Junior Research Associate (JRA) program of RIKEN. MS was supported by JST ASPIRE Grant Number JPMJAP2405.
REFERENCES
Wonho Bae, Yi Ren, Mohamed Osama Ahmed, Frederick Tung, Danica J. Sutherland, and Gabriel I.. Oliveira. AdaFlood: Adaptive flood regularization. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Ricardo Silveira Cabral, Fernando De la Torre, João Paulo Costeira, and Alexandre Bernardino. Matrix completion for multi-label image classification. In Advances in Neural Information Pro- cessing Systems 24, pp. 190-198, 2011.
Elijah Cole, Oisin Mac Aodha, Titouan Loricul, Pictro Perona, Dan Morris, and Nebojsa Jojic. Multi-label learning from single positive labels. In Proceedings of the 2021 IEEEJCVF Confer- on Computer Vision and Pattern Recognition, pp. 933 942, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei. ImageNet: A large-scale hier- archical image database. 2009 IEEE Conference on Computer Vision and Puttern Recognition, pp. 248-255, 2009.
Thibaut Durand, Nazanin Mehrasa, and Greg Mori. Learning a deep convnet for multi-label classifi- cation with partial labels. In Proceedings of the 2019 IEEF/CVF Conference on Computer Vision and Puttern Recognition, pp. 647-657, 2019.
Mark Everingham, Lue Van Gool, Christopher K. Williams, John Winn, and Andrew Zisserman. The pascal visual object classes challenge 2007 (voc2007) results, 2007. URL http: //wwww pascal-nett www.wok............ org/ cha / /OCC/ voc22007 wroc2007/worsshopp/ http///wwwoooiiieeeeeeeeee
html.
Mark Everingham, Lue Van Gool, Christopher K. I. Williams, John Winn, and Andrew Zisserman.
The pascal visual object classes challenge 2012 (voc2012) results, 2012. URL http:// httt:://ww.. hit.kksshppiiiiee..peee innex..iixxe////// html.
pascal net work. org/ wwtpchaaaaleeeeeeeeeeeeeeeeaeeee /O///////////////////
Wei Gao and Zhi-Hua Zhou. On the consistency of multi-label learning. Artificial Intelligence, 199 (1):22-44) 04.22-44222 2013.
Yi Gao, Miao Xu, and Min-Ling Zhang. Unbiased risk estimator multi mubtiellabeled complementary la- bel learning. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, pp. 3732-3740, 2023.
Yi Gao, Miao Xu, and Min-Ling Zhang. Complementary multiple labels: A correlation-aware correction approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12): 9179-9191, 2024.
10

---

Published as a conference paper at ICLR 2026
Yi Gao, Jing- Yi Zhu, Miao Xu, and Min-Ling Zhang. Multi-label learning with multiple comple- mentary labels. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. to appear, 2025.
Yi Gao, Yuan- Meng, Miao Xu, and Min-Ling Zhang. Data augmentation with regularization for multi-labeled complementary label learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 48(3):2368-2379) 2026.
Saurabh Garg, Yifan Wu, Alexander J. Smola, Sivaraman Balakrishnan, and Zachary C. Lipton. Mixture proportion estimation and PU learning: A modern approach. In Advances in Neural Information Processing Systems 34, pp. 8532 8544, 2021.
Xiuwen Gong, Dong Yuan, and Wei Bao. Understanding partial multi-label learning via mutual information. In Advances in Neural Information Processing Systems 34, pp. 4147-4156, 2021.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning, pp. 1321
1330, 2017.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems 31, pp. 8536-8546, 2018.
Mark J. Huiskes and Michael S. Lew. The MIR Flickr retrieval evaluation. In Proceedings of the 1st ACM International Conference on Multimedia Information Retrieval, pp. 39-43, 2008.
Takashi Ishida, Ikko Yamane, Tomoya Sakai, Gang Niu, and Masashi Sugiyama. Do we need zero training loss after achieving zero training error? In Proceedings of the 37th International Conference on Machine Learning, pp. 4604-4614, 4614, 2020.
Ryuichi Kiryo, Gang Niu, Marthinus C. du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. In Advances Neural Information Processing Systems 30, pp. (684,1684,. 2017.
John Langford. Tutorial on practical prediction theory for classification. Journal of Machine Learn- ing Research, 6(10):273-306, 2005.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes, volume 23. Springer Science & Business Media, 1991.
Shikun Li, Xiaobo Xia, Hansong Zhang, Yibing Zhan, Shiming Ge, and Tongliang Liu. Estimating noise transition matrix with label correlations for noisy multi-label learning. In Advances in 2022.
Neural Information Processing Systems 35, pp.
Tsung-Y Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft COCO: Common objects in context. In European Conference on Computer Vision (ECCV), pp. 740-755. Springer, 2014.
Yong Lin, Renjie Pi, Weizhong Zhang, Xiaobo Xia, Jiahui Gao, Xiao Zhou, Tongliang Liu, and Bo Han. A holistic view of label noise transition matrix in deep learning and beyond. In Proceed- ings of the 11th International Conference on Learning Representations, 2023.
Biao Liu, Ning Xu, Jiaqi Lv, and Xin Geng. Revisiting pseudo-label for single-positive multi-label learning. In Proceedings of the 40th International Conference on Machine Learning, pp. 22249 22265, 2023.
Jingzhou Liu, Wei-Cheng Chang, Yuexin Wu, and Yiming Yang. Deep learning for extreme multi- label text classification. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 115-124, 2017.
Qin Liu, Rui Zheng, Bao Rong, Jingyi Liu, ZhiHua Liu, Zhanzhan Cheng, Liang Qiao, Tao Gui, Qi Zhang, and Xuan-Jing Huang. Flooding-X X: Improving BERT's resistance to adversarial attacks via loss-restricted fine-tuning. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics, pp. (634-5644, 2022a.

---

Published as a conference paper at ICLR 2026
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(3):447-45 461, 2015.
Weiwei Liu, Haobo Wang, Xiaobo Shen, and Ivor W. Tsang. The emerging trends of multi-label learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7955-799 -974, 2022b.
Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pp. 1115-1125, 2020.
Jun-Xin MinnXiang Mao, Wei Wang, and Min-Ling Zhang. Label specific multi-semantics metric learning for multi-label classification: Global consideration helps. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, pp. 4055-4063. 2023.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning- The MIT Press, 2012.
Harish G. Ramaswamy, Clayton Scott, and Ambuj Tewari. Mixture proportion estimation via kernel embeddings of distributions. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2052-2060, 2016.
Timothy N. Rubin, America Chambers, Padhraic Smyth, and Mark Steyvers. Statistical topic models for multi-label document classification. Maching Learning, 88(1-2) 2012.
Masashi Sugiyama, Han Bao, Takashi Ishida, Nan Lu, Tomoya Sakai, and Gang Niu. Machine learning from weak supervision: An empirical risk minimization approach. MIT Press, 2022.
Lijuan Sun, Songhe Feng, Tao Wang, Congyan Lang, and Yi Jin. Partial multi-label learning by low-rank and sparse decomposition. Proceedings of the 33rd AAAI conference on artificial intelligence, pp. 5016-5023, 2019.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-uesd birds-200-2011 dataset. Technical Report CNS-TR-201 1-001, California Institute of Technology, 2011.
Wei Wang, Lei Feng, Yuchen Jiang, Gang Niu, Min-Ling Zhang, and Masashi Sugiyama. Binary classification with confidence difference. In Advances Neural Information Processing Systems 36, pp. 5936-5960, 2023.
Wei Wang, Takashi Ishida, Yu-Jie Zhang, Gang Niu, and Masashi Sugiyama. Learning with com- plementary labels revisited: The coneeted--ompleell--ttee. -taaddo setting is more practical. In Pro- ceedings of the 41st International Conference on Machine Learning, pp. 50683-50710, 2024.
Wei Wang, Dong-Dong Wu, Jindong Wang, Gang Niu, Min-Ling Zhang, and Masashi Sugiyama.
Realistic evaluation of deep partial-label learning algorithms. In Proceedings of the 13th Interna- tional Conference on Learning Representations, 2025.
Hongxin Wei, Renchunzi Xie, Hao Cheng, Lei Feng, Bo An, and Yixuan Li. Mitigating neural network overconfidence with logit normalization. In Proceedings of the 39th International Con- ference on Machine Learning, pp. 23631-23644 2022.
Bin Wu, Erheng Zhong, Andrew Horner, and Qiang Yang. Music emotion recognition by multi-label multi-layer multi instaiiisttncee multi-view learning. In Proceedings of the 22nd ACM International Conference Multimedia, pp. 117-126, 2014.
Xi-Zhu Wu and Zhi-Hor thi-Hua Zhou. A unified view of multi-labe performance measures. In Proceedings of the 34th International Conference on Machine Learning, pp. 3780-3788, 2017.
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in noise learning? Advances in Neural Information Processing Systems 32, pp. 6835-6846, 2019.
12

---

Published as a conference paper at ICLR 2026
Xiaobo Xia, Jiankang Deng, Wei Bao, Yuxuan Du, Bo Han, Shiguang Shan, and Tongliang Liu. Holistic label correction for noisy multi-label classification. In Proceedings of the 2023 IEEE/CVF International Conference Computer Viston. pp. 1483-1493, 2023.
Ming-Kun Xie and Sheng-Jun Huang. Partial multi-label learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 4302-4309, 2018.
Ming-Kun Kun Xie and Sheng-Jun Huang. Multi-label learning with pairwise relevance ordering. In Advances in Neural Information Processing Systems 34, pp. 23545-23556, 2021.
Ming-Kut Kun Xie and Sheng-Jun Huang. CCMN: A general framework for learning with class- conditional multi-label noise. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):154-166, 2023.
Ming-Kon Kun Xie, Jiahao Xiao. Hao-Zhe Liu, Gang Niu, Masashi Sugiyama, and Sheng-Jun Huang. dtass-distribution-ann aware pseudo-labeling for semi-supervised multi-label learning. In Advances in Neural Information Processing Systems 36, pp. 25731-25747, 2023.
Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu, and Masashi Sugiyama. Dual T: Reducing estimation error for transition matrix in label-noise learning. In Advances in Neural Information Processing Systems 33, pp. 7260-7271, 2020.
Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Gang Niu, Masashi Sugiyama, and Dacheng Tao. Rethinking class-prior estimation for positive--unlabeedd learning. In Proceedings of the 10th International Conference Learning Representations, 2022.
Guoxian Yu, Xia Chen, Carlotta Domeniconi, Jun Wang, Zhao Li, Zili Zhang, and Xindong Wu. Feature-induced partial multi-label learning. In Proceedings of the 2018 IEEE international con- ference on data mining, pp. 1398-1403, 2018a
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In Proceedings of the 15th European Conference Computer Vision, pp. 68 83, 2018b.
Min-Ling Zhang and Jun- 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 Transac- tions on Knowledge and Data Engineering, 26(8):1819 1837, 2014.
Yivan Zhang, Gang Niu, and Masashi Sugiyama. Learning noise transition matrix from only noisy labels via total variation regularization. In Proceedings of the 38th International Conference Machine Learning, pp. 12501-12512, 2021.
Jing-Y Yi Zhu, Yi Gao, Miao Xu, and Min-Ling Zhang. ComRank: Ranking loss for multi-label complementary label learning. In NeurIPS, 2025.
Yilun Zhu, Aaron Fjeldsted, Darren Holland, George Landon, Azaree Lintereur, and Clayton Scott. Mixture proportion estimation beyond irreducibility. In Proceedings of the 40th International Conference on Machine Learning, pp. 42962-42983 2023.
Yue Zhu, James Kwok, and Zhi-Hua Zhou. Multi-label learning with global and local label correlation. IEEE Transactions Knowledge and Data Engineering, 3016):088111044 2017.
13

---

Published as a conference paper at ICLR 2026
THE USE OF LARGE LANGUAGE MODELS (LLMs)
We used LLMs check the manuseript for typos and grammatical errors.
A MORE DETAILS ABOUT THE ALGORITHM
A.I ALGORITHMIC PSEUDO-CODE
Algorithm COMES-HL HL and COMES-RL
Input: Multi-label classifiers g, PML dataset D, epoch number Tiux, iteration number I
1: for = 1, 2, .... max do
2: Shuffle D;
3: for 1..... Iax do
4:
Fetch mini-batch Dj from D;
5: Forward D and get the outputs of g:
6:
if using the COMES-HL algorithm then
Calculating the loss based Eq. (8): else if using the COMES-RL RL algorithm then Calculating the loss based on Eq. (14): 10: end if
7:
8:
9:
Update g using stochastic optimizer to minimize the loss;
12: end for
13:
end for
Output: g-
A.2
CLASS PRIOR ESTIMATION
any off-the-shed mixture proportion estimation algorithm estimate the class pri- ors (Ramaswamy et al., 2016; Garg et al., 2021; Yao et al., 2022; Zhu et al., 2023), which are mainly designed estimate the class prior with positive and unlabeled data for binary elassification. Specifically, we generate negative and unlabeled datasets according to Eq. (6) and then apply the mixture proportion estimation algorithm. The algorithmic details are summarized Algorithm 2.
We
Algorithm Class-prior Estimation
Input: Mixture proportion estimation algorithm A, PML dataset D.
1: for k E y do
2: Generate unlabeled and negative datasets according to Eq. (6);
3: Estimate the value of (1 π&) by using A and interchanging the positive and negative
classes:
4: end for
Output: Class priors my )).
B PROOFS
B. PROOF OF LEMMA
According to the definition of PML, when s, = 0. the j-th class is impossible to be relavant label,
and we have p(j & 1x, S, 0) p(j Y|s, ss 0) 1. Therefore, on one hand, we have
p(a|s, 0.J Y) p (a]ss) 0) pli $ Y|
p = 0)
plj $ Y|5, = 0)
On the other hand, we have
p0228 Y) p(alj $ Y)p(s; = 0 ()
p(ar)j Y),
p(s; = 0lj $ Y)
14

---

Published as a conference paper at ICLR 2026
where the second equation is due to p(sy 0/æ, Y) = p(s, Olj $ Y) Py-
The proof is
completed.
B.2 PROOF OF THEOREM 1
1 1
Rg)(g)
((a,))
9 2 (2)
e (g) (x). 11)pp(,) Y) dz
j-1
Em 8 (g) (z) 91) pla, Us)p (Y' y3) dæ
(gg (a:) p(. Em-rg p (Y' ar, U3) dx
( (z) pl., da
((g (z)) (),( = dx + ب ( (z) (z. My 0) dæ
[()) (x)) 1) p(x) de أ-- (g) (z), 1),(,, 0) dæ
9 j-1 8 [gg (z) (2, = 0) dx
((g) (x) p() + S Σ 19
(e -
(z) 1)) (1 1y) 0) da
(())
- ( (m) 1)
Ep(cele, =0)
1 ا--- (1 my) (c (z)) ( (a) 1))
E l (g) (m)) 1)
Σ (1 (1-m))((())()))))))))))) (gg (m)
+ Bp(oel,,
where the last equation is by Lemma 1. The proof is completed.
B.3 PROOF OF THEOREM 2
Let
(9)))) { (Du, Dj) Di) l (g) (z)
Σn nJ ki=1
Tr
8 gi (a!)) .1) 0}
and
Dj (g,)) = (Du. 1 n
( e (g) (z.")
1-
{(g3 (x))) .1) < 0
ng
denote the of data pairs with positive and negative empirical losses, respectively. Then, have the following lemma.
Lemma 2. The probability measure of D (g5) can be bounded as follows:
-2a²
(0) < exp Cf/n+ (1 (1
(18)
Proof. Let
p (Dv) p(TH)p((s) ... p(x and p (D,) = p(ar()((ac)) ... ((((h))))))
denote the densities of Di and Dj. respectively. Then, the joint density of (Du, Dj) is p (Du, p (Du) (()))
15

---

Published as a conference paper at ICLR 2026
Then, the probability measure of 5 (gr) can be expressed
P P (g))) S ((D7 p (Du.
(D). Dj)
p (Du. Dj) dæy dæy da U dæy dxž day
When an instance in Du is replaced by another instance, the value of Σ (gj (x /n (1
TTy - l Øj (x?)) 1) /n, changes no more than Cz/nn When an instance in Dj is replaced by
another instance, the value of E (g) (æ.) 1) /n (1 (1-68 π,) Ei (9) xx)) (ee)).) /nn changes
no more than (1-ar)CCe/1) Therefore, by applying the McDiarmid's inequality, we can obtain the following inequality:
( 2 e { (z,)) 1)
1- Jj - e (33) (e.)..) 2a) a
Ty T [g (x),
n2
-2a² n.) (2 2
exp
Then we have
(2)
(9h))
=p
e (g) (z.) 1) 1)
1 1- Ty
"
gi x .1 x0)
11 i==1
nj
k=
<p
i- (g) (z!)) 1)
k
gj (x)) .1) E -1) (g) 1)] a
n
nj
R-1
-2 Ct/n+ (1 ) )²0 C
exxp
/nj
which concludes the proof.
Then, provide the proof of Theorem 2.
Proof of Theorem 2. To begin with, we have
((( - Rg( = -E (((()())) ((((9) > 0.
Besides, we have
1 e ( (z.)) .1)
1- T.
my
8 (g) x
1-1
n
1--
1 1=1
( (or (x.)) 1)
+
1 1- n.
n
8 g
x
nj
-=
C2
16

---

Published as a conference paper at ICLR 2026
Then,
E
[g) gg)
Rg) (
E
1 Σ (DDDD))ED, (gg)
- e (os (x))
(z)) .1) 1- T 1-TT
Σn e f(0) (o!) .1]
9
n2
Σ" l {9) (zx²) 1) 1 1- m Fi Σ
F i- e (()) (o.) (0)) :1))) p p(uu: (DDUD D2)
( | (gz ( - (15 (1t)
TH
sup
1
(Du.D))eD] ( (0z)
1 Σ i= e (e)) (z.²). :11
- Σ ==1
m. l {0) (z!) (et):.)) 11)) (Do.)))007(5)
p (Du. d (Du. D,)
njj
1 19
2==1 (4 2T, (2) (g:))
9
1
-2a²
9 j= (4-2T,) 2x exp
Ct/n++ + (1 - TT C3
1 Ee
ạ - (4- -r
which concludes the proof of the first part of the theorem. Then, we provide an upper bound for (g) - (9) When an instance in Du is replaced by another instance, the value of (f) changes at most C2 n: when an instance in D, is replaced by another instance, the value of R (g) changes at most (2 2n,,) Ce/(g)))))) By applying McDiarmid's inequality, we have the following inequalities with probability at least 1 - 8/2:
E (9) (g) < CN
In (2/5)
19
(2 2TT))ee
In (2/5)
2n
j=1
q
2ng
In (2/5)
(2 2n²)
IIn (2/5)
(g) - E R
< CW
2n
q
2nj
where we use the inequality that Va + b vā Vb. Therefore, the following inequality holds with probability at least - 6:
E
[
R((( E <CN
In (2/8)
(2 22TT)
In (2/5)
2n
2n;
Finally, we have
Rh(g)) R(((g)
(((g)) E (9)
E (f((
(g)
(g( E R (g)
+ |E [ [1)
R1
K((g) E
(9)
+ +E [n(9)
R(i(g)
1
-20²
(0-2x,)C.
Inn (2/8)
In (2/5) 2n
(4 (4-2 2x exp
+ Ca
9 1111
C2/n+ (1 TT) C3)0///
V 2ng
q
-
(2 (2- 22-2
In (2/0)
in (2/8)
(4 2T-
CCN
9
9
2ng
2n
which concludes the proof.
17

---

Published as a conference paper at ICLR 2026
B.4 PROOF OF THEOREM 3
Definition 1 (Rademacher complexity). Let Xn = fæi...... Ln. denote n i.i.d. random variables drawn from a probability distribution with density p(x). (gx X RJ denote class of mea-
surable functions model outputs for the k,-th class, and a = (01, 02 -n ) denote Rademacher variables taking values from {+1, -13 uniformly. Then, the (expected) Rademacher complexity of G is defined as
Rn (9) Ex,, Eo
sup > == (z,) mgeg
(19)
We also introduce an alternative definition of Rademacher complexity:
Ry Ry (9) = -Ex, E.
sup 9
Σ 1 o:gg(az))
(20)
Then, introduce the following lemmas.
Lemma 3. Without any composition, for any 9, we have Wy (99) > Rm.p(g). Ifg is closed under negation, we have Hy Rn, = Rn)((g).
Lemma 4 (Theorem 4.12 in (Ledoux & Talagrand, 1991)). If R x {0, - R is a Lipschitz continuous function with a Lipschitz constant Le and satisfies Vy, E(0, y) 0, have
(e R.,
where l o G (Co g.. G).
Then, we provide the following lemma.
Lemma 5. Based on the above assumptions, for any 8 > 0, the following inequality holds with probability at least 8:
sup 96
R(( -R
&
ALe
DY n. (9) + 8(1 - TT)Le
R Ryyp, (g)
9
q
j=1
In (1/5)
(2 2T, C
In (1/5)
j=1 (4 2Ty Ce4, C
2n
j=1 g
2ng
Proof. When an instance in DU replaced by another instance, the value of E [ ne (g) changes at most Ce/n; when an instance in Dj is re- R9) changes at most
sup ou
placed by another instance, the value of suPpr..a...... E [ (2 2T, Ce/(gn)). By applying McDiarmid's inequality, have the following inequality with probability least 1- ò:
Ratoo||
sup
E
(g((g)
- -R((9)
E
sup 91,92....9,.9
E
91,92
<CeV
In (1/0)
19
(2 - Ce
In (1/8)
(21)
2n
1=1
q
2nz
For ease of notations, let D = Du UD:
UD, denote set of all the data. We have
E
sup
[
ET (
P6100
sup
91 1.9.......99
<E
D
sup
Ri D)
-ii D'
(22)
91.92....99E
18

---

Published as a conference paper at ICLR 2026
where the last inequality is deduced by applying Jensen's inequality twice. Here, R (g: denotes the value of (g) on D. We introduce {(z) ((z)-E(0) and we have {(z))- ((2)) {(21)(()))))))) (22)) It is obvious that ((2) is a Lipschitz continuous function with Lipschitz constant Le. Then, we have
Rfig:: (D) - - (g: 1
1 Σ
n
8 (1) (zx)) .1) - J.
(a!))
1)
i-1
Rj
9j
1- Tj
1=
x
n2
1
9j [
0)
my
(g) .0)
y
1)
- Tt.
Σ
a ,1)
93
R2j
1- Jj Σ -=
93
x
Rij
.0)
1 1- kj
(2.) .0)
8
9/
_
gj
mm
1=1
qm
1
[j
(x.")
Σ -=1=1 i=1
i Oj
xx
U'
.1)
1
i 95
11
1- Tt
py
1 95 (x?) 1)
1=11
m
i-
[x] .0)
1- 1- k
(9) (x .0)
(23)
qn
i=1
qnz
====
where the inequalities are due to the triangle inequality. Then, by combining Inequalities (22) and (23), it a routine work (Mohri et al., 2012) to show that
E
D.F
sup
(g:
l :D'
2 1
DV (1 9) + ((-TTy) 19
N, n2 (Eo g)
D
9
q
1=1
4L
DY m. (9) + 8(1 Dt)L Li
1"
B m, p. (9)
==j=1
--j=1
9
q
4hg
Rg) + 8(1 - nT,) Lu
1
R p. (9),
(24)
j=
where the second inequality is due to Lemma 4, py denotes p(æls, = 0). and the last equality is due to Lemma 3. By combining Inequalities (21) and (24), we have the following inequality with probability at least 1 - 5:
4L E 1=1 <
+ 8(1 F. Le 5 Rm,
sup
E
-R((g)
-)=1 Rn Rs (9)
01.02
q
4
In (1/8)
(2 - 2n Ct
In (1/8)
+ Ci1
17
(25)
2n
j=
2nl
19

---

Published as a conference paper at ICLR 2026
Then, have the following inequality with probability at least 1 5:
R((g) (g)
sup
Rfi(g) - E (9) + [
- Rff (
sup
91.92.m-9 9gg
RH(g) E [
E (R((((
R2 (g)
sup
sup
91.92
1
(4 )Tt) Cr4 Cey/
Inn (1/6)
(2 (2-2T;) 2r
In (1/6)
9
2n
j-1
2n,
4L8 19 +
Rm.p (g) + 8(1 - 8(1-T;)L4
R Ray P3 (9).
9 j=
where the second inequality is due to Inequalities 25 and The proof is complete.
Then, we provide the proof of Theorem 3.
Proof of Theorem 3.
Rgj( (fi) (gn) (un) R (g + R R((
< Hi (ğH) (án) + (9 (g
< 2
Rf(l)) R9(9)) sup
By Lemma 5, the proof is complete.
B.5 PROOF OF COROLLARY
Lemma 6 (Theorem 4 in Gao & Zhou (2013)). The surrogate loss R is multi-label consistent
w.r.t the Hamming or ranking loss RO-1 if and only if it holds for any sequence (ge) that if R (g)
R then R (g) R. Here, Rd* inf, Re and R* inf, R (g).
Lemma 7 (Theorem 32 in Gao & Zhou (2013)). If E is convex function with f' y) < 0, then Eq. (2) is consistent w.r.t. the Hamming loss.
Then, provide the proof of Corollary 1.
Proof of Corollary Since the proposed risk in Eq. (5) is equivalent to the risk in Eq. (2), it is sufficient prove that for any sequence (g:) that if Rfgg:)) Rét then ( R 1
20

---

Published as a conference paper at ICLR 2026
B.6 PROOF OF THEOREM 4
R (g) = -Bp(e.)) Ersscceen I[U # yale 9j(x)= 9x(2)), V/j - yk + +1
2
Ey Σ Eisjekeo T(y ya)e gg(2r) 91 (x(x)) - + 1
p p Y) Y)dæ
2
/Erstake - Wa=0 =0 Ex (usiie)) I[u; * yx)e gj(xz) - gx((r),
V1 yv + 1
(a, Vy u&) (Y' (x,, M1. Wa) dxc
-s [Einsseees Wy -m I(ys yale g5(xx) -gxx)) リ - + 1
2
(xx, Vý. 4k)
Σ -x-rrtus (V'l Uÿ Me) dæ
EEestake En,-o E -0== I(yy * y g5((x) gx(xx, Y/ - +
p (2x, Uo yu) dæ
2
Evejekeo (fe(o,(t)- (x) (x)))))))><))))))))))))))))))>)) 0) p 1, 3) O, uk 1)dx
[(g)(z))
((0)(t)) - gx(()), 1) (xx,,) 1, 1, 0) dæ
EEEjekes (fecos(e) (x)
-o(l))())))(()00)))) (,, 0) p Uy 0, 2) 0)) dæ
+ (( - (x(()) 1)) 0) p(x, B/ = yk 0)) dæ
-EieEkee (felo)(e) (
(x))), 0) (1 (1),,))(( (x|y) 0) dx
[[g](x) -gx 1) 11-))ppp))))) = 0) dæ
(e(og(()) (1:0)--aae (x)x)) 0) (
- (x)) 1)) p (2x = 0, = 0) ca
Σ Eiejekeo ((1 Nyy E Ep [e (g) 91 (z), 0)]
+(1 Thk Epp 0) (z) (x)) Mp(y/ O. yk 0))
su (x),,0) EE ((1 TT) 12 [0
+(1 mh) Eppltsss (g) (a)) gu (z), 1)] M Mp(1 yh 0))
where the last equation is by Lemma 1. The proof is completed.
B.7 PROOF OF THEOREMS 5
Let D == DDDUD ... D, denote the set of all the data used in Eq. (14). We introduce
D (g) - (D) $). and (g) { ( = $)
Then, we have the following lemma.
Lemma 8. The probability measure of
D (g) can be bounded as follows:
-2.2
P P < exp Σ4 (1-
(26)
21

---

Published as a conference paper at ICLR 2026
Proof. When instance from Dj is replaced by another instance, the value of (g) changes at most (1 - <z) 1)Ce/ng. Therefore, by applying the McDiarmid's 's inequality, we can obtain the following inequality:
p - + Enejeken Mp(y, O, yv -0) 27) exp
-272 Σ 7T) - 1)2C2/n)
Then, we have
2 (g) =p (g) < <B)
(g)
Σ 1Ejckey
My(y; 0, yk = =0)
<p
A (g)
Σ LEjckeg
Mp(Uj O, yk - 0) + (g)g)) -7)
<p
-2y²
< exp
(1 (1-1]1])((())) (g) 1
which concludes the proof.
Then, we give the proof of Theorem 5,
Proof of Theorem 5. To begin with, we have
E | | Evegebey Mply, 0. = RR E [(Ri( Af(( 0.
Besides, we have
(g(9) & Col9 1) Σy (1 -Ty).
Then,
E
(f((g) Ei
Mplyj = 0, yk = 0) -)- (g)
E (g) - -
((A((O) -
( +3 p (D) aD
DeD (g)
(28 + 2R((11) 1 (DE0-(9) p p aD
sup
(e0-(9)
(23 + (
P (g)T
sup DED- (0)
-27² Σ (1- 1)2C%//
& (23 2Cr(9 1) E₁ (1- πT)) exp
which concludes the first part of the proof. Then provide upper bound for When an instance from Dj is replaced by another instance, the value of ( - || ||
T changes most (1 xq)( 1)Cr/ng. Therefore, by applying the McDiarmid's inequality, we have the following inequalities with probability at least 1--8 5/2:
In (2/6)
R((()) R
Σ (1 TT)(a- 1)
19
2n,
In (2/0)
E [4(
p (g)
1i=1 (1 TT) 1)
19
2n,
22

---

Published as a conference paper at ICLR 2026
Therefore, we have the following inequalities with probability at least 1 6:
in (2/0) 2ng
(g) - E [ & < (1- Tz>la 1)
Finally,
(g) Σ L
Mp(yj 0, yk 0) - -) (g)
(g(g) E (
+ E (9) -E Mp(Uj 0, Vv 0) R9(
(g) (9(
|| + E [
-Eesjckso Mp(y; 0, yk 0) (g)
Inn (2/0)
0 j-11 (1 (1-T1))) (1) (1-T))a
1) 1 2nl
-2n2 ン (1 (
+ (23 2Crla 1) Σソ 19
(1 -1- (1-x,) exp
(27)
which concludes the proof.
B.8 PROOF OF THEOREM 6
Lemma 9. Based on the above assumptions, for any 8 > O, the following inequality holds with probability at least 8:
Rk(9)= + Ejen Mplyj O, 0) - - (9) & (28 +Cz(a - 1) E,_ (1xr)) A 91.82....9.59
sup
In (1/0) n1
T En (1 (1-TT()) 1
+ Σ 4belg 1)(1 k,)) Rs (9).
(28)
Proof. When an instance in Dj is replaced by another instance, the value of (9) it (g) changes at most (1 - Tg){g - 1)Ca/ng. Therefore, by applying the McDiarmid's inequality, we have the following inequalities with probability least 1 1 8:
sup 91 92 Sggg
sup 91 91.92.....4 BgEg
R [g) - -R - E
sup 9,E
E
R (g) - -RACo)
IIn (1/8)
j-1 (1 (1- T (1-mm(( - -
(29)
Then,
(9) - RRCool
E
sup
EB [
E
sup
91 G
R D) - R :3))
x E
D.D
sup 91.02----9EG
(30)
where the last inequality is deduced by applying Jensen's 's inequality twice. Here, R (g: D) denotes the value of Re (g) on D. Then, introduce the following lemma.
23

---

Published as a conference paper at ICLR 2026
Lemma 10. Ift: IR x {0, - R is a Lipschitz continuous function with a Lipschitz constant Lg and satisfies Vy, E(0, y) = 0, we have
Ry n
(t (g 9)) & 4T.
where f o ((g - 9) - ( (وj 9k) 183 E 9 E g).
Proof.
Ry n. (f (g 9))
= 22 m. (g)
where the first inequality is by symmetrization (Mohri et al., 2012) and the second inequality is by Lemma 4. The proof is complete.
Therefore, we have
(2 D) - R (g: Bi}
| D) - _ - ( -
PR (g: D) A D
Σ Lejcken
- Σm (e (1)(ar))) - mx(a))).)) (n(()) - (g)(az)) ga (20 )o4))
nj
1 - Th E
( (g)(x()) (x()), (2)((a))) sx(a) ), ).1))
1k
1
1
(a;)) 0) ( - E (E(g)(=)) (x , 1) - (0s(at)) cx ),
Jjj
_",
(s)(ar") - 00)
1Ejckeg
i==
Σ lEjekeq
T0kk
1- Tjj
( (9/(z=)) ox(==), 0) - (9,(x²²) gu(2))) ) 0))
Lngj<keg
Zi==
Σ Ei
1 Th E,h (E(g)(=))) (x(x), i (o5(xx") (x 11) (31)
n&k
where the inequalities are due to the triangle inequality. Then, by combining Inequalities 30 and 31, it is a routine work (Mohri et al., 2012) to show that
E
sup
[ R (
R
91.92......o
9,E9
(q 1)(1 N, R,) iPs (eo (g - 9))
4Le(g 1)(1 nT) y9 .P. (g)
4L.(q- - 1) - MT RRn, . (g)
(32)
where the second inequality is by Lemma 10 and the last equality is by Lemma 3. By combining Inequalities 29 and 32, we have the following inequalities with probability at least - 8:
(g)
R (g)
sup
In (1/8) n,
T9)(a- -
Li_ 4Le(g 1)(1 Ry)Rn (9).
(33)
24

---

Published as a conference paper at ICLR 2026
Finally, we have the following inequality with probability at least 1 - 8:
(g) + Σ jeck Mp(y, = 0. yıs 0) - (
sup 91.82
sup
(g) + Σ Lijck jcc Mplys = 0, ys 0) E. R (g)
+ E.
R (0)
R
- (g)
(g) + Σ jzck Mp(y, 0. yh 0) E Ri (g)
E [
Rf(
sup
sup
91.92...996
91.92.--990 9.69
In (1/5)
23 + 2Cr(1 - Σ (1- nTz) A' Σ (1-=,)(4 1-)(a-1)00100000 1)C
nj
+ Σ j-1 4hrlq- 1)(1 - m,)9 (9),
where the last inequality is by Inequalities 33 and 15. The proof is complete.
Then, we provide the proof of Theorem
Proof of Theorem 6.
(gR) - R (gk) = (ĀR) Ejer Mp Mp(y, 0, 1/ 0) (#n) + (gn) Ri (gR) + (
Ljech Mp(uj = 0, y/ 0) 11 (9
(ğR) + Σ jzc Mp(u; = 0, 1/s = 0) (ğR) + RR (g - EEyek Mp(y; = 0, = 0) -R (g
2 sup (g) + ΣE, Mp(yj = 0, yn 0) - (1)
91 01-92-09.EG
Then, based Lemma 9, the proof is complete.
B.9 PROOF OF COROLLARY 2
Lemma 11 (Theorem 10 in Gao & Zhou (2013)). If is a differentiable and non non-increasing function functionnno such that Vy, (0, 3) < and f(z, v) + E(-2,y) M, then Eq, (4) is consistent w.rl. the ranking loss.
Then we provide the proof of Corollary 2.
Proof of Corollary 2. Since the proposed risk in Eq. (5) is equivalent to the risk in Eq. (4), it is sufficient to prove that for any sequence {g:} that if (g))) - R then R R O
C DETAILS OF EXPERIMENTS
C.I MORE DETAILS OF DATASETS
For synthetic datasets, we consider two data generation processes. In case-a, irrelevant labels are flipped to candidate labels independently, which is the assumption used Xie & Huang (2023). This strategy is common in learning with noisy labels (Han et al., 2018), where PML is a special case of MLC with noisy labels (Xie & Huang, 2023). case-b, we assign non-candidate labels in a class-wise manner. For each class, we randomly sample a fraction of the training data and assign that class as a non-candidate label. This data generation process corresponds to the assumption proposed in this paper. We use this process to confirm the effectiveness of our proposed method under this assumption. Additionally, we selected high flipping rates to evaluate the effectiveness of proposed methods challenging datasets with high noise rates since real-world datasets have low noise rates. In this paper, we set the flipping rate in Case-a to be 0.9 and and the sampling rate in Case-b to be 0.1.
25

---

Published as a conference paper at ICLR 2026
C.2 BASELINES
We evaluate against five classical baselines commonly used in PML/CML learning. (A) BCE: uses the given candidate label the cross-entropy target. (B) CCMN (Xie & Huang, 2023): treats PML as multi-label classification with class-conditional noise, relying on a noise transition matrix. (C) GDF (Gao al., 2023): proposes an unbiased risk estimator for multi-labeled single com- plementary label learning. (D) CTL (Gao et al., 2025): introduces risk-consistent approach by rewriting the loss function. (E) MLCL (Gao et al., 2024): estimates an initial transition matrix via binary decompositions, then refines it with label correlations.
D INSTANCE-DEPERE
CASES
The current literature on partial multi-label learning (PML) and complementary multi-labe learn- ing (CML) assumes that label generation independent of instances (see Table 1). Following previ- ous work, we also consider the instance-independens case. It is very challenging design consistent methods for instance-dependent cases due to the difficulty of estimating mnstance-dependerr genera- tion processes, far know from the literature weakly supervised learning. In future work, we will consider developing instance-dependent methods with strong theoretical guarantees.
26


Reviews:
[{"review_id": "6HXFijkWAp", "reviewer": "Reviewer_bJe9", "summary": "This paper addresses multi-label classification under inexact supervision task, proposing a unified framework COMES for partial multi-label learning (PML) and complementary multi-label learning (CML). Existing methods require estimating label generation processes or rely on uniform distribution assumptions. The paper assumes that candidate labels are generated by querying whether an instance is irrelevant to each class, and designs first-order and second-order unbiased risk estimators. The first-order strategy decomposes the problem into multiple binary classification problems using Hamming loss, while the second-order strategy takes label correlations into account using ranking loss. Theoretically, the paper proves consistency and derives convergence rates for both Hamming and ranking losses, improving generalization through absolute value wrapping and flooding regularization. Experiments validate the effectiveness on six real-world and four synthetic datasets, with COMES significantly outperforming baselines including CCMN, GDF, CTL, and MLCL in most cases.", "questions": "1.\tIs the conditional branch error in Algorithm 1, line 8 a typesetting issue or an actual error in the code? Does this error exist in the algorithm implementation, or is it a description error in the main text?\n2.\tWhat is the reason for using different network architectures (MLP and ResNet-50) in experiments? Does this design affect the fairness and comparability of experimental results?\n3.\tHow should first-order and second-order strategies be chosen in practical applications? Has the author considered designing a mechanism to automatically select one strategy or a weighted combination of the two strategies based on dataset characteristics, such as label correlation strength or dataset size?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe unified perspective on treating PML and CML as equivalent problems is interesting.\n2.\tThis paper not only proves consistency of risk estimators but also derives convergence rates for estimation errors. It establishes generalization bounds by Rademacher complexity analysis, and proves that minimizing the corrected risk estimator can achieve Bayes risk.\n3.\tThis paper covers different types of datasets (images, audio, biological information, etc.) with reasonable settings. Sensitivity analyses evaluate the impact of inaccurate class priors and hyperparameter β, and ablation studies validate the necessity of each module.", "weaknesses": "1.\tAlgorithm 1 contains an obvious error in line 8 of the pseudocode. The conditional branch \"else if using the COMES-HL algorithm then\" should be changed to COMES-RL rather than COMES-HL. \n2.\tThis paper provides a detailed introduction to first-order and second-order strategies and validates their effectiveness through experiments. However, it does not explain how to reasonably select or combine first-order and second-order strategies in practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8drKhebgIW", "reviewer": "Reviewer_aB8Q", "summary": "The paper addressed the Partial and Complementary multi-label learning in a unified way. The authors proposed unbiased risk estimators for hamming and ranking loss under inexact supervision, and provided consistency convergence guarantees. In comparison to existing approaches, the proposed method does not rely on accurate estimation of data generation process. They also showed the effectiveness of the framework through empirical results.", "questions": "1. In figure 2, the experiments are done with different sigmas for class priors. Why not actually modify the flip rate in case A for example, and then evaluate?\n2. The average precision of mirflickr stays the same as you increase sigma. Why? \n3. This paper consider data generation process independent from the samples. Shouldn’t MLCL perform better because it is estimating the data generation process from the samples? Can you elaborate? Because I would assume that estimating the data generation process based on the knowledge of the actual samples should be better than independent data generation process (in this case, flipping the negative labels to positive labels with prob 0.9). \n4. Theorem 4 assumes that $l$ is symmetric but in reality, the used loss binary cross entropy, is not symmetric. Am I missing something?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The problem of PML and CML have been addressed separately but this paper provides a unified framework to address the two settings. The authors proposed the method which generalize the label generation process (instead of naively assuming the process) for risk estimators.\n\nQuality: The methodology demonstrates technical soundness. The assumptions and lemmas have extensive proofs and details. Based on the experimental section, the method seems to perform well empirically too.\n\nClarity: The paper is mainly easy to follow and has proper motivation of the problem setting. \n\nSignificance: The paper makes substantial contributions to the area of multi-label learning. I think the results are significant (the theoretical and experimental, both).", "weaknesses": "1. Although the method is more general than prior work, it depends on a strong assumption used in Lemma 1, which results in the independence of the data generation process from the samples. (Authors mentioned this in the paper as well)\n2. I am particularly focused on the result of the Lemma that $p(x|s_j = 0) = p(x|y_j = 0)$. This assumption seems to be a very strong signal for negative labels. This implies a perfect annotation process for 'irrelevant' labels. The proof of the lemma uses another assumption: $p(j \\notin Y | x, s_j = 0) =p(j \\notin Y | s_j = 0). $, which has not been explained in the paper. \n3. The experimental section could be improved a lot. The authors have done experiments but the rationale behind case A and case B is not mentioned. Why choose this particular method of generating the labels and why not some other method (or different \\tau)? \n4. For the effectiveness of the framework, and the impact of the data generation process, there is a need for more experiments. What would be the effect of changing the dataset size for training?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o6wX0gVgp4", "reviewer": "Reviewer_oQbS", "summary": "The paper proposes the COMES framework for partial/complementary multi‑label learning (as the paper points out, these settings are formally equivalent). The paper focuses on deriving two new unbiased losses for Hamming loss (COMES‑HL) and ranking loss (COMES‑RL) under the setting with the assumption that each label has a different but constant (not instance-dependent) probability of being in the candidate set, while being in fact irrelevant for the sample. The authors prove consistency with finite‑sample bounds for both derived losses and perform experiments on six real‑world PML datasets and four synthetic ones, and compare against 5 different algorithms across Hamming loss, ranking loss, one‑error,  coverage, and AP.", "questions": "Please refer to the weakness", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper sounds and is easy to read.\n- Clear theoretical contribution: unbiased estimators with finite‑sample bounds for both Hamming and ranking loss.\n- Useful relaxation of assumptions compared to previous methods.", "weaknesses": "- The biggest weakness of experiments is that they assume the priors are known, but the problem of estimating priors is, in this case, complex, and the problem may not be identifiable in some cases.\n- It is not clear what dataset is used for Figures 2 and 3; comparison with baselines could also be added there.\n- While new losses relax the assumption on uniform distribution, calling them general is an overstatement for me, as obviously, the assumption on constant p_j is still strong and likely untrue in many real-world cases.\n- \"This data generation process coincides well with the annotation process of candidate labels. For example, when asking annotators to provide candidate labels for an image dataset, we\ncan show them an image and a class label and ask them to determine whether the image is irrelevant\nto that class. This is often an easier question to answer than directly asking all relevant labels, since\nit is less demanding to exclude some obviously irrelevant labels.\" - depends, if there is a lot of labels, is it really better to list irrelevant ones? Not sure about that, but I recall that datasets used in experiments were actually created using crowdsourcing, and candidate label sets were created by taking the union of all assigned label sets. Are there any datasets created in this manner?\n- Experiments lack a good description of datasets and baseline methods (also in the appendix).\n\"We evaluate against five classical baselines commonly used in PML/CML learning.\" - Only classical? None of it is SOTA? What about the assumption these methods are using, do they also require priors? Also, what worries me is that from those baselines, the simplest BCE performs the best most of the time. This makes me question baseline choice and correctness of presented experiments.\nA comment how assumptions of the method match data annotations of benchmark datasets would be nice. Also, are all the real datasets indeed real? I might be wrong, but I think some of them are actually created synthetically (yeast ones?). Limited information on data splits/repetitions etc.\n- NIT: There are multiple metrics in MLC called \"coverage\", I assume the authors use the minimal ranking coverage metric here because the stated lower is better, but it would be nice to have metrics defined in the appendix.\n- NIT: It's not clear from the main text what is Case-a and Case-b in Table 3\n- NIT: When I use the code link, for every file I select, it says: The requested file is not found. Basically, the code is not accessible at the moment of writing this review.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hQ6T4vYZDY", "reviewer": "Reviewer_Yr8e", "summary": "This paper addresses the partial/complementary multi-label learning problem. By proposing a consistent multi-label classification\nunder inexact supervision framework called COMES, this paper designs two risk-consistent estimators w.r.t. two classic multi-class classification losses, i.e., the Hamming loss and the ranking loss. Compared with previous works, the proposed estimators neither require estimating the generation process of candidate or complementary labels nor rely on the uniform-distribution assumption. In the theoretical parts, this paper derives the generalization bounds for the proposed estimators (COMES-HL and COMES-RL). In experiments, the proposed estimators are evaluated on both real-world and synthetic PML benchmark datasets, achieving lower errors and higher average precision compared with previous methods.", "questions": "- In Eq. (13), there is no negative loss term to induce overfitting. Why is the flooding regularization technique necessary?\n- Why do Eq. (8) and Eq. (14) use different strategies to avoid overfitting?\n- Just out of curiosity, why are the proposed methods named first-order and second-order strategies when no derivatives are involved?\n- How do the proposed methods perform under estimated class priors?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- This paper is overall well written and easy to follow.\n- The proposed methods are theoretically inspired and proved to be consistent. Although I did not check every detail in the proof, the theoretical results seem sound and reasonable.\n- The proposed methods neither require estimating the generation process of candidate or complementary labels nor rely on the uniform-distribution assumption, which is a significant advancement compared to existing methods.", "weaknesses": "**Major**\n- In Theorem 2, if the non-negative $\\alpha=0$, according to (9), the estimator is inconsistent because the bound becomes independent of $n$. For example, if the classification problem is easy enough so that $g_j(x)$ predicts every $y$ exactly, then theoretically, we have $\\pi_j\\mathbb{E}\\_{p(x|y_j=1)} [\\ell(g_j(x),1)]=0$. Nonetheless, I believe that the estimator can still be proved consistent in such a corner case, because the classification problem becomes very easy now. I hope the authors could discuss this case in further detail so that the theoretical results can be more rigorous and complete.\n- Similarly, in Theorem 5, it is also possible that $\\gamma=0$ for easy classification problems, making the bound independent of $n$.\n- Another of my major concerns is about the fair comparison in the experiment section. In Figure 2, the inaccurate class priors affect the performance of COMES. Even for the relatively robust COMES-RL, under a slight noise $\\theta=0.1$, the average precision drops unacceptably. For example, on mirflickr, mAP drops from 0.818 to approximately 0.80, and on music_style, mAP drops from 0.732 to below 0.70, which makes COMES-RL perform worse than many of the compared methods in Table 2. Therefore, I wonder if these compared methods also use the true class priors in Table 2. If so, from my perspective, an additional comparison under estimated class priors may be more persuasive.\n\n**Minor**\n- In Eq.(8), an absolute value function is used to prevent overfitting. Further explanations are needed to elaborate on how and why this approach works. \n- In Section 3.1, the generation procedure of non-candidate labels is class-dependent instead of instance-dependent. I think this point should be emphasized in the context.\n- Line 250. \"$\\sup\\_{g_i \\in \\mathcal{G}}\\\\|g\\\\|_\\infty$\". Should it be \"$\\sup\\_{g_i \\in \\mathcal{G}}\\\\|g_i\\\\|\\_\\infty$\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mBXSqsPfEx", "reviewer": "Reviewer_fd9d", "summary": "This paper proposed the consistent approaches to handle both partial label and complementary multi-label problems in a unified way, with two unbiased risk estimators based on first- and second-order strategies. The theoretical work is elegant and self-contained. In addition, the empirical study largely validates the effectiveness of the proposed approaches.", "questions": "Please see the weaknesses.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper innovatively transforms the PML problem into a negative-unlabeled (NU) learning problem through a carefully derived loss function, providing a clear and elegant theoretical perspective. \n2. The theoretical analysis is rigorous, with well-stated assumptions, formal consistency proofs, and convergence rate derivations. \n3. The empirical evaluation is thorough, covering both standard benchmarks and additional real-world datasets, which enhances the credibility and generality of the proposed method. \n4. The paper is well-motivated and clearly written, with smooth logical flow and sound reasoning connecting problem definition, theory, and empirical validation.", "weaknesses": "1. The derivation in Lemma 1 heavily relies on assumptions, which may be difficult for readers to intuitively grasp. I would suggest providing more intuitive insights or illustrative examples to clarify the underlying rationale of the lemma and its implications for the overall theoretical framework. \n2. The rank loss based on the second-order strategy appears to primarily capture the gap between the ground-truth and non-ground-truth labels, but not the relevance among ground-truth labels themselves. It would be interesting to discuss whether a rank loss can be designed to simultaneously model both the inter-ground-truth relevance and the ground-truth and non-ground-truth gap. \n3. In the experiments on synthetic benchmark datasets, the differences between case-a and case-b are not clearly analyzed. It would strengthen the empirical section if the authors could elaborate on the motivation for setting up these two distinct cases, and provide a detailed discussion of the respective findings and their implications. \n4. Although this paper focuses on weakly supervised multi-label learning, the proposed loss formulations and theoretical derivations seem readily transferable to weakly supervised multi-class settings, such as partial label learning and complementary label learning. A discussion along with potential preliminary experiments on this broader applicability would further highlight the generality and impact of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4rgjyufnnf", "reviewer": "Reviewer_2V1q", "summary": "This paper presents a unified framework, COMES, for consistent multi-label classification under inexact supervision, targeting both Partial Multi-Label (PML) and Complementary Multi-Label (CML) learning. The authors aim to overcome the limitations of existing methods, which rely on either estimating the complex label generation process or adopting a uniform distribution assumption. The core contribution is a new data generation assumption—that true negatives are marked as non-candidates with a constant, instance-independent probability—which allows for a new approach. Based on this premise, the paper derives unbiased risk estimators (and their subsequent corrected, consistent versions) for two widely used metrics: the Hamming loss (COMES-HL, a first-order strategy) and the Ranking loss (COMES-RL, a second-order strategy). The authors provide theoretical guarantees for the consistency and estimation error bounds of their proposed estimators. Empirically, the framework is validated on ten benchmark datasets, where it is shown to outperform current state-of-the-art methods.", "questions": "See in weekness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  The paper is well-structured and clearly articulates its approach (COMES) as a unified solution for both PML and CML problems.\n2.  It introduces a new data generation assumption that avoids the common pitfalls of transition matrix estimation or uniform distribution assumptions.\n3.  The proposed methods are supported by both theoretical guarantees and extensive empirical validation.", "weaknesses": "1. There is a contradiction between the method's motivation and its empirical results. The second-order strategy (COMES-RL), which was introduced specifically to model label correlations, paradoxically performs significantly _worse_ than the first-order strategy (COMES-HL) on datasets with strong label correlations (e.g., CUB and COCO), an inconsistency the authors do not address.\n    \n2. The paper's claim of proposing \"unbiased risk estimators\" is misleading. The practical estimators (Eq. 8, 14) used in the algorithm are \"corrected\" versions that are _biased_ (to avoid overfitting from the original unbiased forms).\n    \n3. The method's reliance on accurate class-prior estimation ($\\pi_j$) is a critical vulnerability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)