Complementary Label Learning with Positive Label Guessing and Negative Label Enhancement
Authors: Yuhang Li
Zhuying Li
Yuheng Jia
Venue: ICLR 2025 Poster (2025)
Keywords: Complementary label learning
negative label enhancement
weakly supervised learning
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We propose a novel complementary label learning method with excellent classification performance and theoretical guarantee.

Abstract: Complementary label learning (CLL) is a weakly supervised learning paradigm that constructs a multi-class classifier only with complementary labels, specifying classes that the instance does not belong to. We reformulate CLL as an inverse problem that infers the full label information from the output space information. To be specific, we propose to split the inverse problem into two subtasks: positive label guessing (PLG) and negative label enhancement (NLE), collectively called PLNL. Specifically, we use well-designed criteria for evaluating the confidence of the model output, accordingly divide the training instances into three categories: highly-confident, moderately-confident and under-confident. For highly-confident instances, we perform PLG to assign them pseudo labels for supervised training. For moderately-confident and under-confident instances, we perform NLE by enhancing their complementary label set at different levels and train them with the augmented complementary labels iteratively. In addition, we unify PLG and NLE into a consistent framework, in which we can view all the pseudo-labeling-based methods from the perspective of negative label recovery. We prove that the error rates of both PLG and NLE are upper bounded, and based on that we can construct a classifier consistent with that learned by clean full labels. Extensive experiments demonstrate the superiority of PLNL over the state-of-the-art CLL methods, e.g., on STL-10, we increase the classification accuracy from 34.96\% to 55.25\%. The source code is available at https://github.com/yhli-ml/PLNL.

Published as a conference paper at ICLR 2025
COMPLEMENTARY LABEL LEARNING WITH POSITIVE LABEL GUESSING AND NEGATIVE LABEL ENHANCE-
MENT
Yuhang Li Zhuying Li
Yuheng Jia
Schooo of Computer Science and Engineering. Southeast University, Nanjing 210096, China KKey Laboratory of New Generation Artificial Intelligence Technology and Its Interdisciplinary Applications (Southeast University), Ministry of Education, China (yuhangli, zhuyingli, yhjia) ($seu. edu.
ABSTRACT
Complementary label learning (CLL) is a weakly supervised learning paradigm that constructs a multi-class classifier only with complementary labels, specifying classes that the instance does not belong to. We reformulate CLL as an inverse problem that infers the full label information from the output space information. To be specific, we propose to split the inverse problem into two subtasks: positive label guessing (PLG) and negative label gnhancement (NLE), collectively called PLNL. Specifically, we use well-designed criteria for evaluating the confidence of the model output, accordingly divide the training instances into three categories: highly-confidentt, moderately-confidee instances, perform PLG to assign them pseudo labels for supervised training. For moderately-confice and under-confident instances, we perform NLE by enhancing their complementary label set different levels and train them with the augmented complementary labels iteratively. In addition, we unify PLG and NLE into consistent framework, in which we can view all the pseudo-labeling-ban methods from the perspective of negative label recovery. We prove that the error rates of both PLG and NLE are upper bounded, and based on that we can construct a classifier consistent with that learned by clean full labels. Extensive experiments demonstrate the superiority of PLNII over the state-of-the on STL-10 10, we increase the classification accuracy from 34.96% to 55.25%. The source code is available at https: / /ggtthb.... com/ yhli ml /PINL.
and under-confident. For highly-confident
CLL methods, e-g-,
INTRODUCTION
Over the past few years, large-scale and accurately labeled data has tremendously boosted the development of deep neural networks. However, collecting accurately labeled data is extremely time-consuming, iuboor-ntenssie and sometimes requires specific expertise in real-world tasks. To reduce the dependency on large-scale and accurately labeled datasets, deep learning communities have given increasing attention to weakly supervised learning, including but not limited to partial label learning (Cour et al., 201 1; Xie and Huang, 2018; Feng and An, 2019; L.v et al., 2020; Xia
et al., 2023; Jia et al., 2023; 2024; Yang et al., 2024; Huang and Cheung, 2024; He et al., 2024; Tian et al., 2024), noisy label learning (Natarajan et al., 2013; Han et al., 2018; Song et al., 2023; Wei et al., 2020; Zhang et al., 2023; Huang et al., 2023), semi supervised learning (Van Engelen and Hoos, 2020; Sohn et al., 2020; Xie al., 2020; Yang al., 2023; Li et al., 2024; Jiang al., 2024b), positive-unlabeled learning (Niu et al., 2016; Kiryo et al., 2017).
Here, consider a recently proposed weakly supervised learning framework called complementary label learning (CLL) (Ishida et al., 2017: Feng et al., 2020). In CL.,, each training instance is associated with one or multiple complementary labels (CLs) which specify one multiple classes that the instance does not belong to. The goal of CLL is to learn a multi-class classifier only from complementary labeled data. In real-world scenario, if the number of classes is huge, choosing the
"Corresponding author.

---

Published as a conference paper at ICLR 2025
correct class label from many candidate classes is difficult and laborious, while choosing or several of the incorrect class labels as CLs would be much easier and thus less costly. Recently, CLL has been applied to online learning (Kaneko al., 2019), medical image segmentation (Rezaci et al., 2020) and medical molecular imaging (Tapper et al., 2024), etc. Besides, another promising future application scenario of CLL is to ensure privacy security in data collection scenarios. For example, collecting some survey data may require extremely private questions and it would be mentally less demanding if we ask the respondent to provide some incorrect answers as CLs (Dwork, 2008).
Previous studies on CLL can be roughly divided into two categories: methods that attempt to construct an unbiased risk estimator (URE-based) (Ishida et al., 2017; 2019; Feng al., 2020) and methods based on feature learning (FL-based) (Chou et al., 2020; Wang et al., 2021; Liu et al., 2022; Jiang et al., 2024a). For URE-based methods, Ishida et al. (Ishida et al., 2017) and Feng et al. (Feng et al., 2020) showed that the ordinary classification risk can be recovered by their proposed unbiased risk estimator only from complementary labeled data. Ishida et al. (Ishida al., 2019) later extended the unbiased risk estimator to arbitrary losses and models. Chou et al. (Chou al., 2020) proposed a surrogate complementary loss framework, which avoids the extremely noisy gradient problem encountered in unbiased risk estimator. For FL-based methods, Wang et al. (Wang et al., 2021) gave the first attempt to leverage regularization techniques with complementary label by aligning the model output of one instance and its multiple augmented views. Liu al. (Liu et al., 2022) proposed to integrate self-supervised and self-distillation to complementary learning. Jiang et al. (Jiang et al., 2024a) leveraged a contrastive learning framework to facilitate CLL. These methods mainly focus on the design of robust loss functions or the exploration of feature space information, while neglecting the power of output space information.
We propose that CLL can be viewed as solving the multi-class classification problem from two inverse aspects, where one is to infer the positive label and another to infer the negative labels. To this end, we propose two subtasks: positive label guessing (PLG) and negative label enhancement (NLE). We use well-designed criteria for evaluating the confidence of the model output, accordingly divide the training instances into three categories: highly- confident in each epoch. We perform PLG by simply pseudo-labeling highly-confident instances for supervised training. Unlike pseudo-labeling methods used in semi-supervised learning (SSL), PLG pseudo-labeling reaches high selected ratio and high precision even without any positive labels available.
moderately-connfieet and under-
More importantly, previous SSL methods lack the utilization of untrustworthy instances. They either discard this part simply employ techniques such consistency regularization. In this paper, we perform NLE by enhancing the negative label set of moderately-conffier and under-confident instances and train them with the augmented negative labels iteratively.
Although PLG and NLE will inevitably bring pseudo-labeling errors, we theoretically prove that the егrоr rates are upper bounded. And the generalization error of the learned classifier under PLG and NLE errors is also upper bounded, which means that we can construct a classifier consistent with that learned by clean full labels. We demonstrate that PLNL achieves state-of-the of-tth-art performance on five benchmark datasets. Our contributions can be summarized as follows:
A novel method for CLL. Different from conventional loss design methods, we pioneer a novel method for CLL called PLNL that formulates CLL from output space information and solve it by two subtasks: PLG and NLE.
A unified framework for parudo-labeling -based methods. From the perspective of negative label recovery, we construct a unified framework for pseudo-labeling-basee methods. We empirically show that PINNI outperforms state-of-the-art SSL methods in terms of pseudo- labeling error, selected ratio and recovered negative labels.
Solid theoretical analysis. We theoretically prove that both the error rates of PLG and NLE are upper bounded. The generalization error of the learned classifier is also upper bounded.
State-of oot--he--ttrr- art performance. Extensive experiments on five benchmark datasets demon- strate the superiority of P.NN. over the state-of-the-art CLL methods.
2

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
Ordinary Multi-Class Classification. Let A' E Ra denote the feature space with d dimensions and y
K} denote the label space with K classes. The precisely labeled instance (a. y) E X y is sampled from an unknown joint probability distribution P(X, Y). The goal of ordinary multi-class classification is to learn a parameterized function f(x) R - R that minimizes the classification risk:
R(f) Y) ((f())))
(1)
where Y refers to the expectation across all possible samples drawn from the distribution
P(X, Y) R x - I is multi-clas: classification loss function. In this paper, we consider common case where the function / is a deep neural network with the softmax output layer, where / f(x)) is considered as the output prediction confidence of the model on each class. Since the probability distribution P(X, Y) unknown, we use the empirical risk R(ff) to approximate R(f). Assuming a dataset { 9:) ) is independently drawn from distribution P(X, Y), then we have
1 N Σ (()()))
R(
Complementary Label Learning. Different from the ordinary multi-class classification, in CLL, let {xx, Y.)] be the complementary labeled dataset, where N is the dataset size, Y, indicates the complementary (negative) label set of æ,. Each complementary labeled instance (æ. Y) E X x y is sampled from an unknown joint probability distribution P(X, Y). Our goal is to learn a classifier that minimizes the classification risk Eq. (I) only from complementary labeled training instances. Then the empirical risk becomes:
N Σ
R(n) = N
(f:)) Pt), i=1
where EOLL is a specially designed loss function for learning from only complementary labeled data.
3 PROPOSED METHOD
The overall framework of PLNL is shown in Fig. and the pseudo-code is presented in Appendix A. We begin by employing weak and strong augmentation to complementary labeled image I;, which leads to two augmented views z,", x;. These two images are then fed into a two-view network with shared weight f(x; θ) to obtain two prediction confidences f (x="") and f(x"). Then we utilize the two-view prediction confidences to select three subsets of training instances mentioned above, i.e., highly-confident, moderately-confidee and under-confident. We select these subsets using the historical confidences of the previous training epochs to better alleviate confirmation bias. Finally, different techniques are utilized to conquer individual subsets. In this section, we first explain the well-designed confidence-basee highly- -ogfidcconfident instances and two different versions of NLE for the moderately-confidee instances and the under-confiden instances in detail.
instances selection strategy, and then introduce the PLG for the
3.1 CONFIDENCE- CONFIDENCE-BASED INSTANCES SELECTION
We first maintain two memory banks M and M for weak and strong augmentation respectively, each with size x N x K to store the historical prediction confidence over the past epochs. For simplification, we only consider one view here unless otherwise specified.
M. = (x:),....... (*x)))
(4)
where f(x,)) denotes the prediction confidence of the t-th epoch in the memory bank M.
We propose to select subsets based on the following criteria.
Wi1 = V1 < j < f, arg max (f (mx)) & V.,
(5)
W2 = v1 < j, k < t, arg max (f (m:) = arg
(6)
Wg v1 م f tt ( X.
(7)
3

---

Published as a conference paper at ICLR 2025
Backgropagation
Week
Fz
Enhancing
f 0)
A
Highlt-confieett
PLG
Complamettary Iabited
backbone
Canfidence- based lastances whectiun
Moderately-ceefflee
0
(x2 Pt
NLE
rox
Under-euufieet
1
(Initial) negative
x7
I: goened positive label I: cahaneed negative labbll sct
Figure The overall framework of PLNL. We employs two-view network (shared backbone) to extract features and compute confidences for weak and strong augmentations of one instance respectively. After the selection of highly-confident,
and under-confident set, We employ PLG highly-confident instances and NLE for the rest. The loss is computed on the enhanced labels of both views and the model updates through backpropagation.
moderately-connidee
where wi,, W22, wis are boolean variables which indicate whether the corresponding criterion is satisfied. Wa ensures that the label corresponding the max prediction confidence does not fall on the complementary label set, which excludes the complementary labels from being selected as positive label. wi2 ensures that the max prediction confidence be stable and show no sign of fluctuations over the past /. epochs. wis ensures the max prediction confidence should be higher than threshold X. Note that can be either man-made threshold or a self-adaptive one, which will be discussed in detail later.
Warm up. Before selecting, we warm up the model using the entire training set. The goal of this stage is to reduce the classification risk and obtain some historical prediction confidence to construct the memory bank since we have no historical information at initial epoch. In this paper, we use SCL-LLGG algorithm (Chou et al., 2020) warm up models for 20 epochs.
Instance-aware self-adaptive threshold. The threshold in criterion Was, as mentioned above, can be fixed high threshold (like 0.95). However, single global threshold does not consider the fitting difficulties of different instances, i.e., hard instances and easy instances. This will result in very few samples being selected in the early training stages as well as confirmation bias. Therefore, to comprehensively consider historical information, we design an instance-awan self-adaptive threshold for each instance at each epoch & as:
1 K'
X(1) ad(t + (1-
8
where is the number of classes, f(1)= = max (xx and a is the ratio which controls the threshold stability.
The threshold is initialized at a low value K which will take more data into account and helps speed up convergence in the early stages. As the prediction confidence increases, the threshold grows higher to filter out wrong pseudo labels to alleviate the confirmation bias. Note that we compute X (!) and (t) for two different views respectively according to Eq. (8). We use the momentum average confidence of each instance, computed based on all previous epochs. In this way, the threshold comprehensively considers historical information and remains stable and trustworthy.
Subset Selection. For the two-view network, we perform two independent verifications. Let 3:"T = Wi A W/2/ A Wia be the indicator of satisfying the criteria. Thus, 8 and B indicate whether the weak and strong views meet the criteria respectively. For an instance, if both views meet the criteria, we select it to the highly-confident subset, i.e.,
H = {2 A A =3.
means the prediction confidences of both views are stable and high, thus we consider them to be highly-confident. The size of H. is denoted N₁.
4

---

Published as a conference paper at ICLR 2025
Similarly, the moderately-confidee subset consists of instances only augmented version of which meet the criteria, i.c.,
M 13." * B.)
(10)
It means only one view's prediction is trustworthy, the other is not. which shows that the model is moderately-conffdent about its prediction. The size of M is denoted Nm.
Finally, the under-confident subset consists of the rest of the instances, i.e.,
= { 5 V 3 = 0}.
(11)
means the prediction confidences of both views do not meet the designed criteria, these instances are considered under-confident. The size of 24 is denoted as N..
After obtaining H. .M and U, we design different techniques to better utilize these different types of training instances.
3.2 POSITIVE LABEL GUESSING
For highly-confident set H. we consider the label with the max prediction confidence as its positive label. Conversely, all remaining labels considered complementary labels. Let V, be the enhanced negative label set for instance 2;, we have:
Φ, = {clc Y, c + Uz)
(12)
where Ú; is the guessed positive label and Y, ..... K} is the full label set. For highly-confident set H. we compute the CLL loss on the negative labels for both views:
No. Σ Coulf(a))))) (oul(f())) &.),
Cn
(13)
where [(x;") and f(x)) denote model outputs of weak augmentation and strong augmentation respectively.
3.3 NEGATIVE LABEL ENHANCEMENT
For the moderately-confides set M and the under-confident set U. guessing the positive labels directly might lead to much more errors due to their relatively lower confidence. Therefore, we employ different strategy for these instances, called negative label enhancement (NLE).
The rationale of NLE is that more negative labels will bring in additional supervision information for better training. However, whether the enhanced negative labels are correct remains question. Intuitively, randomly enhancing negative labels will bring in a large number of labeling errors. To better enhance the reliability of NLE, further exploit information in the output space and design the following solution.
Calculation of Nearest Neighbor (k-NN) instances. For instance æ; and its model output prediction confidence y/, we can compute its k-NN instances in the output space. It is safe to assume that nearby instances in the output space should have the same positive label with a high probability, while their original complementary label sets are likely to vary. The formal definition of this assumption as follows:
Assumption 1. Y(a;, V.) D and its k-NN instances (ar (.())))) the positive label yi exists in its k-NN instances' complementary label set V.D) with probability no more than Ork, any negative label 3 A ii exist in its k-NN instances' complementary label set Y((3) with probability no less than Bu-
This assumption describes the intrinsic characteristics of CLL in the output space, which can be interpreted in two aspects. First, similarity in the input space will be mapped to similarity in the output space, which has been widely utilized for tackling representation learning problems (He et al., 2020). Second, instances the same category are likely to be labeled with complementary labels of different categories, which is key enhancing the negative labels.
5

---

Published as a conference paper at ICLR 2025
k-NN label frequency. For instance z; propose calculate the times negative label appears in its k-NN instances' complementary label set and then enhance top-r; frequent ones, that is, add them to the complementary label set of Z;. We define the j-th k-NN label frequency of æ; follows:
F3J
- T(j )
(14)
where v:(1) denotes the complementary label set of the v-th nearest instance of 0;.
Negative label enhancement. We enhance the complementary label set Y, by adding additional labels with top-T; label frequency. For each instance æ; in M and U, the enhanced complementary (negative) label set Y, is calculated by:
Φ: = {clc Y, V top-7:-maxjey, (Fiy))
(15)
However, the prediction confidence of the under-confident is more unreliable than that of the moderately-confiden Therefore, we should be more conservative when enhancing these instances as the k-NN information may be more unreliable. In our work, we set T; I
K-si for U where s; where is current epoch, Emaa is total
is the size of Y, For M, we set T; = (1 epochs. This provides a linear growing strategy for the moderateey-confiden because the model's s output becomes increasingly accurate as the training progresses. The ablation study on this strategy is provided in section G.6.
For moderately-conffe confident set M and under-confident set U, we compute the CLL loss on the negative labels for both views:
N No
Leur(f(=)), V.) + Loun(((a;), Va).
mm,
(16)
where fxx"") and f(=²) denote model outputs of weak augmentation and strong augmentation
respectively.
4 A UNIFIED FRAMEWORK FOR PSEUDO-LABELNG-BBA. METHODS
Pseudo-labeling which has been widely used in the recent comi-supervised learning (SSL) methods, employed by giving unlabeled instances pseudo labels and train them a supervised way. PLNL an extension of pseudo-labeling. We not only consider pseudo-labeling of highly-confident instances, but also consider enhancing the negative label set of untrustworthy instances. In this way, we actually recover more supervised information than only leveraging aseudo-labeling and further boost the classification performance.
In this section, construct unified framework where PLG and NLE viewed from the perspective of negative label recovery. Let ýJ be the pseudo-label of æ;, Let Y; be the full label space. Let Y, be the reconstructed (PLNL) imposed (pseudo-labeling) negative label for æ;.
For PLNL, PLG is equivalent to reconstructing a negative label set Ý, {clc E Y,, di} of size K 1-1, in which only the guessed positive label does belong. NLE equivalent reconstructing a negative label set of size s; т. where we add negative labels to the original negative label set of size st-
Similarly, for pseudo-labeling methods, let the pseudo label for instance be js as well. The process of paeudo-label highly-confident instances also equivalent to imposing a negative label set Y, {clc E Y,, + 9.} of size K - 1 as additional supervised information.
In this paper, we propose two metries for evaluation of pseudo-labeling -basdd methods. Firstly, we define selected ratio 7):
N N
17
(17)
Obviously, 7) evaluates the ratio of highly-confident instances selected for labulig methods.

---

Published as a conference paper at ICLR 2025
Furthermore, we define average size of enhanced negative label set
1 N
(18)
In section 6, we empirically show that PLNL achieves lower error rate e, higher selection ratio 7) and obviously larger size of negative label compared with pseudo-labeling method Fixmatch (Sohn et al., 2020) and Freematch (Wang et al., 2023b).
5
THEORETICAL ANALYSIS
5.1
GENERALIZATION BOUND
For simplification, only consider one view network here, which has influence the deduction of generalization enror bound. Our goal is to learn a classification model f(æ; θ) by minimizing the empirical risk Rt acquired from data with enhanced negative labels:
1 R'()) N E CeLL(((E))) (f..),,
(19)
where Y; denotes the enhanced negative label set of a;..
where f is the Let the CLL loss function be (CLL(f(x), F:) = E NeR ((K-I>
be the average size of enhanced negative size of the enhanced negative label set. Let 8 - Pi
label set. Let E1 = E,
Km be the error rate of PLG. Let E2 = Ei NA.
N. Iu:EY;)
be the No+N.
error rate NLE. The actual pseudo-labeling error rate = ΣN En K(ne8d N + Nm 171 + n)E2. Morcover. ((f(x), y) is p-Lipschitz w.r.t. f(x) where p can be any Lipschitz constant (not necessarily the best). Let (FF be the expected Rademacher complexity (Mohri et al., 2012) of F with N training instances. Let f = argmin R R'(F) be the empirical risk minimizer, where F is function class, and f ar R(f)) ((((() be the true risk minimizer. We derive the following theorem, which provides a generalization error bound for the proposed method.
N 62
Theorem 1. Suppose that (xx(x) y) is bounded by B. For pseudo-labeling error rale E f).
any O, with probability at least - 6, we have
log 2
R(F) R(f") S 2(1
- B ApK(HN(F) + 2KB
(20)
K-
2NV
Remark. Detailed proofs are provided in Appendix B. Theorem 1 shows that N 00, 60, - 0. E2 + 0, the empirical risk minimizer converges to the true risk minimizer with high probability. It can be observed from Eq. (20) that the generalization bound is influenced by five factors: the number of categories K, the average size of enhanced negative label set & and two error rates. This is consistent with the intuition that more categories and less complementary labels will make the CLL problem harder. In a nutshell, smaller PLNL pseudo-labelie error rates e 62 and larger size of enhanced negative label set will produce better generalization performance.
5.2 ERROR BOUND POSITIVE LABEL GUESSING
Theorem 2.
Let ys denote the ground-truth positive label of x; and ÿJ denote the guessed positive label which might not be true. PLG error rate 6, is upper bounded by:
E1 = =P(: YY.) < (XX ()KKY)
(21)
where K is class number, is the size of Y,, 1b is positive constant approaching zero, which is related to the probabilistic distribution where (x,, Y,) is sampled. Detailed proofs are provided in Appendix C.
7

---

Published as a conference paper at ICLR 2025
5.3 ERROR BOUND OF NEGATIVE LABEL ENHANCEMENT
Theorem 3. Let yi denote the ground-truth positive label of æ; and of denote an arbitrary negative label. Let F(T)) denote the T--th largest label frequency. Let p denote the probability of the ground- truth positive label yj appearing in its k-NN instance's 's complementary label set. Let q denote the probability of the label y' appearing in its k-NN instance's 's complementary label set. The NLE error rate 62 is upper bounded by:
62 = P -P((EEE)))
#
(
(x
|x - T.
Y ) lo. -
-+ jjj---t-
1,5) Dau (k:
(22)
j=1 where Ls, (): = -0 (1 g
denotes the regularized incomplete beta function, bove (k, () (1as))* is the probability mass function of a binomial distribution B(k, aa). Detailed proofs are provided in Appendix D.
Remark. Theorem and Theorem show that both PL.G error rate 61 and NI.E error rate 62 are upper bounded under mild condition.
Table 1: Comparison of classification accuracies between different methods on four datasets with single complementary label per instance. The results (mean + std) are reported over random trials. The best results are highlighted in bold (The same applies hereinafter).
Method
STL-10
SVHN
FMNIST
CIFAR-I 10
UB-EXP
28.84++0.54%
88.93++0.177
87.96+00.08%
62.90-+0.006
UB LOG
20.41=+0,46%
89.59=0.088
87,59 14%%
70.28+0.122
SCL-EXP
31.03++0.615 %
88.66+0.20%%
88.31 +0.0%%
72.35-+0.105
SCL-LOG
30.74:10.72%
89.26=00.24%
88.03
79.87=10.149
POCR
34.96++0.32%
96.65-+0.144%
92.29:
94.15++0.09%
SELF-CL
30.87:10.22%
90.13:10.23%
84.8610.
88.95:10.22%
ComCo 32.43:+:0.28%
+0.41%
85.422+0.400 4.0%
89.36---0.766
Ours 55.25:10.36 %
97.58.10.88%
93.38:10.06
%
94.78:10.12 %
Table 2: Comparison of classification accuracies between different methods on five datasets with
multiple complementary labels per instance. The results (mean + std) are reported over 3 random trials.
Method
STI.-10
SVHN
FMNIST
CIFAR-10
CIFAR-100
UB-EXP 60.85+t0.124
95.23+t0.09g
92.34+0.28%
91.13++0.23%
34.43=00.0%%
UB-LOG
62.84-H0.174
94.76+00.07%
91.84:+0.29%
92.01++0.21%
52..76++0.15%
SCL-EXP
62.964 10%
95.2
92.20=0.27%
| 91.85+00.25%
47.81+0009%
SCL-LOG
61.60
94.88-+0.166
| 92.67-+0.188% 9..51+
49.40-t0.1994
POCR
74.51110.29%
97.144+0.09%
94.76+ 2.6%%
| 96.09:10.27%
53.16:20.11%
SELF-CI.
|
69.85-+-.2004
91.58++0.305
94.92+0.211
92.23-+0.1193
5...65-
ComCo
73.28++0. 19%
05.41100.239
92.01
91.38++0.339
57.88:t0.95%
Ours 77.11+00.14%
98.13-+0.119; %
95.16.10.13%
96.80+ %
64.33---.43%
6 EXPERIMENT
6.1 EXPERIMENT SETUP
Datasets. We use five commonly used benchmark datasets, STL-10 (Coates et al., 2011), Fashion- MNIST (FMNIST) (Xiao et al., 2017), SVHN (Netzer et al., 2011), CIFAR-10 and CIFAR-100 (Krizhevsky and Hinton, 2009). We conduct experiments by considering both the scenarios of Single CLL (SCLL) and Multiple CLL (MCLL). The datasets generation process are provided in Appendix F.
8

---

Published as a conference paper at ICLR 2025
Compared methods. We compare the performance of PLNL with seven state-of-the CLL methods, including UB-EXP (Feng et al., 2020). UB-LOG (Feng et al.. 2020), SCL-EXP (Chou et al., 2020), SCL-LOG (Chou et al., 2020), POCR (Wang et al., 2021), SELF-CL (Liu et al., 2022) and ComCo (Jiang et al., 2024a) and two state-of-the-art SSL. methods, Fixmatch (Sohn et al., 2020) and Freematch (Wang al., 2023b).
Implementation.
Implementation details are provided in Appendix F.
6.2
MAIN RESULTS
1.00
50
0.8
Jine. Stre or Kis 6
80
Predten1
20
Leg
0.94
1003
50
100
150
200
0.90
20c
Spochs
Rpech
Spach
(a) Accuracy Comparison of CLL methods
(b) PLG Procision vs. Selected Ratio
(c) NLE Precision vs. Ave. Num. of NLS
Figure 2:
The experiments is conducted on CIFAR-100 with multiple complementary labels (MCLL). (a)
The accuracy of PLNL improves tremendously over epochs and achieves the best finally. (b) The precision of PLG decreases slowly, while the selected ratio steadily rises, indicating growing proportion of selected instances during training. (c) Ave. Size of NLS denotes average number negative label set The precision NLE remains relatively stable with a slight decrease, whereas the average size negative label set increases significantly, showing steady recovery of negative labels.
PLNI achieves SOTA results. As shown in Table and Table 2, PINI. outperforms all the compared method by a significant margin across all datasets. Specifically, on STL-10 dataset, we outperform the previous SOTA by 20.29% % and 1.61 % in both SCLL and MCLL settings. Furthermore, PLNL performs even better in harder scenarios where there is larger label space less supervised information for each class. We challenge this by showing our results on CIFAR- 100 datasets. On CIFAR- 100 with Multiple CLs, the improvement 6.45% compared previous SOTA. Fig. 2a further demonstrates that PLNL significantly outperforms the compared ones.
PLNL pseudo-labeling achieves excellent performance with extremely high precision. Fig. 2b shows that as the number of epochs increases, PLG will select more and more highly-confident instance, eventually occupying most of the dataset, while the precision only drops slightly in the final stage, which maintains high precision and high selected ratio. Meanwhile, Fig. 2c shows that NLE identifies more and more negative labels with extremely high precision, which maintains above 0.99 throughout training.
0.5
I.PL
JUIL
Flomatch
Rometon Rneearch
0.6
0.4
0.3
50
300
350
200
50
150
200
50
1000
150
2003
Froc
(a) Selected Ratio Epach
(b) Ave. Num. of NLS Epoch
Converggence of 1-4
Figure 3: The experiments is conducted on CIFAR-10 with single complementary labels (SCLL). (a) shows that selected ratio of PINNI trenscends Fixmatch and Freematch significantly. (b) shows that average size of NI.S of PLNL significantly larger due to specially designed technique NLE for enhancing labels. Nearly all negative labels are revealed at the end of training. almost reaching negative labels for each instances in CIFAR-10 10 (c) indicates that the value of (1
untrustworthy negative
R- decreases steadily during training.

---

Published as a conference paper at ICLR 2025
Compared with SOTA semi-supervised learning methods, PLNL performs even better. From Fig. 3a and Fig. 3b, we can see that PLNL achieves both higher selected ratio and recovered more negative labels compared with Fixmatch and Freematch. PLNL is both accurate and comprehensive in recovering label information. This highlights PINL's enhanced capacity leveraging moderately- confident and under-confident instances for label recovery, showcasing both stability and scalability.
PLNL can reduce the generalization bound and achieves lower generalization bound compared with SSL methods. Fig. 3c demonstrates that (1 K- decreases as the training progresses. As
I-c
(1 k-s) is the variable of the generalization bound derived in Theorem 1, it is safe conclude
that PLNL can continuously and significantly reduce the generalization error.
6.3 ABLATION STUDY
Two-view networks facilitate increased pseudo- labeling precision. We observe that two-view network significantly boost the performance of PLNL pseudo- labeling, which helps accurately select more highly- confident instances. As shown in Table the 1) in- creases 8.75% and 8.65% respectively on CIFAR-10 and CIFAR-100 with 61 increases 6.58% and 9.22% respectively. We also compare PLNL with one variant:
Table 3: The performance of PLNL with single network on two settings.
CIFAR-10 10 SCLL
CIFAR-100
Method
MCLL
7
1-E1
7
1-c1
Single
84.65
90.21
67.43
70.62
PLNL v1 where we replace the two-view networks in PLNL with single network in Table 4, which shows that ours outperforms PLNL vI by a remarkable margin (e.g. +6.00% % on STL-10).
Two-view
93.40
96.79
76.08
79.84
All the components contribute to the performance gain. We explore the effectiveness of our proposed PLG and NLE method on three settings STL-10 (SCLL), CIFAR-10 (SCLL), CIFAR- 100 (MCLL). Specifically, compare PLNL with several variants: (1) PLNL v2 which removes the PLG component; (2) PLNL v3 which removes the NLE component. From Table we observe that PLNL outperforms PLNL v2 remarkably (e.g., +5.43% % on STI.-10), which proves the effective- ness of positive label guessing. We also observe that ours outperforms PLNL v3 (e.g., +1.19% on CIFAR-100), which proves the effectiveness of NLE,
Table 4: Classification accuracy of degen- erated methods three settings.
STL-10 SCLL
CIFAR-10 SCLL
CIFAR-100 MCLL
Method
PLNL
55.25
94.78
64.33
PLNL v1
49.25
93.75
63.09
PLNL v2
49.82
92.01
58.94
PLNL v3
53.22
94.28
63.14
POCR
34.96
94.15
53.16
CONCLUSION
In this paper, introduce novel complementary label learning method that reformulates CLL an inverse problem to infer the full label information from the output space information. To this end, we split this inverse problem into subtasks (PLG and NLE). confidence- based instances selection module is proposed for dataset split: highly-confident, moderately coofiiden and under-confident. Then we perform PL.G for highly-confidens instances by assigning pseudo-labels to them. For moderately-confider and under-confident instances, we perform NLE by enhancing their negative label set with different levels and train them with the augmented negative labels iteratively. We theoretically prove that when pseudo-labeling error is limited, we can construct classifier consistent with that learned by clean full labels. The upper bounds of PLG and NLE error rate are deduced and empirically show that PLNL can infer both positive and negative labels with high precision. We conducted extensive experiments which demonstrate that PLNL achieves a new sfate-of-the-us in CLL.. In addition, extensive ablation studies have proved the effectiveness of each component.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work was supported by the National Natural Science Foundation of China under Grants U24A20322 and 62302094. This work was also supported by the Big Data Computing Center of Southeast University.
REFERENCES
Shoshana Abramovich, Graham Jameson, and Gord Sinnamon. Refining jensen's inequality, Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, 47 (95)(122:3-144, 2004.
Yu- Yu-Ting Chou, Gang Niu, Hsuan Hsuan-Tien Lin, and Masashi Sugiyama. Unbiased risk estimators can mislead: A case study of learning with complementary labels. In International Conference on Machine Learning, pages 1929-1938. PMLR, 2020.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis of single-layer networks in unsuper- vised feature learning. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 215-223. PMLR, 2011.
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12(42):1501-1536 2011.
Cynthia Dwork. Differential privacy: survey of results. In International Conference on Theory and Applications of Models of Computation, pages 1-19. Springer, 2008.
Lei Feng and Bo An. Partial label learning with self- self-guided retraining, In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 3542-3549, 2019.
Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple complementary labels. In International Conference Machine Learning, pages 3072-3081. PMLR, 2020.
Xiuwen Gong, Dong Yuan, Wei Bao, and Fulin Luo. A unifying probabilistic framework for partially labeled data learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(7): 8036-8048, 2023, doi: 10.109/TPAMM.202.325577
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. Advances in Neural Information Processing Systems, 31:8535-8545, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Proceedings of the European Conference on Computer Vision (ECCV), pages 630- 645, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729-9738, 2020.
Shuo He, Chaojie Wang, Guowu Yang, and Lei Feng. Candidate label set pruning: data-centric per- spective for deep partial-label learning. In International Conference on Learning Representations, 2024.
Jintao Huang and Yiu-Ming Cheung. Trustworthy partial label learning with out-of-distrribtioo detection. arXiv preprint arXiv:2403.0668/ 2024.
Zhizhong Huang, Junping Zhang, and Hongming Shan. Twin contrastive learning with noisy labels. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11661-11670, 2023.
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. Advances in Neural Information Processing Systems, 30, 2017.
11

---

Published as a conference paper at ICLR 2025
Takashi Ishida, Gang Niu, Aditya Menon, and Masashi Sugiyama. Complementary-late learning for arbitrary losses and models. In International Conference on Machine Learning. pages 2971-2990 PMLR. 2019.
Hiroki Ishiguro, Takashi Ishida, and Masashi Sugiyama. Learning from noisy complementary labels with robust loss functions. IEICE Transactions on Information and Systems, 105(2):64-376, 2022.
Yuheng Jia, Chongjie Si, and Min-Ling Zhang. Complementary classifier induced partial label learning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 974-9832 2023.
Yuheng Jia, Fuchao Yang, and Yongqiang Dong. Partial lahel learning with dissimilarity propagation guided candidate label shrinkage. Advances in Neural Information Processing Systems, 36, 2024.
Haoran Jiang, Zhihao Sun, and Yingjie Tian. Comco: Complementary supervised contrastive learning for complementary label learning. Neural Networks, 56, 2024a.
Jiahao Jiang, Yuheng Jia, Hui Liu, and Junhui Hou. Fairmatch: Promoting partial label learning by unlabeled samples. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1269-1278, 2024b.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535-54) 547, 2021. doi: 10.1 1010///DDTTA2219222255555
Takuo Kaneko, Issei Sato, and Masashi Sugiyama. Online multiclass classification based on prediction margin for partial feedback. arXiv preprint arXiv: (el:::90220000 2019.
Ryuichi Kiryo, Gang Niu, Marthinus C Du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. Advances in Neural Information Processing Systems, 30, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 7(7):3 2015.
Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models. In International Conference on Machine Learning, pages 11740-1974. PMLR, 2023.
Siyuan Li, Weiyang Jin, Zedong Wang, Fang Wu, Zicheng Liu, Cheng Tan, and Stan Z. Li. Semire- ward: A general reward model for semi-supervised learning. In International Conference Learning Representations, 2024.
Jiabin Liu, Biao Li, Minglong Lei, and Yong Shi. Self-supervised knowledge distillation for complementary label learning. Neural Networks, 155:318 05:311-327, 2022.
Jiaqi Lv. Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identification of true labels for partial-label learning. In International Conference on Machine Learning, pages 6500-6510. PMLR, 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012. ISBN 026201825X.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances in Neural Information Processing Systems, 26, 2013.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Baolin Wu, Andrew Y Ng, al. Reading digits in natural images with unsupervised feature learning. In NIPS workshop on deep learning and featurr learning, volume 2011, page 4. Granada, 2011.
Gang Niu, Marthinus Christoffel Du Plessis, Tomoya Sakai, Yao Ma, and Masashi Sugiyama. Theo- retical comparisons of positive- unlabeled learning against positive-negative learning. Advances in Neural Information Processing Systems, 29, 2016.
positive-unlabeled
12

---

Published as a conference paper at ICLR 2025
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, sigh-performance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
Mina Rezaci, Haojin Yang, and Christoph Meinel. Recurrent generative adversarial network for learning imbalanced medical image semantic segmentation. Multimedia Tools and Applications, 79(21):15329-15544 2020.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang. Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances in Neural Information Processing Systems, 33:596-608, 2020.
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions Neural Networks and Learning Systems, 34(11):8 (111))8833-8155 135-8153, 2023. doi: 10. N0.1009TNNISS
William Tapper, Gustavo Carneiro, Christos Mikropoulos, Spencer A Thomas, Philip M Evans, and Stergios Boussios. The application of radiomics and ai to molecular imaging for prostate cancer. Journal of personalized medicine, 14(3):287, 2024.
Shiyu Tian, Hongxin Wei, Yiqun Wang, and Lei Feng. Crosel: Cross selection of confident pseudo labels for partial-label learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 19479-19488, 2024.
Jesper E Van Engelen and Holger H Hoos. A survey semi-supervised learning. Machine learning, 109(2):373-440, 2020.
Deng-Bao Bao Wang, Lei Feng, and Min-Ling Zhang. Learning from complementary labels via partial- output consistency regularization. In International Joint Conference on Artificial Intelligence, pages 3075-3081, 2021.
Haobo Wang, Ruixuan Xiao, Yixuan Li, Lei Feng. Gang Niu, Gang Chen, and Junbo Zhao. Picot: Contrastive label disambiguation for robust partial label learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 36(5):3183-3199 2024. doi: 10. 109/TPAM1.203333326600
Hsiu- Wang, Wei-I and Hsuan-Tien Lin. Cleifar: Cifar-derived benchmark datasets with human annotated complementary labels. arXiv preprint S.Miv:2305.08990 2023a.
Yidong Wang. Hao Chen, Qiang Heng, Wenxin Hou, Yue Fan, Zhen Wu, Jindong Wang. Marios Savvides, Takahiro Shinozaki, Bhiksha Raj, Bernt Schiele, and Xing Xie. Freematch: Self- adaptive thresholding for semi-supervised learning. In International Conference on Learning Representations, 2023b.
Hongxin Wei, Lei Feng, Xiangyu Chen, and Bo An. Combating noisy labels by agreement: joint training method with co-regularization. In Proceedings of the IEEE/CVE Conference on Computer Vision and Patlern Recognition, pages 13726-13733 2020.
Dong-Dong Wu, Deng-Bao Wang, and Min-Ling Zhang, Revisiting consistency regularization for deep partial label learning. In International Conference Machine Learning, pages 24212-24225. PM 2022.
Shiyu Xia, Jiaqi Lv, Ning Xu, Gang Niu, and Xin Geng. Towards effective visual representations for partial-label learning. In Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition, pages 15589-15598, 2023.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
Ming-Kul Kun Xie and Sheng-Jun Huang. Partial multi-labe learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
13

---

Published as a conference paper at ICLR 2025
Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoe Le. Unsupervised data augmentation for consistency training. Advances in Neural Information Processing Systems, 33:6256-6206 2020.
Fuchao Yang, Yuheng Jia, Hui Liu, Yongqiang Dong, and Junhui Hou. Noisy label removal for partial multi-label learning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3724-3735, 2024.
Xiangli Yang. Zixing Song, Irwin King, and Zenglin Xu. survey on deep semi-supervised learning. IEEE Transactions on Knowledge and Data Engineering, (5(9):8934-8954 2023. doi: 10.1000K0D..222.2222229
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In Proceedings of the European Conference Computer Vision (ECCV), pages 68-83, 2018.
Manyi Zhang, Xuyang Zhao, Jun Yao, Chun Yuan, and Weiran Huang. When noisy labels meet long tail dilemmas: representation calibration method. In Proceedings the Conference on Computer Vision, pages 15890- 15900, 2023.
the IEEE/CVF International
14

---

Published as a conference paper at ICLR 2025
A THE PSEUDO-CODE OF PLNL
Algorithm 1 Pseudo-code of PLNL.
Input: Training dataset D, mini-batch size B, epochs Fmazz two-view network with shared parameter θ and two memory bank matrices M M hyperparameters i, k, Tms Ta-
1: Initialize M M θ by warming up 20 epochs using SCL-LOG (Chou al., 2020).
2: for ........ Emar do
3: Shuffle into [D] mini-batches;
4: Construct M M
5: Compute two-view network outputs of cach instances;
6: Select H. M, Z4 based on criteria in Eq. (5);
7:
Pseudo-label the highly-confident set H; // PLG
8:
Enhance negative labels of set M,,, U based on Eq. (14) and Eq. (15); // NLE do Fetch an batch B, with enhanced negative label set;
9:
for = 1,
Compute the empirical risk R' (J) by Eq. (19); 12: Update parameters of O;
11:
end for
14:
end for
Output: parameters +
B PROOF OF THEOREM
We first derive the uniform deviation bound between R(f) and R(f).
Lemma 1. Suppose that the binary loss function ((f(x), y) is p-Lipschitz continuous w.r.t. f(x).
For any 8 > 0, with probability at least 8, we have
log 2 8
R(f) (R()) (pk + HBB
(23)
2N
Proof. We firstly define the Rademacher complexity of and F with N training instances follows:
Ry FF)
Exzy,
sup FEF
(24)
Considering that (c = = E E [(f(x), v), we have
Ry F) < KR (
S PK (F),
(25)
where the second line is based Lipschitz continuity of {(f())))) y).
Suppose an instance (æ;;, y:) replaced by another arbitrary instance (z) v.). this leads to a change of sup R(f) - R(f) no greater than KB due to the fact that & bounded by B. According to "N McDiarmid's inequality (Mohri et al., 2012), for any â > O, with probability at least 8
we have
2.
sup R()) - T8(5)) + KB feF
log 2NN
sup R(S) R() < E feF
(26)
In addition, it is routine (Mohri al., 2012) that
E
sup R(f) - R(()) < (F).
(27)
lEF
15

---

Published as a conference paper at ICLR 2025
By combining Eq. (26) and Eq. (27), and futher taking the other direction of sup R(f) R(f) into
feF
account, with probability at least 1 8, we have
log 2 a 2N
sup
RR) Ri() S $2oKRx(F) + KBV
(28)
SEF
which concludes the proof.
Due to inevitable error made in PLG and NLE. The problem of CLL actually has been translated into noisy CLL problem where the true label might be mislabeled complementary label (Ishiguro et al., 2022). Let El be the error rate of PLG and 62 be the error rate of NLE. Since NLE error
rate 6 = >, KyreÝn and NLE error rate C2 = -> N. Hu,eř, No+ the actual noise rate c =
NA
>> K) can be calculated as e = N1 61 + N., = 1 + (1 - n))2.. We further bound the N
N
difference between R(()) and (e'
Lemma 2. Suppose that the binary loss function is bounded by B. For some noise rate c E (0, 1)
and average complementary label size 8 for any f F, we have
R((()) R(() 5 K - B. We firstly proved the upper bound of the (T):
(29)
N N
(f(
(f,,)
N
1 N I[u $ Yi)
1
K- - {(f(x)).
+ ((f(zs).
Σ
((f(x)),
N
N
K 18,
K- |
1=1
Log P.ssin
1 N
+
Σ
Ily E Pi)
Σ
((f(x;), e(f(zz).
N
K - |Y.
LoRY.
N
N
<RS)+ +
I(1 $ Y.)
Σ K-8
1 ((f(a)), +
Σ
Mn E Yi)
[VE=~ Kー (((a)))))
1
N
N
og8:
K 5
B + eB,
(30)
where the second line holds based on Mn T( and Jensen's inequality (Abramovich et al., 2004). Detailed proof of Eq. (30) is provided in Appendix I. We can prove the lower bound in similar way:
N
K- - |p ef(()))
1 R(()) N
Σ ((f(2.).
1
I( $
Pi))
Σ
1
((f(x)),
N
K- K-1
1&
K - 1
1 N
+
Σ
Il E Pi)
Σ
((f(x:), - e(f(2z)) vi)
N
K - 1811
1=1
1 N
1 N
2 R(()
Σ
T(ys $ P,)
Σ K-8 ((f(x)),
1
Σ
T(y
E EY)
Σ ogY,
K (f((x)))).
1
N
N
1=1
K-3-1 B - BB,
2 -
(31)
K -
By combining these two sides, we have:
Rh()) (f) 51 1
1-6 6 B,
(32)
K
16

---

Published as a conference paper at ICLR 2025
which concludes the proof.
Then, for any > O, with probability at least
we have
R(f)
log 8
s R(() + 22p+KN(()) KB)
2N
+ 1-6
log 2
K K-3 + 22 + KB
2N
1
log
<R(()+ +(1
B + 2 (F) + KB
V
K
2N
log 2
< <R()+ +11
B (F) +BV
K 8
2N
1 K B + 4pK + 2K
log go 2.V
S RR()) + 2(1
(33)
where the first and fifth line are based on Lemma 1, the second and fourth line based on Lemma 2, the third line is based the definition of the empirical risk minimizer f argmin Rey which means any other f + would lead to larger risk of R(f).
C PROOF OF THEOREM 2
Motivated by the formulation of partially labeled data learning in (Gong et al., 2023), here we derive the framework for CLL and PLG from probabilistic view. Assume that the full label information can be expressed Y -Y, Y) where Y is the complementary label set and Y is set of the rest labels (containing the true label). Assume that training dataset D = {z; Y 1 is drawn i.i.d. N times from a probability distribution P. where is drawn from underlying random variables X [ X2.... x and Y is drawn from random variables Y = YY, Y ...... Yx)² (d denotes feature dimension and K denotes the number of full labels). And we assume that Q is hypothetical predictive model with parameters 0, where 0 is the model parameter used for prediction. PLG aims identify the moound-truth label from Y, which be implemented by maximizing the conditional likelihood of training dataset with respect to parameters 0. The conditional log-likelihood given all training examples can be expressed as follows.
1 Σ log Q(()a, E(O D) = N
(34)
By multiplying and dividing classifier Q by the distribution of identified ground-truth labels given features Plylæ:, we can formulate Eq. (34) as follows.
Σ log QV 0)
N
N Σ log x.))
(( = N
(35)
((Y))::))
N
By multiplying and dividing the probability P(Y (z) the second term, can formulate Eq. (34) as follows.
2Y..0.0) 0)
P(T P(Y|))) + N 1
((D) N log
log
Σ
log P(Y P(Y)).)) (36)
P(Y
N
1=1
We use E(Xy) operator calculate the expectation of the random variables (X, Y), meaning + co.
log Q(1x0,0) 0) p()
p (x) P(Y (x)
((O)D) = E(x,,)
+ B(x,,)
log
+ Ex,,) flog P(Y)2)) (37)
17

---

Published as a conference paper at ICLR 2025
Recall that assume that the full label information Y (Y, Y). Then the second term of Eq. (37) can be developed as follows.
(x))) { log (L08 P(Y
{
p({())
= (x,,))
log
P(Y x)) P(Y [))
P(Y, Y(x)
P(x, Y)
P(Y
(x.Y)
P( Y,æ)
P(x, Y) log
2(V,2)
P(Y,)
E (m,Y)
P(x, log
P(x|Y)
P(Y, x\) P(Y
Σ P(x, log
P(xlÝ) P(PI))
Σ P(x, Y) log
E Pog
P(x
(z,Y)
P(Y, xl
Σ (x,Y)
P(æ, Y) log
Σ P( log P(Y
P(
(8
-IY X() H
= -
(38)
The last equality holds because the conditional entropy H(Y = 0. This is because in CLI., once Y is known, then Y known, meanwhile, the uncertainty remaining in Y is zero, i.e., H(Y Y 0.
By combining Eq. (38) and Eq. (37), we have the objective function as follows.
() = - log P(Y Q(
} I(Y, -
(39)
The first term is a log likelihood ratio between the true and the predicted ground-trutt label distribu- tions given features. The value of this term depends how well the model Q can approximate P. The second term is the conditional mutual information between the complementary labels and the features, given the guessed positive label. The last term is constant independent of parameters.
Then, we discuss the mild assumption under which PLG method is effective for CLL.
Assumption Let X denote the random variables where is drawn from. Let L,YYXIXY denote the conditional mutual information between the complementary labels and the features, given the ground-truth label y and (Y, X X denote the conditional mutual information between the complementary labels and the features, given any non-complementary label y'. Then, with probability no more than 1/( X, Y)) we have
LY (Y,X(Y) < by X())..
(40)
Remark. Generally, the value of Ig (XX will increase as the guessed positive label 9 explains more about features X. 1, X Y) is negative number and its maximum value reaches zero when the rest labels in Y contain no additional information about X, namely ý = y. Note that in the absence of label noise and image noise, (x( Y) is very small value approaching zero and obviously vb( X, Y) is relevant to specific probability distribution X and Y.
In PLG, the training objective actually is the second term of Eq. (39):(() = - -I(., -I(Y, As a result, the error rate of PLG can be caleulated as follows. Suppose is the guessed positive label, and
18

---

Published as a conference paper at ICLR 2025
y is any non-complementary label.
Ply f). Ppy + j. = j)
II (Y, S (X,
S (0(,8))K-1
(41)
where the second line is because once the true label classified complementary label. means that the conditional mutual information between the complementary labels and the features under every label in Y being selected as guessed true label is larger than that under being selected. The third line is based on Assumption This concludes the proof.
D PROOF OF THEOREM
It is evident that reliable representation information is of great importance to the performace of k-NN based NLE. Motivated by the label distinguishability setting in (He et al., 2024), mild assumption for CLL datasets are discussed to ensure the reliability of the representation information.
The full label information can be expressed as = (V, YY where Y the complementary label set and Y is a set of the rest labels (containing the true label). According to Assumption 1, we have the following lemma.
Lemma 3. V(a;;, Y ED let p denote the probability of the true label yi E Yi appearing in its k-NN instance's 's complementary label set. Let q denote the probability of each non-Complementury negative label y' E YiN(v:) appearing in its k-NN instance's 's complementary label set. Then, we have
p S ak: 8k.
(42)
Then, derive the error bound of NLE in a step by step manner.
Let ((()) denote the v-th largest k-NN label frequency instance æ,, Assume that Fiy and F(()) are sampled from binomial distribution (kk, on) and binomial distribution B q) respectively, An NLE error is caused by mistakenly adding into Y, which means appears more frequently than least one label that should have been added into Y,, namely the ry-th frequent one. Based on the above, we have
P(u: E P.)) P(F
(T) < Fiy),
(43)
Σ (( (T) Fiy F)) 5),
1=
Σ P(F(TT) (7)) zj - P)F j),
P(F!!) > s).... ......(( 1) P(F(T)) < ((F... <s)
P(Fig j);
(Te- 1)items
(1Y2) Jieems
(11/)
[xX]] TV
Ioe - j+ 11 ba (ks
(44)
j-1
where Is, (k. = 10¹ (1 - denotes the regularized incomplete beta function. ba, (k: () (1 a3 F is the probability mass function of a binomial distribution B(k, ox)).
The fourth line holds because the aim is to constrain that there exists Y; т. labels whose label frequency is less than the true label. The fifth line holds because the following scaling equation holds.
19

---

Published as a conference paper at ICLR 2025
P(F <) P( <3)
1X.1-T.
[Vg 1
Im 11-1( qm )mm)
[ Tt
[ - T: )
Av [X]] (1%²)
(1811-T:)
(1-1)) (1-1))-1pi-1d
(45)
Below, we numerically show that the upper bounds for NLE error rates are small numbers approaching zero.
(0 1) binomial coefficient, which a non-negative integer, and in this context, scales the term.
La (k j + 1, is the regularized incomplete beta function, which lies in the range [0, 1]. bas (k represents the probability mass function of binomial distribution (kk, akk), also within [0, 1].
Since Ta, (k: assumed to be large in practical scenarios, causes this term to approach zero, making the contribution of each term the sum negligible.
I, is within [0, 1), raising it to high power, specifically ([Y n), which is
Thus, the right-hand side of the inequality is approximately:
1) Σ j= [ (IXI-
[11] [1 Lpx (k - j +
( 1,5) (k: O.
(46)
E DETAILS OF MCLL SETTINGS
Ishida et al. (Ishida al., 2017) assumed that P(X, Y)) is expressed as:
- c- E P(X)))))))
(47)
This assumption implies that all other labels except the correct label are picked as the complementary label with uniform probabilities. Later, Feng al. (Feng et al., 2020) considered more general setting where each instance is associated with multiple complementary labels (Multiple CLL). Suppose Multiple CLL dataset represented as {(x;, Y.) where Y, is the complementary label set for instance E, Let us denote the number of the complementary labels by random variable st which is sampled from a distribution P(s)). Then, we assume that each sample is drawn from the following distribution:
P(X,Y) Σ P(X,Y -) =),
(48)
where
(5) Erer P(X,Y), 8, j
P(X, Y|8, P)s(s =)
(49)
0,
otherwise.
F EXPERIMENTAL DETAILS
Details of Compared Methods.
UB-EXP (Feng al.. 2020), an unbiased risk estimator with an estimation error bound, which is derived for Multiple CLL specially.
UB-LOG (Feng et al., 2020), another unbiased risk estimator with an estimation error bound but with different multi-class classification loss function.
20

---

Published as a conference paper at ICLR 2025
SCL-EXP (Chou et al., 2020), surrogate complementary loss with the use of exponential loss function.
SCL.-LOG (Chou al., 2020), surrogate complementary loss with the of negative log loss function.
POCR (Wang et al., 2021), an algorithm which combines the SCL-LOG loss and the consistency regularization technique.
SELF-CL (Liu et al., 2022), a self-supervised learning algorithm which integrates self- distillation to CLL.
ComCo (Jiang et al., 2024a), a contrastive learning framework which leverages the con- trastive learning technique CLL.
Datasets generation. To generate single complementary label, we randomly select one of the complementary classes per instance. To generate multiple complementary labels, let be the size of Y. first instantiate p(s) = / -2), s {1, ..., [K-1] 11. which represents the possibility of randomly sample a complementary label set whose size is from all possible complementary label sets which has 2 sets to choose from. Then for each instance 2,, we first sample s; from p(s,).
and then sample a complementary label set Y; with size from p(Y; (V;) = (
Implementation. Values of hyperparameters in PLNL are set as follows. The queue size is selected from 3,, 5, k-NN parameter & is selected from {100, 250, 500}. The a in the instance- aware self-adaptive threshold is selected from {0.1, 0.3, 0.5, 0.7, 0.99]. For each method, we train the commonly used PreAct-ResNet 8 (He et al., 2016) with 200 epochs (initial 20 epochs for warm-up), and use SGD as the opimizer with a momentum of 0,9, a weight decay of le-4. We set the batch size from (64, 128). the initial learning rate from {10-1, 10 10-2), and
cosine learning rate scheduling with final learning rate 10 10-3, We employed faiss (Johnson et al., 2021) to compute k-NN instances in the output space, which is library for efficient similarity search and clustering of dense vectors. For weak augmentations, we employ normalization, horizontal flipping and random cropping. For strong augmentations, we use RandAAugmet strategy for all, which selects the type and magnitude of augmentation based on uniform probability.
For implementation of SSL methods, firstly pre-train the network with complete CLL dataset for 200 epochs. Next, we perform beudoolabeling iteratively and train the model for another 200 epochs.
All of the experiments are implemented based on PyTorch (Paszke al., 2019) and all of our experiments are conducted with 8 NVIDIA 4090 GPUs.
G MORE EXPERIMENTAL RESULTS
G.1 PARAMETER SENSITIVITY ANALYSIS
Influence of memory bank size t. As shown in Table 5, it is obvious that has little effect on the experimental results the three datasets. We chose a slightly better effect. It is important to utilize historical confidence information alleviate confirmation bias, but the size of the memory banks does not matter.
Table Classification accuracy of PLNL with different memory bank size t on three benchmark datasets. The best results are highlighted in bold and the second best are underlined (The same applies hereinafter).
5, which has
Influence of confidence threshold From Table 6, we observe that there is trade-off between and 1-C1, ie., a higher threshold will lead the precision to increase but result in less reliable instances selected while lower threshold will decrease the precision but select more re- liable instances. Instance-awan self-adaptive threshold (IST) shows obvious performance gain compared with a fixed global threshold, showcasing its effectiveness.
STL-110 SCLL
CIFAR-10 SCLL
CIFAR-100 MCLL
54.45%
94.12%
64.21%
3
54.95%
93.98%
63. 63.95%
4
54.88%
94.56%
63.81%
55.25
94.78% %
64.33%
21

---

Published as a conference paper at ICLR 2025
Table 6: Classification accuracy and PLG performance of PLNL with different confidence threshold on two benchmark datasets. 7) denotes PLG selected ratio, denotes PLG precision, 1 C2 denotes NLE precision. IST denotes instance- aware self self-adaptive threshold.
CIFAR-I0. SCLL
CIFAR- 100, MCLL
Accuracy
7
1-61
Accuracy
1-61
0.85
92.89%
99.86%
90.79%
62.12%
81.52%
72.88%
0.90
93.85%
95.78%
92.43%
63.95%
77.25%
77.34%
0.95
94.74%
87.28%
98.68%
64. 02%
73.48%
83.61%
1ST (a 0.5)
94.78% %
93.40%
96.79%
64.33
76.08%
79.84%
Influence of k-NN parameter k. As shown in Table 7, the selection of & depends on the specific situation of the dataset. For example, STL-10 10 has only 500 labeled instances for each category. If is set too large, there will be instances that are not in the category near the decision boundary, which will induce more noise in NLE and cause performance degradation.
Table 7: Classification accuracy of PLNL with different k-NN parameter k on three benchmark datasets.
k:
STI.-10 SCLL
CIFAR-10 SCLL
CIFAR-100 MCLL
100
54.45%
94.25%
63.27%
250
55.25% %
94.73%
64.33%
500
47.23%
94.78%
59.65%
G.2 QUANTATIVE RESULTS: PERFORMANCE OF PLG AND NLE
As shown in Table PLG achieves high selected ratio in all datasets, even reaching 98.86% on FMNIST (MCLL), and 76.08% on the difficult CIFAR-100. And the precision remains high even at high selected ratio. NLE also has high precision, reaching 80.84 60.84% even on CIFAR-100.
Table 8: The performance of PLG and NLE on three settings. The results (mean + std) are reported over 3 random trials. denotes PLG selected ratio, - él denotes PLG precision, 1 - e2 denotes NLE precision.
Performance 1-61
Dataset
Case
1-63
CIFAR-10
SCLL MCLL
93.40=t0.14%
96.79:0000%%
97.79+0.09%
97.4910.112%
99.30-0.05%
98.9110..7%
SCLL 97.25++0.08%
95.24=0.119%
97.56+t0.08%
FMNIST
MCLL
98..6%00006%
97.89-0.1198
98.9710.03%
CIFAR-100
MCLL
76.08:00.2%%
79.84=0.41%
80.84+0.04%
G.3 EXPERIMENTAL RESULTS ON TINY-IMAGENET
Tiny- Ima-lImaeeNet (Le and Yang. 2015) contains 100000 images of 200 classes. Each class has 500 training images, validation images and 50 test images. Due to its huge number of categories, an extremely difficult dataset for complementary label learning. Most existing CLL methods have only tested their performance on 10-class small datasets. Most of their backbones are ResNet and single complementary label is rather difficult setting for large datasets, these will lead to poor performance of traditional CLL methods.
However, have tested the performance of our method on Tiny- Imageeee with MCLL settings. The results are shown in Table 9. Though most of the methods perform poorly, our method still outperforms traditional CL.L methods obtrusively.
22

---

Published as a conference paper at ICLR 2025
Table Comparison of classification accuracies between different methods on Tiny-ImageNet with multiple complementary labels per instance.
Method
Tiny-ImageNe
UB-EXP
3.89%
UB-LOG
7.17%
SCL-EXP
3.36%
SCL-LOG
8.96%
POCR
4.29%
SELF-CL
7.87%
ComCo
8.52%
Ours
11.87% %
G.4 EXPERIMENTAL RESULTS CLCIFAR-20).
DATASETS (CLCIFAR-10 AND
For real-world scenarios, added two datasets, including CLCIFAR-10 1- and CLCIFAR-21 (Wang et al., 2023a), which are two manually-annotate datasets specially designed for CLL. The results are shown in Table 10.
Table 10: Comparison of classification accuracies between different methods on CLCIFAR-10 and CLCIFAR-20.
Method
CLCIFAR-10
CLCIFAR-20
UB-EXP
41.95%
8.08%
UB-LOG
38.46%
6.00%
SCL-EXP
40.93%
7.86%
SCL-LOG
38.77%
7.45%
POCR
51.83%
8.82%
SELF-CL
44.35%
8.64%
ComCo
46.42%
8.21%
Ours
64.39%
9.88%
It can be seen from the above table that PINI performs much better than previous CL.L methods in real-world scenarios, with a 12.56% improvement on CLCIFAR-II 10 and a 1.06% improvement on CLCIFAR-20 compared to previous SOTA (POCR).
G.5 EXPERIMENTAL RESULTS UNDER BIASED COMPLEMENTARY LABEL LEARNING SETTINGS
We add the experimental results of three datasets (STL-10, CIFAR-10, CIFAR-100) 100) under biased complementary label learning settings.
To generate biased complementary labels, we first give the probability of each complementary label to be selected, following the same settings in (Yu et al., 2018), where two settings given, including "without 0" and "with 0"
In the "without 0" setting, for each class y. first randomly split Y y into three subsets, each containing three elements. Then, for each complementary label these three subsets, the probabilities set to 0.6 0.3 and 0.1 respectively.
3
In the "with 0" setting, for each class y. we first randomly selected three labels in y. and then randomly assign them with three probabilities whose summation 1.
The experimental results are shown in Table 11.
The results reveal main points:
23

---

Published as a conference paper at ICLR 2025
Table 11: Comparison classification accuracies between different methods under biased comple- mentary label learning settings.
Method
STL-10
CIFAR-10
CIFAR-100
Without O:
UB-EXP
52.43%
22.54%
1.18%
UB-LOG
48.36%
22.71%
1.00%
SCL-EXP
60.85%
23.53%
1.07%
SCL-LOG
58.63%
22.96%
0.93%
POCR
74.78%
29.03%
1.00%
PLNL
75.38%
38.82%
1.00%
With 0:
UB-EXP 60.71%
78.73%
1.00%
UB-LOG
44.42%
78.69%
1.00%
SCL-EXP
61.24%
79.17%
1.00%
SCL-LOG
63.36%
81.51%
1.00%
POCR
74.69%
94.71%
1.00%
PLNL 74.88%
95.15%
1.00%
1. The advantage of PLNL over previous CLL methods still exists in biased settings, which demonstrates the robustness of PLNL, For example, under CIFAR-10 ("without 0"), PLNL outperforms previous SOTA by 9.79%.
2. All CLL methods cannot converge on biased CIFAR-100.
G.6 ABLATION STUDY THE DIFFERENT NLE STRATEGY ON MODERATELY--CNFIDENT AND UNDER-CONFIDENT
In our method, dividing the dataset into three parts is much more natural than two parts. Since train a two-view network for instance selection, it naturally divides the whole dataset into three parts based the number of the output confidences of the two networks meeting the selection criteria:
Highly-confident: both of two confidences meet the criteria
Moderately-confident one of the two confidences meets the criteria
Under-confident: both two confidences do not meet the criteria
Since the model is under-learned for under-confident instances, the feature space of under-confident instances might be inaccurate, performing NLE based on this would lead to considerable error. We show the NLE error rate of two strategies in the following table. "PLNL w/ same strategy" denotes treating the moderately-conficee and under-confident instances the same way.
Table 12:
Comparison of NLE error rate e2 between different strategies of treating the moderately- confident and under-confident instances.
Method
CIFAR-10 (SCLL)
CIFAR-10 (MCLL)
CIFAR-100 (MCLL)
PLNL same strategy PLNL
3.42 + 0.06%
2.11 + 0.12%
25,36
0.09%
2.21 + 0.09 %
1.09 + 0.07%
19.16 0.04% %
And the final classification accuracy increases significantly under PLNL strategy.
can be seen from the above tables that the separate treatment strategy used by PLNL outperforms the same treatment strategy.
24

---

Published as a conference paper at ICLR 2025
Table 13: Comparison of classification accuracies between different strategies of treating the moderately-confiden and under-confident instances.
Method
CIFAR-10 (SCLL)
CIFAR-10 (MCLL)
CIFAR-100 (MCLL)
PLNL w/ same strategy PLNL
93.98 + 0.15%
95.89 = 0.24%
62.25 = 0.34%
94.78 + 0.12%
96.80 0.28%
64.33 = 0.43%
G.7 EXTRACT FEATURES BASED ON VISUAL LANGUAGE MODELS (VLMs) AND SELF-SUPERVISED LEARNING (SSL) TECHNIQUES
In the paper, we compute K-NN instances based on the model output space information, namely the feature extracted by the model itself. It strikes us that different features may have much to do with the NLE performance. To confirm this, we employ different feature extractors for computing k-NN, including PreActResNet- MeeeRReeeeet---Moo I8-MoCo, BLIP-2 (Li et al., 2023). Note that these results are just for performance comparison which has nothing to with the results presented the main body of the paper. For MoCo, we train PreActResNet by self-supervised learning method MoCo (He et al., 2020) without any supervision. The weak and strong data augmentations used in MoCo follow the original configurations mentioned in the main body. Then we compute N--N the 512-dimensional feature output of the PreActResNet. For BLIP-2, we first employ the visual encoder to extract 0o8-dimensional high-quality representations and then leverage faiss (Johnson al., 2021) to compute k-NN instances in this feature space. We compute the average precision of NLE 1 e2 and accuracy on CIFAR-I0 10 (SCLL) and CIFAR-100 (MCLL). As shown in Table 14, the feature extracted from BLIP-2 outperforms MoCo and ResNet itself significantly. This shows the powerful visual representation ability of VLMs, which has great potential for facilitating innovation in weakly-supervised learning in the future.
Table 14: Comparison of classification accuracies and NLE precision between different methods on CIFAR- 100 with multiple complementary labels per instance. PreActResNNt--1 18 denotes leveraging the model output space information for k-NN calculation
CIFAR- 10, SCLLI
CIFAR- 100, MCLL Accuracy 1
Feature Extractor
Accuracy
1-
MoCo
93.12%
95.64%
61.82%
75.34%
BLIP-2
95.84% %
99.91 %
69.85 %
93.34%
PreActResNNtt118
94.78%
97.79%
64.33%
80.84%
G.8 COMPARISON WITH SEMIREWARD
We further compare the performance of PLNL with of the recently published SSL method SemiReward (Li et al., 2024). It can be seen that PLNL still outperforms SemiReward significantly in selection ratio and average size of NL..
H DEVIATION REPORTS OF TABLE 3 AND TABLE
We re-tested and added deviation terms in Table and Table 4 of the paper, with results respectively shown in Table 15 and Table 16.
Table 15: The performance of PLNL. with single network on two settings.
CIFAR-10 SCLL
CIFAR-100 MCLL
Method
?)
1-61
1-G1
Single
84.65+:0. 12%
90.21
67.43+10.24%
70.62+00.1%%
Two-view
93.40:10.14%
96.7910.08%
76.08:10.22%
79.8410.419 %
25

---

Published as a conference paper at ICLR 2025
1.0
Ave. Size of NUS
Ratio
0.7
0.0
PLNL
PLNL
0.4
Hxmatch
freematch
Ireemetch
Fixmatch
0.3
Roward
Scmi Reward
50
100
150
200
55
100
150
200
Epoch
Epoch
Selected Ratio Epoch
Ave. Num. NLS Epech
Figure 4: The experiments is conducted on CIFAR-10 10 with single complementary labels (SCLL). (a) shows that selected ratio of PLNL trenscends Fixmatch, Freematch and SemiReward significantly. (b) shows that average size of NLS of PLNL is significantly larger due to specially designed technique NLE for enhancing the untrustworthy negative labels. Nearly all negative lahels are revealed at the end of training, almost reaching 9 negative labels for each instances in CIFAR-10.
Table 16: Classification accuracy of degenerated methods three settings.
STL-10 SCLL
CIFAR-10 10 SCLL
CIFAR-100 100 MCLL
Method
PLNL
55.25.10.35%
0..12%
64.33.L0.43%
PINL vl
49.25+t0.41%
93.75--0.08%
63.09:t0.27%
PLNL
49.82+10.39%
92.01=0.1129
58.94400.31%
P.NL v3
53.22++0.3%%
94.28++0.108
63.14:0..32%
POCR
34.96:0..2%%
94.15=:0.09%
53.16:0.111%
I DETAILED DERIVATION OF EQ. (30)
1 N R(()) = Σ
Lou(( Pt),
N
N
(((()),))
(50)
K K- 1
This step is due to the definition of CLL loss function:
CCLL (CLL(f()).8)
E - 18,1
1
((f(z).))
Then we have:
(i(
1 N Σ
(f((.)).
1 N N
Σ
I( $ Y:)
Σ
1
(ff(x)), c)
K - K
e(f(x)) v.
N
K
K
E=1
i=1
Lof o..i.yy
N Σ
+
I( E Pi)
Σ
v1)
(51)
N
K
Y
LoeY.
The first term the loss on the ground-truth label, summing up to the empirical risk R()) The second and third term is the difference between empirical risk R(f) and practical empirical risk with pseudo-labeling error R' (f).
26

---

Published as a conference paper at ICLR 2025
Since pseudo-labeling enror may occur during PLG and NLE processes, the ground-truth -ruuthtruthh label of æ; may be mistakenly included or correctly excluded in the enhanced negative label set Pz. We discuss two situations separately (i.e. lyy E Y, and 11y, & Y)). We extract the empirical risk term R(f) by subtracting the equivalent value in the second and third terms, which is shown between square brackets above.
As {ff())))) y) is bounded by a positive value B. We can scale up the second and third terms by directly removing the terms after minus sign, which is double underlined above, which will yield the following line.
N I(y & Pi) Σ
R(f)+
1
Σ
1 [(f(zz)).). K- - Y/
N
1
I(
Y,)
Σ
{(f(z)),
(52)
N
K [Pll
oRV;
Then we utilize Jensen's 's Inequality for further scaling up. Jensen's Inequality for concave function yo:
Y Σ
(((())))>,
where )2 +.... An 1, 1,
We first scale the second term in Eq. (52). Here, the concave function is .(Ii)
where A v. since Eegr,eoy ((((x)), c) indicates the sum of binary losses on non-complementary
K K-
labels & Yr, excluding the ground-truth label yt- The number of non-complementary labels is
K [2/. excluding the ground truth label will get K Ý.1 - 1, which means computing the binary loss (ff(z).. c) for K- 1871 times. Finally, since & bounded by B, we can make such a scale:
Σ
1
((f(x.))
K [Y]
of 1 y
N
K
B
N i=1
K - Y/
- 1 N
1=
B.
(53)
K 1 Σ 1= PY
Since we have defined that 3 =
N Σm
1
and I(us $ 8.)
= 1
we have
N
K 1 Σソ
(y: $ vi)
N
K K- N
Σ
Y
1=1
K 1
$ (1
(54)
K-3
The third term in Eq. (52) follows similar scaling procedures.
27

---

Published as a conference paper at ICLR 2025
J COMPARISON BETWEEN CLL AND PARTIAL LABEL LEARNING (PLL)
CLL relieves the efforts for Data Annotation. CLL and partial label learning (PLL) distincts intrinsically in the data annotation stage. From the perspective of data annotation, PLL still requires true label being selected while CLL only requires classes the instance does not belong to, which makes data annotation less laborious.
Moreover, CLL data annotation reduce the complex process of labeling data into much easier "yes/no" question. For each instance, answering "yes/no" question naturally gives either a true label or complementary label. This logic of creating datasets is creative and time-efficient, which has great potential in the future.
Most importantly. CLL certainly provides machine learning community new perspective of viewing data annotation and label distribution.
CLL shows promise in Privacy Field. The formulation of learning from complementary labels may also be useful in the context of privacy-aware machine learning: a subject needs to answer private questions such psychological counseling which make him/her hesitate to answer directly. In such a situation, providing a complementary label, i.e. one of the incorrect answers to the question, would be mentally less demanding. The issue will surely be investigated in the future.
CLL and PLL are indeed related. CLL and PLL can enlighten and learn from each other in terms of methodology, etc.
In conclusion, the problem settings are intrinsically different. Both CLL and PLL is reasonable and deserves further investigation and research.
The advantages of PLNL over existing PLL methods (motivationally and experimentally). Experimentally, we supplement two SOTA partial label learning (PLL) methods: DPLL (Wu et al., 2022) and PiCO+ (Wang al., 2024) for comparison. The results are shown in Table 17 as follows.
Note that for the transformation from CL datasets to PL datasets, we conduct this by simply taking the complement of complementary label sets candidate label sets.
Table 17: Results comparing DPLL,, PiCO+, and PINN. across multiple test cases.
Method
CIFAR-10 SCLL
CIFAR-10 MCLL
CIFAR-100 SCLL
CIFAR-100 MCLL
DPLL
93.9810.00%%
95.4910.11%
1.00%
61.4710.21%
PiCO+
94.4310.077%
95.35=0.08%%
1.00%
61.2510.32%
PLNL
94.78-10.12%
96.80=0.28%%
1.00%
64.33:10.43% %
can be seen from the results that PLNL outperforms PLL SOTAs in all test cases.
28


Reviews:
[{"review_id": "QvnVfQnj68", "reviewer": "Reviewer_ocgG", "summary": "In this paper, the authors address the complementary label learning problem by performing positive label guessing (PLG) and negative label enhancement (NLE). The authors prove the generalization error bound and the error rates bounds. Extensive experiments demonstrate the superiority of the proposed method.", "questions": "1.\tIn Figure 2(b), the PLG precision decreases as the training progresses, while the NLE precision remains relatively stable, please explain this.\n2.\tWhy do you report the method POCR in Table 4?\n3.\tPlease give the detailed derivation of Eq.(30), especially the first inequality.\n4.\tThere are some typos, e.g., in Eq.(32), “B” is missing, in line 134, “show” should be “shown”, in line 169, ”p” should be “f”, in line 216, “are” should be “is”, and in Figures 2(b) and 2(c), “Precison” should be “Precision”.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe authors provide theoretical generalization error bound for their proposed method.\n2.\tThe results of the experiments verify the effectiveness of the method.\n3.\tThis paper is well-organized and easy to understand.", "weaknesses": "1.\tAccording to Eq.(21), the upper bound of the PLG error rate ranges from 0 to 1, which is too broad and meaningless. And it is not easy to estimate the interval of the error bound in Eq.(22). It would be more meaningful if the authors could show that the upper bounds for these error rates are small numbers close to zero.\n2.\tMost datasets used in Tables 1 and 2 are relatively easy, it would be better if data set such as 20 Newsgroups is included for comparison.\n3.\tSome of the experimental results need further explanation, please refer to the questions below.", "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": "dXW2ejAoWG", "reviewer": "Reviewer_K6ZB", "summary": "This paper proposes a new Complementary Label Learning (CLL) method called PLNL (Positive Label Guessing and Negative Label Enhancement), which solves the CLL problem by decomposing the inverse problem into two subtasks, positive label guessing (PLG) and negative label enhancement (NLE). Specifically, PLNL classifies training instances into three categories based on the confidence evaluation of the model output: high confidence, medium confidence, and low confidence, and performs PLG and NNE on them respectively. This paper also proposes a unified framework that considers PLG and NLE as the process of negative label recovery, and theoretically proves that the error rates of PLG and NLE have upper bounds, thus enabling the construction of a model consistent with classifiers learned using clean and complete labels.", "questions": "Please see the weaknesses above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.This paper provides a novel solution for the CLL field by transforming the CLL problem into an inverse problem that outputs spatial information and decomposing it into two subtasks, PLG and NLE.\n2.This paper also provides a theoretical upper bound proof of error rate, enhancing the credibility and effectiveness of the method.", "weaknesses": "1. The performance of PLNL may be sensitive to parameter selection, such as k-NN parameter k and confidence threshold λ, which requires users to make detailed parameter adjustments when using it.\n2.Although PLNL has performed well in experiments, its generalization ability on different datasets and tasks of different complexities still needs further validation.\n3.The k-NN computation involved in PLNL may have high computational costs on large-scale datasets, which may limit its application in resource-constrained environments.", "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": "IrTeFFf8hI", "reviewer": "Reviewer_Gske", "summary": "The paper introduces PLNL, a new method for complementary label learning that leverages positive label guessing and negative label enhancement based on a confidence-based instances selection module. Through a unified framework and theoretical analysis, it demonstrates the effectiveness of PLNL, achieving state-of-the-art results in CLL.", "questions": "1. In the ablation study, it appears that the weak-strong data augmentation strategy is more effective than the proposed confidence-based instance selection strategy.\n\n2. The settings outlined in Table 1 are lacking experimental results for the CIFAR100 dataset.\n\n3.  The number of SOTA methods employed in the experiments is insufficient: only one SOTA method (published in 2023 or 2024) is used, which is inadequate and too weak to validate the effectiveness of the proposed method.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is written clear and easy to understand.\n\n2. This paper proposes a new method PLNL for CLL by PLG and NLE.\n\n3. Extensive experiments demonstrate the effectiveness of PLNL over the SOTA CLL methods.", "weaknesses": "The contribution of this paper is incremental and using a commonly used confidence based instance selection strategy. Moreover,  only one SOTA method (published in 2023 or 2024) is used and it is too weak to validate the effectiveness of the proposed method.", "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": "9vwLOv9cVS", "reviewer": "Reviewer_K5tE", "summary": "This paper solved the complementary label learning problem by dividing the training instances into three categories: highly-confident, moderately-confident and under-confident. Then, it performed positive label guessing (PLG) and negative label enhancement (NLE) according to the categories of the instances. In addition, it unified PLG and NLE into a consistent framework. It also studied the bounds of the error rates of both PLG and NLE.", "questions": "1. Please consider the point 1 and 2 in the weaknesses.\n2. How to evaluate the contribution of the separation of moderately-confident and under-confident instances?\n3. Assumption 1 should be reconsidered and carefully checked. It assume that the variety of negative labels is large enough in the KNN instances. However, I think this assumption is too strict.\n4. Is there any difference between the supervised and complementary learning losses for the high-confident instances? Maybe there are different from the loss gradient perspective.\n5. The negative label set size in eq.(15) is fixed at $\\tau_i$. However, when the top-$\\tau_i$ and the complementary label is largely overlapped in the multiple complementary label setting, the benefit from the complementary label sharing mechanism is largely weakened.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The study of generalization error bound is useful for algorithm evaluation.\n2. The improvement in empirical study is significant.", "weaknesses": "1. There is no performance reported under biased complementary label learning settings.\n2. There is no performance reported under manually annotated datasets, such as CLCIFAR10，CLCIFAR20. In addition, the results on these manually annotated data indicates the performance under instance-depedent CLL.\n3. The semi-supervised learning methods used in this paper is not the SoTA ones.\n4. There is no deviation reported in Table 3 and Table 4. It is suggested to add standard deviations or confidence intervals for the results, which would help readers better assess the statistical significance and reliability of the reported performance.\n5. The study of the separation of moderately-confident and under-confident is not reported in the ablation. It will be helpful for evaluate the idea by comparing the performance when treating these two categories the same versus separately.", "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": "eEswAFYy5g", "reviewer": "Reviewer_zFpU", "summary": "This paper proposes to decompose the CLL problem into multi-class classification problems. The one is to infer the positive label by a positive label guessing method, and another is to infer the negative labels by enhancing the negative labels of the moderately-confident and under-confident instances. Besides, this paper provides the upper bounds for the error rate of positive label guessing method and negative label enhancement method, and the effectiveness of the proposal is demonstrated by several experiments.", "questions": "1. What is the difference between partial label learning and the problem addressed in this paper?\n2. What are the advantages of the proposed algorithm over other existing algorithms (including CLL and partial label learning)?\n3. What are the conditions for the proposed algorithm?\n4. What do Theorem 2 and Theorem 3 reveal?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper proposes a new method for CLL, which divides the CLL into two subtasks: PLG and NLE to deal with the high-confident and low-confident instances separately. The authors also verify the effectiveness of the proposal by several experiments and theorems.", "weaknesses": "1. This paper attempts to learn a multi-label classifier from CL. However, the difference between CL and partial labels is not clarified. Initially, Ishida proposed complementary label learning, and noted that complementary label y can be regarded as an extreme case of partial labels given to all K −1 classes other than class y. However, in lines 48 and 121 of this paper, the authors claim that CL can be multiple classes that the instance does not belong to, which seems to fundamentally eliminate the difference between partial label and CL.\n2. This paper does not well-motivate the proposed method, so that its advantages over existing methods are not clear. It is also not clear what conditions make the proposed method work or fail. Besides, given the strong relevance of this paper and partial label learning, it is not yet clear what advantages the algorithms in this paper have over existing partial label learning algorithms, either motivationally or experimentally.\n3. Theorem 2 and Theorem 3 do not give valuable information. For example, the theorem presented in Equation (21) seems to say one thing that a probability value does not exceed 1. Furthermore, the author's discussion of Theorems 2 and 3 is very shallow; they just tell readers that there is an upper bound on the error rate, which is meaningless because any error rate has an upper bound of 1.", "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)