CLImage: Human-Annotated Datasets for Complementary-Label Learning
Authors: Hsiu-Hsuan Wang
Mai Tan Ha
Nai-Xuan Ye
Wei-I Lin
Hsuan-Tien Lin
Venue: Accepted by TMLR ()

Abstract: Complementary-label learning (CLL) is a weakly-supervised learning paradigm that aims to train a multi-class classifier using only complementary labels, which indicate classes to which an instance does not belong. Despite numerous algorithmic proposals for CLL, their practical applicability remains unverified for two reasons. Firstly, these algorithms often rely on assumptions about the generation of complementary labels, and it is not clear how far the assumptions are from reality. Secondly, their evaluation has been limited to synthetically labeled datasets. To gain insights into the real-world performance of CLL algorithms, we developed a protocol to collect complementary labels from human annotators. Our efforts resulted in the creation of four datasets: CLCIFAR10, CLCIFAR20, CLMicroImageNet10, and CLMicroImageNet20, derived from well-known classification datasets CIFAR10, CIFAR100, and TinyImageNet200. These datasets represent the very first real-world CLL datasets, namely CLImage, which are publicly available at: https://github.com/ntucllab/CLImage_Dataset. Through extensive benchmark experiments, we discovered a notable decrease in performance when transitioning from synthetically labeled datasets to real-world datasets. We investigated the key factors contributing to the decrease with a thorough dataset-level ablation study. Our analyses highlight annotation noise as the most influential factor in the real-world datasets. In addition, we discover that the biased-nature of human-annotated complementary labels and the difficulty to validate with only complementary labels are two outstanding barriers to practical CLL. These findings suggest that the community focus more research efforts on developing CLL algorithms and validation schemes that are robust to noisy and biased complementary-label distributions.

Published in Transactions on Machine Learning Research (06/2025)
CLImage: Human-Annotated Datasets for Complementary- Label Learning
Hsiu-Hsuan Wang'
w099022027@csiccvuu.cco
Department of Computer Science and Inforrattin Engineering National Taiwan University
Tan-Ha Mai
k1092202/@cssee.cee edu..
Department of Computer Science and Information Engineering National Taiwan University
Nai- Xuan Ye
6099022008@csie.rttv edu. tw
Department of Computer Science Information Engineering National Taiwan University
Wei-I Lin
r109220768ccsic.tttv. edu.
Deportment of Compuuuer Science and Information Engineering National Taiwon University
Hsuan-Tien Lint
htlin@tcsie. edu.
Department of Computer Science and Information Engineering National Taiwan University
Reviewed on OpenReview: https: // openreview. net/ ftte/ffrmm id=FHNWY4GGsi
Abstract
Complementary-label learning (CLL) is a weakly-supervise learning paradigm that aims to train multi-class classifier using only complementary labels, which indicate classes to which an instance does not belong. Despite numerous algorithmic proposals for CLL, their practical applicability remains unverified for two reasons. Firstly, these algorithms often rely on assump- tions about the generation of complementary labels, and it is not clear how far the assumptions are from reality. Socondly, their evaluation has been limited to synthetically labeled datascts. To gain insights into the real-world performance of CLL algorithmss, we developed a protocol to collect complementary labels from human annotators. Our efforts resulted the creation of four datasets: CLCIFAR1O, CLCIFAR20, CLMierolmageNeet. and CLMierolmageNNt220, dcrived from well-known classification datasets CIFAR10, CIFAR100, and TinyImageNet200.. These datasets represent the very first real-world CLI datasets, namely CLImage, which are publicly available at: https:// httpt/hwww...coo/tccll/laa/aa//a [latteeaatttttt Dataset Through ex- tensive benchmark experiments, we discovered a notable decrease in performance when transitioning from syuthetically labeled datasets to real-world datasets. We investigated the key factors contributing the decrease with a thorough dataset-level ablation study. Our analyses highlight annotation noise as the most influential factor in the real-world datasets. In addition, we discover that the biased-nature of human-annotated complementary labels and the difficulty to validate with only complementary labels two outstanding barriers to practical CLL. These findings suggest that the community focus more rescarch efforts on developing CLL algorithms and validation schemes that are robust to noisy and biased complementary-lie distributions.
"These authors contributed equally to this work. t "Corresponding author.

---

Published in Transactions on Machine Learning Research (06/2025)
1 Introduction
Ordinary multi-class classification methods rely heavily on high-quality labels to train effective classifiers. However, such labels can be expensive and time-consuming to collect in many real-world applications. To address this challenge, researchers have turned their attention towards weakly-supervised learning, which aims to learn from incomplete, inexact, or inaccurate data sources (Zhou 2018 Sugiyama et al. 2022). This learning paradigm includes but is not limited noisy-label learning (Frénay & Verleysen 2014), partial-label learning (Cour et al., 2011 positive-unlaeled learning (Denis 1998), and complementary-kan learning [Ishida et al. 2017).
In this work, we focus on complemeentary-label learning (CLL). This learning problem involves training a multi-class classifier using only complementary labels, which indicate the classes that a data instance does not belong to. Although several algorithms have been proposed to learn from complementary labels, they were only benchmarked on syuthetically labeled datasets with some idealistic assumptions on complementary-
generation [Ishida et al., 2017 2019; Chou et al. 2020 Wang al., 2021 Liu al. 2023). Thus, it remains unclear how well these algorithms perform in practical scenarios.
In particular, current. CLL algorithms heavily rely on the uniform assumplion for generaling complementary labels (Ishida et al. 2017), which specifies that complementary labels are generated by uniformly sampling from the set of all possible complementary labels. To alleviate the restrictiveness of the uniform assumption, (Yu et al. 2018) considered a more general conditiond assumption, where the distribution of the complementary labels only depends on its ordinary labels. These assumptions have been used in many subsequent works to generate the synthetic complementary datasets for examining CLL algorithms (Ishida et al. 2019 Chou et al. 2020 Feng et al., 2020 Wang et. al. 2021 Wei et al.) 2022 Liu et al.) 2023). Although these assumptions simplify the design and analysis of CLL algorithms, it remains unknown whether these assumptions hold true in practice and whether violation of these assumptions will significantly affect the performance of CLL algorithms. In addition to the uniform or class-conditional assumptions, most existing studies implicitly assumes that the complementary labels are noise-free. That is, they do not mistakenly represent the ordinary labels. While some studies claim to be more robust to noisy complementary labels (Lin) & Lin 2023), they were only tested on synthetic scenarios. It remains unclear how noisy the real-world datasets are, and how such noise affects the performance of current. CLL algorithms.
To understand how much the real-world scenario differs from the assumptions, collect complementary-labe datasets and conduct benchmarking experiments. We begin by constructing the CLCIFAR10 and CLCIFAR21 R20 datasets, derived from the widely used CIFAR datasets for multi-class classification (Krizhvskyy) 2009). Building upon this foundation, we further extend our collection to include two additional Tin2mmageNet200 (Le & Yang) 2015). For all four datasets, we analyze the collected complementary labels, including their noise rates and non-uniform nature. Then, we perform benchmark experiments with diverse state-of-the-art CLL algorithms and conduct dataset-level ablation study on the assumptions of complementary-llbeel generation using the collected datasets.
datasets, CLMierolmaaeNNe110 and CLMicrolmageNett2., derived from
Our studies reveal annotation noise as the most influential factor affecting the performance of CLL algorithms in real-world datasets. The claim is evidenced by our ablation study results on both synthetic and real-world complementary datasets. Notably, classification accuracy drops from 64.18% on CIFARIO to 34.85% on CLCIFAR1O, highlighting the detrimental impact of noisy complementary labels. To further investigate the role of label noise in the performance gap across different CLL algorithms, we conducted an ablation study that examined various noise levels. The results consistently reinforce our conclusion that the performance disparity between hunan-annotated complementary labels and synthetically generated complementary labels is primarily driven by label noise. Moreover, through thorough analysis we confirmed that the non- non-uni uniform nature of human-annotated complementary labels makes certain CLL algorithms more susceptible to overfitting, although its impact less pronounced compared to label noise.
These findings immediately suggest that the community focus more research efforts on developing CLL algorithms that are robust to noisy and non-uniform complementarr-label distributions. In addition, we used the collected datasets to demonstrate that existing complementary--abeeeee validation schemes are not
2

---

Published in Transactions on Machine Learning Research (06/2025)
mature yet, suggesting the community a novel research direction for making CLL practical. Our contributions are summarized as follows:
We designed a collection protocol of complementary labels (CIs) for images, and verified that the protocol collects reasonable human-annotated CLs across different datasets.
We collected the set of four real-world CL datasets and plan to release CLImage to support the continuous research of the community.
We analyzed the collected datasets with extensive benchmarking experiments, which provides novel and valuable insights for the community.
2 Preliminaries on CLL
2.1 Complementary-labe learning
In ordinary multi-class classification, dataset D {(,, W4)l= that is í.í.d. sampled from an unknown distribution is given to the learning algorithm. For each i, x; TR represents the M-dimension feature of the i-th instance and E [K] (1,2...., }} represents the class x; belongs to. The goal of the learning algorithm is to learn a classifier from D that can predict the labels of unseen instances correctly. The classifier is typically parameterized by a scoring function g: RM + RK and the prediction is made by arg [a g(x)x given an instance x, where g(x)): denotes the k-th output of g(x). In contrast to ordinary multi-class classification, CLL shares the same goal of learning classifier but trains with different labels. In CLL, the ordinary label y, is not accessible to the learning algorithm. Instead, complementary label in is provided, which is class that the instance does not belong to. The goal of CLL is to learn a classifier that is able to predict the correct labels of unseen instances from a complementary-labd dataset D {(x,, F=)
2.2 Common assumptions CLL
Researchers have made some additional assumptions on the generation process of complementary labels to facilitate the analysis and design of CLL algorithms. One common assumption is the class condiiconiiiinnall assumption YYu et al., 2018). It assumes that the distribution of a complementary label only depends on its ordinary label and independent of the underlying example's 's feature, i.e,, P(ye xi, = P (e) for each One special case of the class-conditional assumption the uniform assumplion, which further specifies that the complementary labels are generated uniformly. That is, P(y kly;
रニ for all k E [K]]]
[Ishida al. 2017 2019
Lin & Lin 2023).
For convenience, a K x K matrix T, called transition matria, is often used to represent how the complementary labels are generated under the cass-connitional assumption. Ti is defined to be the probability of obtaining a complementary label k if the underlying ordinary label is j, i.c., T2 = P(ý = k y j) for cach j. k E [K]. The diagonals of T hold the conditional probabilities that a complementary label mistakenly represents the ordinary label. That is, they indicate the noise level of the complementary labels. When T contains all zeros its diagonals, the CLL scenario is called noiseless. For instance, the uniform and noiseless assumption can be represented by T3 0 for each [K] and Ty, k- for each le + Class-conditional CLL scenarios based on any other non-uniform T are often called biased.
2.3
A brief overview of CLL algorithms
The pioneering work by Ishida et al. (2017) studied how to learn from complementary labels under the uniform assumption by converting the risk estimator in ordinary multi-class classification to unbiased risk estimator (URE) in CLL (Ishida et al. of negative empirical risks, and is upgraded gradient accent (URE-GA) (Ishida et al.
2017). URE is then found to be prone to overfitting because with two tricks, non-negative risk estimator (URE-NN) and
2019 The surrogate complementary loss (SCL) algorithm mitigates the overfitting issue URE by a
different. loss design that decreases the variance of the empirical
https://github www.///ccllla/llaeaeeeeeooo DDtaast
3

---

Published in Transactions on Machine Learning Research (06/2025)
estimation. However, these algorithms either rely on the uniform assumption in design or are only tested on the synthetically labeled datasets that obeys the uniform assumption.
To make CLL one step closer to practice, researchers have explored algorithms to go beyond the uniform (and thus noiseless) assumption. (Yu al. 2018) utilized the forward-corection loss (FWD) to accommodate biased complementary label generation by adapting techniques from noisy label learning (Patrini et al. 2017] to change the loss. Additionally, (Gao & Zhang 2021) proposed the L-W algorithm based on discriminatively modeling the distribution of complementary labels through a weighting function, further improving the
performance in bias scenario. Furthermore, (Ishiguro et al.) 2022) designed robust loss functions for learning from noisy CLs, including MAE and WMAE, by applying the gradient ascent technique (Ishida et al. 2019 to handle noisy scenarios.
Besides CLL algorithms, crucial component for making CLL practical is model validation. In ordinary-label learning, this can be done by naively calculating the classification accuracy on a validation dataset. In CLL, this scheme can be intractable if there are not enough ordinary labels. One generic way of model validation is based on the result of [Tshida. et al. 2019) by calculating the unbiased risk estimator of the zero-one loss, i..,
Roi
v.. (T (oo)((())))
N 1=1
where eq, denotes the one-hot vector of D.. (g(()) denotes the K-dimensional vector (for (g(x)), (on (g(x)),, K))", and foi (g(x.),),, = 0 if arg maxxe[k] g(x;) = k and 1 otherwise, rep- resenting the zero-one loss of g(æ,) if the ordinary label is k. This estimator will be used in the experiments in Section Another validation objective, surrogate complementary csimation loss (SCEL), was proposed by (Lin & Lin 2023). SCEL measures the log loss of the complementary probability estimates induced by the probability estimates on the ordinary label space. The formula to calculate SCEL is as follows,
(g) N
log (eTTT" softmax(g(x:)))
(2)
3 Construction of the CLimage collection
In this section, introduce the four complementtar--laelled datasets that collected, CLCIFAR10, CLCIFAR20, CLMiccolmageNet100 and CLMicrolmageNet200, All datasets are labeled by human annotators on Amazon Mechanical Turk (MTurk 2
3.1 Datasets and goals
The complementary--abblle datasets are derived from ordinary multi-class classification datasets. CIFARIO, CIFAR100 and TinylmageNet200 (Krizhevsky 2009 Le & Yang) 2015 Russakovsky et al.] 2015 This selection is motivated by the real-world noisy label dataset by (Wei el al. 2022). Building upon the CIFAR and Tiy2ImageNet200 datasets allow us to estimate the noise rate and the empirical transition matrix easily, as they already contain nearly noise-free ordinary labels. In addition, many of the state-of-the-art CLL algorithms have been benchmarked on synthetic complementary labels with the CIFAR datasets (Dosovitskiy et al. 2021 Kolesnikov et al. 2020 Oquab et al.] 2024h. Our CL.CIFAR counterparts immediately allow a fair comparison to those results with the same network architecture.
In addition to our CLCIFAR extensions, we are the first to introduce loag>)mmaeeeeeeeeeee datasets to the CLL literature. Such datasots serve two purposes. First, allows us to confirm the validity of our collection protocol and findings beyond CIFAR-derived datascts. Second, ImageNet knowingly contains images of higher complexity than CIFAR and can thus be used to challenge the ability of existing CLL algorithms more realistically.
There is a historical note that is worth sharing with the community: We initially attempted to collect complementary labels based on the 100 classes in CIFAR100. But some preliminary testing soon revealed
hhttpp://www http:://wwwwwtt///ee com/
4

---

Published in Transactions on Machine Learning Research (06/2025)
that state-of-the-art CLL algorithms cannot produce meaningful classifiers for 100 classes even synthetic complementary labels that are uniformly and noiselessly generated. We thus set our collection goals to be 10-class classification, which is the focus of most current CLL studies, and 20-class classification, which exlends the horizon of CLL and matches the super-class structure CIFAR.
3.2 Complementary label collection protocol
To collect only complementary labels from the CIFAR, TinylmageNet datasets, for each image in the training split, we first randomly sample four distinct labels and ask the human annotators to select any of the incorvect one from them. To leave room for analyzing the annotators' behavior, each image labeled by three different annotators. The four labels re-sampled for each ammotator on each image. That is, each annotator possibly receives different set of four labels to choose from. An algorithmic description of the protocol is as follows. For each image
1. Uniformly sample four labels without replacement from the label set [K].
Ask the annotator select any one of the complementary label 7 from the four sampled labels.
3. Add the pair (x,7) to the complementary dataset.
Note that if the annotators always select one of the correct complementary labels uniformly, the empirical transition matrix will also be uniform in expectation. We will inspect the empirical transition matrix in Section The labeling tasks are deployed on MTurk by dividing them into smaller we first divide the total images into smaller human intelligence tasks (HITs). For instance, for constructing the CLCIFAR datasets, we first divide the 50,000 images into five batches 10,000 images. Then, each batch further divided into 1,000 HITs with each HIT containing 10 images. Each HIT is deployed to three annotators, who receive 0.03 dollar as the reward by annotating 10 images. To make the labeling task casier and increase clarity, the size of the images are enlarged to 200 200 pixels.
4 Dataset Characteristic
Next, we closely examine the collected complementary labels. We first analyze the error rates of the collected labels, and then verify whether the transition matrix is uniform or not. Finally, we end with an analysis on the behavior of the human annotators observed in the label collection protocol.
20000
2200
Number of CL Collected
Collected
1800
16000
1800
14000
12000
1200
10000
pirpann
astomdble
truck
Ship
torne
d54
bird
cai
deer
1000
toch
backnack
Scandal
aud bunterfyy
m- m-cerspaes
Bintoro
ap
caedigan
Complementary Label
Complementary Label
(a) CLCIFAR10
(b) CLMiecolmmageNet10
Figure 1: The label distribution of CLCIFAR10 and CLMicrolmageNet10 datasets.
Observation 1: noise rate compared to ordinary label collection We first look the noise rate of the collected complementary labels. A complementary label is considered to be incorrect if it is actually the ordinary label. The mean error rate made by the human annotators is 3.93% for CLCIFAR10, 2.80% for

---

Published in Transactions on Machine Learning Research (06/2025)
CLCIFAR20, 5.19% for CLMicrolmageNet100 and 3.21% for CLMicrolmageNet20. In theory, we can estimate a random annotator achieves a noise rate of _े for complementary label annotation and a noise rate of K-1 for ordinary label annotation. If we compare the human annotators to a random annotator, then for CLCIFAR10, human annotators have 60.7% less noisy labels than the random aunolator whereas for CIFARIO-N, human anotators have 78.17% less noisy labels. This demonstrates that human annotators are more competent compared to random annotator in the ordinary-label annotation. Similarly, human annotators have 44% less noise than random annotator for CLCIFAR20 and 73.05% less noise for CIFAR10ON-coars (Wei et al. 2022 This observation reveals that while the absolute noise rate is lower in innotating complementary labels, it may be more difficult to be competent against random labels than the ordinary label annotation.
K
Observation 2: imbalanced complementary label annotation Next, we analyze the distribution of the collected complementary labels. The frequency of the complementary labels for the CLCIFAR10 and CLMierolmageNet10 (CLMIN10) datasets are reported in Figure !
As we can see in the figure, the
3.05
0.23
0:32
0.13
0.33
2.32
0.07
0.32
sul-zurterty
0.04
0.22
0.09
0.11
0.07
2:3
0.54
0.31
0.07
automobile
0:1
0.36
barkpack
0.4
0.16
4.4
brd
0.34
0.19
0.54
0.0
E:0
0.93
0.29
3.09
0:11
0.5
card cardigar
0.12
0.5
0.00
000
0.59
3.0
532
0.54
0.7
8.0
deer
1:17
6.17
0.24
0.66
6m0
0:07
0.28
3.55
6.12
0.11
TD: m--c0pa0
0.13
0:11
6000
0.35
3.27
5113
6.11
0.15
0.04
60g
o000
tag
0:16
0.16
0.27
0.07
0.07
0.24
6:12
0.13
sanda
0.22
0:2
8:00
0:30
0.29
0.00
2.04
0.34
0.22
0.07
1005e
8:16
0.24
0.00
0.03
0.34
0:11
0.54
0.15
0:33
000
0.11
2:12
6.07
0.1
0.00
3.08
ship
2:1
0:11
6:10
017
016
021
brakk
0:30
0:08
0:2
0:2
6:11
0.2
022
1:32
0.00
0.34
1/4
46c
0.00
0:22
0:07
007
0.53
3.7
235
0.14
022
0:00
KM
Aeplere
butterfy
Aeckpack
cprigon
Almarr
complementary Labels
Comp ementary Lagels
(a) CLCIFARR0
(b) CIMicrolmageNet10
Figure 2: The empirical transition matrices of CLCIFAR10 and CLMicrolmageNet10.
annotators exhibit specific biases towards certain labels. For instance, in CLCIIFA11,, annotators prefer "airplane" and "automobile", while in CLMIN10, they prefer "pizza" and "torch". In CLCIFAR1O, the bias is towards labels in different categories, as vehicles ("airplane", "aulomobile"" versus animals ("cat", "bird"). In contrast, in CLMIN10, the bias is towards items that are easily recognizable ("pizza" and "torch") and against those that are less familiar ("cardigan" or "alp").
Observation 3: biased transition matrix Finally, we visualize the empirical transition matrix using the collected CLs in Figure 2 Based on the first two observations, we could imagine that the transition matrix is biased. By inspecting Figure 2 we further discover that the bias in the complementary labels are dependent on the true labels. For instance, in CLCIFARR0, despite we see more annotations on airplane and automobile in aggregate, conditioning on the transportation-relate labels ("airplane", "automobile" etc), the distribution of the complementary labels becomes more biased towards other animal-related labels ("bird", "cat", etc.) Furthermore, this observation holds true on CLMIN10 as well. Next, we study the impact of the bias and noise on existing CL.L algorithms.
We discovered similar patterns in all four human-annotated datasets, validating that our design methodology is practical for collecting real-world CLL image datasets. Due to space limitations, we have included the detailed analysis of CLCIFAR20 and CLMiccolmageNet220 in Appendix A.4

---

Published in Transactions on Machine Learning Research (06/2025)
5 Experiments
In this section, we benchmarked several state-of-the-art CLL algorithms on CLImage. A significant performance gap between the models trained on the humanly annotated CL,CIFAR, CIMiccollageeNe dataset and those trained on the synthetically generated complementary labels (CL) was observed in Section 5.1 which motivates us to analyze the possible reasons for the gap with the following experiments. To do so, we discuss the effect of three factors in the label generating process, feature dependency, noise, and biasedness, in Section 5.2 Section 5.3 and Section 5.4 respectively. From our experiment results, we conclude that noise is the dominant. factor affecting the performance of the CLL algorithms on CLCIFAR
5.1 Standard benchmark on CLimage
Baseline methods Several state-of-the-art CLL algorithms were selected for this benchmark. Some of them take the transition matrix T as inputs, which we call T-informed methods, including two version of forward correction Yuu et al.
2018): : FWD-U and FWD-R, two version of unbiased risk estimator with
gradient ascent (Tshida et al.
2019) URE-GA-U and URE-GA-R, and robust loss (Ishiguro et al. 2022
for learning from noisy CL: CCE, MAE, WMAE, GCE, and SI We also included some algorithms that assume the transition matrix T to be uniform, called T-agnostic methods, including surrogate complementary loss SCI-NL and SCI-EXP (Chou et al. 2020), discriminative modeling L-W and its weighted variant. (L-UW) (Gao & Zhang 2021 and pairvise-comparison (PC) with the sigmoid loss (Ishida et al., 2017]. The details of the algorithms mentioned above are discussed in Appendix [
Implementation details We collected and released three CLs per image to prepare for future studies. However, for this standard benchmark, we chose the first CL from the collected labels for cach data instances to form a single CLL datasel, ensuring reproducibility. Then, we trained a ResNet18 (He et al. 2016) model using the baseline methods mentioned above on the single CLL dataset using the Adam optimizer for 300 epochs without learning rate scheduling. Detailed results from the ablation study on various neural network architectures, which further justify our choice of ResNet18 as the backbone, are available in Appendix [A.6] The training settings included fixed weight decay of 10-4 and a batch size of 512. The experiments were run with Tesla V100-SXM2. For better generalization, BandomforizzntalFIyy
applied standard data augmentation technique, RandomCrop, and normalization to each image. The learning rate was selected from [10-3, 5 x 10-1, 10-1,5 5 x 10-5, 10-5} using a 10% hold-out validation set. We selected the learning rate with the best classification accuracy on the validation dataset. Note that here we assumed the ordinary labels in the validation dataset are known. We will discuss other validation objectives that rely only on complementary labels in Section 6 As CLL algorithms are prone to overfitting (Ishida et al., 2019 Chou et al. 2020). some previous works did not use the model after training for evaluation. Instead, previous works were performed by evaluating the model on the validation dataset and selecting the epoch with the highest validation accuracy. In this work, we also follow the same aforementioned lechnique to validate testing set. For reference, we also performed the experiments on syuthetically-geneee were generated uniformly and noisclessly, denoted uniform-CIFAR.
CLL dataset, where the CLs
Results and discussion As we can observe in Table [ there a significant performance gap between the humanly annotated dataset, CLCIFAR, and the synthetically generated dataset, -CIAR The differ- ence between the two datascts can be divided into three parts: (a) whether the generation of complementary labels depends on the feature, (b) whether there is noise, and (c) whether the complementary labels are generated with bias. A negative answer to those quest ions simplify the problem of CLL, We can gradually simplify CLCIFAR to uniform-CIFAR by chaining those assumptions as follows
DDue to space and time constraints, we only provide the results and discussion on the CLCIFAR datascts.
*Due to space limitations, we only provided the results of MAE The remaining results and discussions related to the robust loss methods can be found in Appendix A.3
NNte that FWD-R and URF-GA-R assume the empirical transition matrix Te to be provided. The empirical transition matrix is computed from the labels in the training set, so it is slightly different from uniform transition matrix Tu in the uniform-CIFA, datasets. As result, the performances of FWD-R and URE-GA-R do not exactly match those of FWD-U and URE-GA-U, respectively, in the uniform-CIFA, datasets.
TThe "interpolation" between CL.IIFAR and uniform-CIFA does not necessarily have to be this way. For instance, one can remove the biasedness before removing the noise. We chose this order reflect the advance of CLL algorithms. First,

---

Published in Transactions on Machine Learning Research (06/2025)
Table Standard benchmark results on CLCIFAR\ CLMicrolmageNett Ceaeiaageeeeeeeeieiiii (CLMIN) and uniform- uniform-CIFAR/ MicrolmageNel(MMNN datasets. Mean accuracy (+ standard deviation) on the lesting dataset from four trials with different random seeds. Highest accuracy in each column is highlighted in bold.
uniformn CIFARIO
CLCIFARIO
wilform CIFAR20
CLCIFAR20
uniform MIN10
CLMINIO
uniform MIN20
CLMIN20
PWI-U
64.1910.57
34.83.9.30
21.344
8.03.1774
36.30_1.12
23.85
12.571254
6.33.1
PWI+R
61.3220.00
38.13.0.88
21 11.5000--35
20.27
35.70
30. 00.15:1..8 1,83
1.78
10.60.0.92
URE-CA-U
50.2411::1
34. 14.42.0.40
16.67
10.49.1052
36.70
22.90_2.7
11.65.1500
5.75.10.45
UREGA-R
50.73:1185
30: 00:23:.077
17:5740061
6:17::0:8
33.65_1160
13.25
9.78433
6.50g1o-31
SCL-NL
63. 7020000
31.77 70
21.37=1118
8.02+3.36
37.05+1.cd 440
21. 21.80=1.65
13.00=2.0 80
6.17+0.40
SCL-EXP
63.2911.07
35. 18
21.57
7-70110:41
10.55_1..0
24, 14.80.11-3
12.962..938
5. 5.58 13
L-W
51.32+0.41
32, 12.90=11001
19. 50::0.00
7.71+3.56
33.80 33.80=2.66
23. 50=2.64
12, 22.70=a2.00
6. 6.40+=0
L-UW
57.52:00.50
34.0011:.32
20. (0.771.0
8.151:030
35.10=2.70
222.40 107
12. 12.12.
6.35.1 86
PC-sigmoid
37.78=0.80
52. 15=0.60
14.45400447
12:11+0.46
29.10=0,95
23.15m0.44
10.72e1.88
6.90+1..00
ROB-MAR
39.38.0.63
20. 20.23111000
18. 1-13
6-401...9
31.50=1.81
14.13g.000
6.35a 86
5.38.10.30 33
CIFAR10
CIFAR20
MIN10
MIN20
standard supervisson
02.802...5 28
63.80_0.4
68 08.70a1.58
63.90sa3 00
CLCIFAR
Section
Section
Section
uniform- CINNIR--IFRRR.
Remove dependency
Remove
Remove blaseduess
In the following subsections, we will analyze how these three factors affect the performance of the CLL algorithms.
5.2 Feature dependency
In this experiment, verified whether the performance gap resulted from the feature-dependent generation of practical CLs. Conceivably, even if two images belong to the same class, the distribution the complementary labels could be different. On the other hand, the distributional difference could also be too small to affect model performance, e-g., if P( y, x) R P(ğ y) for most x. Consequently, we decided to further look into whether this assumption can explain the performance gap. To observe the effects of approximating P(y y. x) with Pl v), we generated two synthetic complementary datasets, CLCIFARIO-HG üdd and CLCIFAR20-HH by ii.d. sampling CLs from the empirical transition matrix in CLCIFAR10 and CLCIFAR20, respectively. We proceeded to benchmark the CLL algorithms CL.CIFAR-iid and presented the accuracy difference compared to CLCIFAR in Table 2
Results and discussion From Table 2 we observed that the accuracy barely changes on the resampled CLCIFAR-id,, suggesting that even the complementary labels CLCIFAR could be feature-dependent, this dependency does not affect the model performance significantly. Hence, there might be other factors contributing to the performance gap.
Table 2: Mean accuracy difference (#: standard deviation) of different CLL algorithms. A plus indicates the performance on is calculated CI.CIAAR-...dd accuracy minus CLCIFAR accuracy.
FWD-U
FWD-R
URE-GA-U
URE-GA-R
SCI-NL
SCL-EXP
L-W
L-UW
PC-sigmoid
CLCIFARIO-Bd
-1.11217
-0.36.1.15
3..03.1.25
0.7410.3
-0.6711811
-1.97-116
-2.5.0.66
-3.53
-2.0312.05
CLCIFAREE R20-dd
-0.64=0.30
-3.502111
-0.37+0.51
1.79
-0.2820611
-0.39=0.60
-0.5+1337
.0.8220.04
-2.2420.52
5.3 Labeling noise
In this experiment, we further investigated the impact of the label noise on the performance gap. Specifically, measured the accuracy the noise-removed versions of CLCIFAR datasets, where varying percentages (0%, 25%, 50%, 75%, or 100%) of noisy labels are eliminated.
Results and discussion We present the performance of FWD trained on the noise-removed CLCIFARIO dataset in the left figure in Figure 3 From the figure, we observe a strong positive correlation between
researchers address the uniform case [shida al. 2017). then generalize to the blased case Yu et al. 2018 then consider noisy
labels [shiguro al. 2022 There work considering feature-dependent complementary labels yet.
8

---

Published in Transactions on Machine Learning Research (06/2025)
FWD-UIES)
PWD-UCES)
FWD-R FWU--RIES)
PWD-RO:SI
Accuracy
Accuracy
20
20
10
10
(25%)
(50%)
(75%)
(100%)
(25%)
(50%g)
(75%)
(100%)
Noise Rate
Noise Rate
(% of removed noisy data)
(% removed noisy data)
Figure Accuracy of FWD-U and FWD-R on the noise-removed CLCIFAR10 dataset (Left) and the Infform-CIFARIL dataset with uniform noise (Right) at varying noise rates.
the performance and the proportion of removed noisy labels. When more noisy labels are removed, the performance gap diminishes and the accuracy approaches that of the ideal uniform-CIFAR dataset. Therefore, we conclude that the performance gap between the humanly annotated CLs and the synthetically generated CLs are primarily attributed to the label noise. The results for FWD-(U/R) and SCL-(NL/EXP)) of the noise-removed CLCIFAR10 and CLCIFAR20 datasets are presented in the Figure 4 The other results for other algorithms can be found in Appendix C
5.4 Biasedness of complementary labels
To further study the biasedness of CL as a potential factor contributing to the performance gap, we removod the biasedness from the noise-removed CLCIFAR dataset and examined the resulting accuracy. Specifically, introduced the same level of uniform noise in uniform-CIFAR dataset and reevaluated the performance of FWD algorithms.
Results and discussion The striking similarity between the two curves in the right figure in Figure 3 shows that the accuracy is significantly influenced by label noise, while the biasedness of CL. has a negligible impact on the results. Furthermore, we observe that the accuracy difference between the results of the last epoch and the best accuracy of validation set (or carly-stopping: ES) results bocomes smaller when the model is trained on the uniformly generated CLs. That is, the T-informed methods are more prone overfitting when there is bias in the CL generation.
With the experiment results in Section 5.2
conclude that the performance gap between humanly annotated CL and synthetically generated CL is primarily attributed to label noise. Additionally, the biasodness of CLs may potentially contribute to overfitting, while the feature-dependent CLs do not detrimentally affect performance empirically. It worth noting that the last row of Table [ the MAE methods that can learn from noisy CL fails to generalize well in the practical dataset. These results suggest that more research on learning with noisy complementary labels can potentially make CLL more realistic.
5.3 and 5.4
Following above conclusion, the label noise and biasedness of CL emerge the two primary factors contributing to overfitting. To gain better understanding, demonstrated the necessity of employing data augmentation techniques to prevent overfitting and attempted to address the issue of overfitting by employing an interpolated transition matrix for regularization.
conducted deeper investigation into this phenomenon. We
A blation on data augmentation To further investigate the significance of data augmentation, we conducted identical experiments without employing data augmentation during the training phase. As we can observe in the training curves in Figure 5, data augmentation could improve the testing accuracy of all the algorithms considered.

---

Published in Transactions on Machine Learning Research (06/2025)
FWD-UIES)
FRID-UIES)
FIND-R FAND-RIES)
FWU--RIES)
Accuracy
Accuracy
10
10
(25%)
(50%)
(75%)
(100%)
(25%)
(5055)
(75%)
(100%5)
Noise Rate
Noise Rate
(% removed noisy data)
(% removed noisy data)
(a) FWD-(U/R) CLCIFAR10
(b) FWD-(U/R) CLCIFAR20
70
70
SCL-ML
SCL-NI
SCI-NLIES)
SCI-NI(FS)
60
SCL-EXP
60
SCL-EXP
SCI-FXP(FS)
Accuracy
Accuracy
3,93% (0%)
2.94% (25%)
1.86%
0.98% (75%)
0% (100%)
3.93% 00%1
2.94% (25%)
1.98%
0.98% (75%)
0%
(50%)
(50%)
(100%)
Noise Rate
Noise Rate
(% of removed noisy data)
(% of removed noisy data)
(c) SCL((NL/EX)) on CLCIFARIO
(d) SCL((NL/EXP) on CLCIFAR20
Figure 4: Accuracy (WD-(U/R) and SCL-(NL/EXP) on the noise-removed CLCIFARI0 dataset (Left)
and the CLCIFAR20 dataset with uniform noise (Right) at varying noise rates.
Table 3: The overfitting results when there is no data augmentation.
uniform-CIFAN CIFAR10
CLCIFARIO
Snlform-CIFARe
CLCIFAR20
methods
valid
valid (ES)
valid
valid (ES)
valid
valid (ES)
valid
valid ace (ES)
FWD-U
48.44
49.33
21.29
25.59
17.4
17.97
6.91
7.32
FWD-R
14.97
28.3
6.82
14.67
TRE-GA-U
39.55
39.67
21.0
23.53
13.52
14.08
8.35
URE-GA-R
19.81
20.8
6.43
SCL-NL
48.27
21.96
16.55
17.54
7.92
SCL-EXP
46.79
47.52
21.89
27.66
16.18
17.59
7.3
LWW
44.78
10.39
L-UW
46.38
12.33
16.32
PC-sigmoid
18.97
33.26
7.67
10.41
Ablation on interpolation between T₁ and T, Table I we discovered that the T-informed methods did not always deliver better testing accuracy when Te given. Looking at the difference between the accuracy of using early-stopping and not using early-stopping, we observe that when the T, is given to the T-informed methods, the difference becomes smaller. This suggests that T T-informed methods using the empirical transition matrix has greater tendency overfitting. On the other hand, T-informed methods using the uniform transition matrix could be more robust choice.
10

---

Published in Transactions on Machine Learning Research (06/2025)
FWD-U
FWD-R
TRE--A-U
URE-GA-R
0.4
Accurasy
0.44
0.4
Avenreey
0..4
M mm
M Aap
0.3
0.3
0.3
0.3
0.2
0.2
0.2
0.2
0.1
0.1
0.1
0.1
100
200
300
100
200
300
0
100
200
300
100
200
300
Epochs
Spochs
Rpochs
Spochs
SCL-NL
SCL-EXP
L-W
L-UW
0.4
Accurart
0004
0..4
0.3
0.3
0.3
0.3
0.2
0.2
0.2
0.2
0.1
0.1
0.1
0.1
100
200
100
200
300
100
200
300
100
200
300
tsochs
upochs
iopochs
Ipochs
Figure The Overfitting accuracy curve FWD, URE, SCL-NL, L-W. The dotted line represents the accuracy obtained without data augmentation, while the solid line represents the accuracy with data augmentation included for reference. The accuracy of FWD, SCL.NN,, SCI-EXX, I.-W, L-UW methods reaches its highest at approximately the 50 epoches and converges to some lower point. The detail numbers are in Table
We observe that the uniform transition matrix T, acts like regularization choice when the algorithms overfit interpolate between Tu and Ta to let the
CL.CIFAR. This results motívate us to study whether algorithms utilize the information of transition matrix while preventing overfitting. To do so, provide interpolated transition matrix Tim: aT, (1 a)Ta to the algorithm, where a controls the scale of the interpolation. As FWD is the T-informed method with the most sever overfitting when using T, we
performed this experiment using FWD adn reported the results in Figure D As shown in Figure G FWD can learn better from an interpolated Tint, confirming the conjecture that Tu can serve as a regularization role.
a=0%
e=25%
a=50%
CLCIFAR20 Accuracy
a=75%
1=100%
15
14
30
50
55
CLCIFARIO Accuracy
Figure 6: The last epoch accuracy of CLCIFAR10 and CLCIFAR20 for FWD algorithm with a-interpolated transition matrix Tim. The five solid points on each cruve represent different noise cleaning rate: 0%, 25%, 50%, 75%, 100% from left to right.
6 Validation Objectives
Validation is crucial component in applying CLL algorithms in practice. With the collection of the real-world datasets, able to estimate the difference between using ordinary labels for validation (the common practice in existing CLL studies, as what do in Section 5 and using complementary labels for validation.
11

---

Published in Transactions on Machine Learning Research (06/2025)
Validation objectives As discussed in Section 2, validating the model performance solely with complementary labels poses a non-trivial challenge. To the best of our knowledge, only two existing CLL studies offer some possibility to evaluate a classifier with only complementary labels. They are URE (Ishida et al. 2019 and SCEL (Lin & Lin 2023). , We lake these two validation objectives to select the optimal learning rale from {10-3, 10 10 5 10-5, 10 and provides the accuracy on testing set in Table 5 We compare the result to another validation objective that computes the accuracy on an equal number of ordinary labels. Our goal was to determine the gap between using complementary labels and ordinary labels for validation. We selected the best learning rate based on the validation objectives for URE, SCEI., and ordinary-labe accuracy, and then report the test performance, as shown in Table 4 for synthetically labeled datasets and Table for real-world datascts.
Table 4: The testing accuracy of models evaluated with URE and SCEL.
unzfomm CIEAROOO
aallco-UUBAAA
millorm MINIO
URB
SCEL
wilkd
CRE
SCTEL
valil
URE
SCRL
vallć
(2)
URB
SCEL.
vilii
p/p (1)
FWTT-
S3.11
50.M0ss x
61.
10:75
16 73
16.57pmmm
21 511
1.51
53.055774
31.20as
36.30s
2.65
16. 10
9:15gr sx
12.57grm
2.17
FWD-R Rt
62.5002.
41.17_3111
61.32.1.00
8.77
38.25
10.61244
21 21.50L
3.21
32.15.11.9
31,3012:3
35, (5.2011::9
2.00
12.72
11,57.54
14.80.1.70
2.12
URE-GA-U
016821.11
23.20.1.57
00.2421.11
0.5G
35:51:235
16.92155
16 16677128
0.58
25. 35
31.3312:39
35, 25.2112:37
1.35
8.5011.50
6.02.1.3
11,60.100
3.12
URE-GAA-
20.40
50.20 21.00.15
00.72211.5
0.25
15 35
16.122055
5T
1.45
25.55.475
31.10/1.9
33.652 43
-0.45
7.30a9.1
7:1M:2.4
9.7821
2,61
SCL_NL
64.32
SL:0--112
61.70.4.
9.64
16.05:144
16.82.241
21.37a1.1
0.56
22.56.119
31.20.1.
47.06a..3
3.65
11 11.20ua.0
9,38-245
13.00.2.0
1.50
EXP
60.98.000
4L.61-352
61.29.1.22
12,30
16.71112
16.151255
21.871141
4.56
22.56.221
22.701230
36,091:33
3.00
10.53:505
6.88.119
12.80
2.41
L-W
00.36.0.1
G4.32.x..1
3.5G
16.2611.91
14.071154
10 10.881008
0,38
17.70:240
25.0015.35
33,911245
0.30
5,58.122
7.70.a.3
12.70.2.00
4.12
LUW
52.47esu
67.52
5.06
16 10
15.58e100
20 20.7aas00
4.62
22.10e::
25. 23.00am:s
35. 10a27a
9.90
10.00
6.38-248
12.12asus
1.52
PC-sigeed
55.20
34.50-1.25
87.78
2:60
18
18-004612
16 14.48a4.0
1,77
25.56
27.0645.0
28.10 28.10-284
2.05
7.78
6.72
10.72
2,00
ROB-MA
67.50
07.79-220
08.38
1.30
17.07
15.02:359
18.174128
1.31
90.164522
27.101200
31.00..31
1.35
5.42
8.00
6,50
0.92
Table 5: The testing accuracy of models evaluated with URE and SCEL.
CLCIFARIO
CICIFAROO
CLMINIO
CLMIN20
URE
SUEL
valid 6oe
Sap (1)
URE
SCEL
villd 002
URE
SCEL
vold occ
RAD (4)
URE
SCEL
valid ace
RND (1)
PWISU
35 13
31 1..56a1
31 33ence
1.70
6.700:1
01.43
30 19
23 20
3.10
1.97pmm
4.55ggm
6:30g1
1.35
FWD-R
38 38.701524
05.5411337
38 13.133
2.40
17.35.2.10
15. 15.001:.55
20127.0.3
1.95
22.55.415
20.151163
20 20.10.1.40
1.00
5.62.1.8
9.50..15
10,011142
0.70
GUU--GA-
30 4513.04
21.2111:33
34 34.7210.0
1.51
7.0012.11
S71.6.4
10.49.032
1.79
17.00..335
21.3013:0
22 22.30:297
1.00
4:272000
5.03.0..
0.72
URE- GA--
27 27.35
28.52
30.234mc
1.9L
3.58v1
6.42-com
6.17e122
0.75
8:50a1.3
10.30+113
18.25+a.1
2.05
5.15mmm
6.57-1.3
0.90
0.58
SCL
38.654405
83.70a1
34.774u0
1.00
6,78east
7.47
8.62.13
0.55
19.56-1.37
22.1541.74
21.504145
-0.35
4.851112
6.20aa.5
6.17a04
0.98
SCI
31.47a1
35 18
1.71
7:70gm
0.95
18.3e
20:
24 21.80tx
6:15
5.05nae
4.45mm2
5.58
0.52
L-W
27 40..3
90.52e3
32 32.99em0
2.67
5.50e111
2.18
7.31
0.53
19.30ca
18.05
23 Sttrrm
1.50
5.97
5.55
6.80mmmm
0.15
L-WWW
29.7812
34 31.600008
4.91
6,01:342
8:16..00
8.10:330
-1001
18.25.2.11
19.901344
22.401144
6.48.1.3
6335.00
PCCllggood
31.48a1
32 15:10a
7.98:247
10.50
12:11:0.0
1.51
12.50.1.31
17.652443
6.40e119
5.38:1.36
6.002..4
0.50
ROB-MAE
18.804104
18.75.0
20.234100
4.70a244
487.6008
11,80.2.2
14.851128
14.15anss
462...90
6.88.608
Results and discussion Firstly, there appears no clear winner between URE and SCEL, both using only CLs for validation. Validating with the ordinary-label accuracy generally provides stronger performance than URE/SCEL, and the test performance gap between validating with ordinary labels and validating with complementary labels can be as big nearly 5%. These findings suggest that using purely complementary labels for validation, whether through URE or SCEL, still suffers from a non-negligible performance drop compared to using ordinary validation. That is, the nunbers reported in existing studies, which validates with ordinal labels, can be optimistic for practice. Whether this gap can be further reduced remains an open research problem and the community can pay more attention on that to make CLL more practical.
7 Alternative to Current Data Collection Protocol
In this work, we used specific protocol to collect complementary labels, but we acknowledge there are several alternative protocols that could also be considered. Here we highlight possibilities while explaining the rationale behind our current design choices.
The first alternative would be to provide annotators with more than four classes. However, realistically, increasing the number beyond four would significantly increase the effort required from annotators. We chose four because it is a common standard for multiple-choice scenarios and was effectively employed in prior research (Wei et al.] 2022) that used human annotations to collect noisy labels in real-world settings. Nevertheless, we admit exploring different numbers of labels beyond four presents an interesting area for future research in complemenaary dataset.
12

---

Published in Transactions on Machine Learning Research (02))
wi-butterlyy.
sue
01:1
0:2
6:32
0:13
6.50
Bscepack
313
800
507
003
033
0.0
0.2
0.3
6:39
0.77
645
1400
cardigan
91
811
800
031
000
615
604
6:14
Collected
Ordinary Labels
kimono
313
512
304
660
032
647
6:4
6:27
C.99
2200
6:29
m-compass
514
SAC
601
6000
2000
000e
SRW
013
sandal
032
0:0
689
623
800
farch
400
adsbbuterfyy
tacrgeec
cardigann
Himona
n-coppass
forch
Bazz
pizza
tarch
autbutterrl
Jandel
berkpacck
you pocouppans
Almono
dboat
aip
cartigan
Complementary Labels
lementary
Transition matrix
(b) Label distribution
Figure 7: The transition matrix (a) and label distribution (b) of CLMicrolmageNet10 with the true labels hidden.
A second alternative, we considered was using a simple "yes/no" format. However, this approach posed two main issues. First, it would generate a dataset containing both true and complementary labels, which conflicts with our goal of creating a purcly complementary datasct. Second, the resulting datasct would likely contain increased noise, complicating clear analysis and validation of the label transition assumptions.
Another possible protocol involves explicitly hiding the true label during annotation minimize noise. However, this approach is less realistic since, in real-world scenarios, true labels are typically unknown (otherwise complementary annolation will not be necessary). Note that part of our current dalaset, which does not have choices that include the true label, can be taken to analyze the effect of such a protocol. We show in Figure that such a protocol does not lead to much change of the transition matrix (except for the diagonal noise removal) and label distribution, when compared with our original choice of protocol.
We view our work as an initial exploration into collecting complementary labels, and we hope that this work will inspire the future work on other possible collection protocols of complementary label.
8 Conclusion
In this paper, we devised protocol to collect complementary labels from human annotators. Utilizing this protocol, we curated four real-world datasets, CI.IIFAR10, CL.IIFAR0, CIMierolmaageeet10 and CLMicrolmageNet200 and made them publicly available to the research community. Through our meticulous analysis of these datasets, we confirmed the presence of noise and bias in the human-annotated complementary labels, challenging some the underlying assumptions of existing CLL algorithms. Extensive benchmarking experiments revealed that noise is a critical factor that undermines the effectiveness of most existing CLL algorithms. Furthermore, the biased complemenarry labels can trigger overfitting, even for algorithms explicitly designed to leverage this bias information. In addition, CLL suggests that validating with only complementary labels causes significant performance degrading. These findings emphasize the need for the community to dedicate more effort on those issucs. The curated datascts pave the way for the community to creale more practical and applicable CLL solutions.
study the validation objective for
9 Limitations
To ensure the compatibility with previous CLL algorithms, our work focuses on image datasets based on CIFAR10/100, and TinyImageNer. It is worth investigating the real-world CLL datasets on larger datasets, such as ImageNet, and other domains. On the other hand, the proposed protocol focuses on collecting real-world complementary labels for analyzing the common assumptions CLL. That said, it is also crucial to understand efficient ways to collect complementary labels in practice, e.g., by asking annotators binary
13

---

Published in Transactions on Machine Learning Research (06/2025)
questions to collect ordinary and complementary labels simultaneously. We leave these directions as future works and hope that our work can open the way for the community to understand these questions.
Broader Impact Statement
It is known that weakly-supervised learning can be used for some privacy-preserving applications. While our CLImage datasets do not fall under such privacy-preseree applications, we suggest that practitioners exercise caution when exploring these use cases.
Acknowledgement
We thank the anonymous reviewers and members of CLLab for their constructive feedback. This work is supported by the National Science and Technology Council in Taiwan via NSTC 1.3-2628--E0002-03 NSTC 113-234---0002-088 and NSTC puting (NCHC) of National Applied Research Laboratories (NARLabs) in Taiwan for providing computational and storage resources.
We thank to National Center for Hfgh-pprrfommnce Com-
References
Yu-Ting Chou, Gang Niu, 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, pp. 1929-1938, 2020.
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 2011.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation strategies from data. In IEEE Conference on Computer Vision and Pallern Recognition, pp. 113-123, 2019.
François Denis. PAC learning from positive statistical queries. In Algorithmii Learning Theory: 9th International Conference, pp. 112 126, 1998.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple complementary labels. In International Conference on Machine Learning, pp. 3072 3081, 2020.
Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: a survey. IEEE Transactions on Neurul Networks and Learning Systems, 25:845 869, 2014.
Yi Gao and Min-Ling Zhang. Discriminative complementary-labor learning with weighted loss. In International Conference Machine Learning, pp. 3587-3597, 2021.
Timmit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumé III, and Kate Crawford. Datasheets for datasets, 2021. URL htttps://arxiv.orrtt org/ abt///asb////////////// 0008800.000000
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, pp. 770 778, 2016.
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. Advances Newral Information Processing Systems, pp. 5639 5649, 2017.
Takashi Ishida, Gang Niu, Aditya Menon, and Masashi Sugiyama. Complementary-labe learning for arbitrary losses and models. In International Conference Machine Learning, pp. 2971-20 19--0, 2019.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Hiroki Ishiguro, Takashi Ishida, and Masashi Sugiyama. Learning from noisy complementary labels with robust loss functions. IEICE Transactions on Information and Systems, 105:364-370) 2022.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In European Conference Computer Vision, pp. 491-507, 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Computer Science University of Toronto, Canada, 2009.
Ya Le and Xuan Yang. Tiny imagenct visual recognition challenge. Report CS231N: Deep Learning for Computer Vision Course, 2015. Standford University.
Wei-I Lin and Hsuan-Tien Lin. Reduction from complementary-label learning to probability estimates. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 169-481, 2023.
Shuqi Liu, Yuzhou Cao, Qiaozhen Zhang, Lei Feng, and Bo An. Consistent complementary-labed learning via order-preserving losses. In International Conference Artificial Intelligence and Statistics, pp. 8734 8748, 2023.
Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy V. Vo, Marc Szafranice, Vasil Khalidov, Picrre Fernandez, Daniel HAZIZA, Francisco Massa, Alaaeldin El-Nouby, Mido Assran, Nicolas Ballas, Wojeiech Galuba, Russell Howes, Po-Yo Yao Huang, Shang- Wen Li, Ishan Misra, Michael Rabbat, Vasu Sharma, Gabriel Synnaeve, Hu Xu, Herve Jegou, Julien Mairal, Patrick Labatut, Armand Joulin, and Piotr Bojanowski. DINOv2: Learning robust visual features without supervision. Thansactions on Machine Learning Research, 2024. ISSN 2835-8856.
Giorgio Patrini, Alessandro Rozza, Aditya Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: loss correction approach. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 1944-1952, 2017.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Audrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. Imagenct large scale visual recognition challenge. International Journal of Computer Vision, 115:211- 1-222,, 2015.
Masashi Sugiyama, Han Bao, Takashi Ishida, Nan Lu, Tomoya Sakai, and Gang Niu. Machine learning from weak supervision: An empirical risk méndmization approach. MIT Press, 2022.
Deng-Bao Wang, Lei Feng, and Min-Ling Zhang. Learning from complementary labels via partial-output consistency regularization. In International Joint Conference on Artificial Intelligence, pp. 3075-3081 2021.
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. In International Conference on Learning Representations, 2022.
Yanwu Xu, Mingming Gong, Junxiang Chen, Tongliang Liu, Kun Zhang, and Kayhan Batmanghelich. Generative-diseriminati complementary learning. In A AATT Conference on Artificial Intelligence, pp. 6526 6533, 2020.
Nai-Xuan Ye, Tan-Ha Mai, Hsiu-Hsuan Wang, Wei-l Lin, and Hsuan-Tien Lin. libell: an extendable python toolkit for complementary--abel learning. arXiv preprint 1rXto:2411.12276 2024.
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In European Conference on Computer Vision, pp. 68-83, 2018.
Zhi- thi-Hua//e Zhou. A brief introduction to weakly supervised learning. National Science Review, 5:44-53, 2018.
15

---

Published in Transactions on Machine Learning Research (06/2025)
Appendix
A More discussion on practical noise and extended ablation study
Our work found out that the labeling noise the main factor contributing to the performance gap between synthetic CL and practical CL. Hence, we conducted doeper investigation into some directions to handle the practical noise. In Section A.1 we discussed the performance improvement when more numaan-annotaie complementary labels were available. In Section A.2 we designed the synthetic CLCCIFARNN dataset to study the difference between syuthetic uniform noise and practical noise. In Section A.3 we provided the benchmark results of all robust loss methods to emphasize the essence of studying a practical complementary label dataset. In Section|
A.4 we discussed result analysis of CLCIFAR20 and CT.Micro described the process how MicrolmageNet10 and MicrolmageNet20 datasets were generated in Section A.5 In Section A.6 we provided an ablation study on different. net work architectures commonly used in complementary label learning.
datasets and
A.1 Multiple complementary labels
In this experiment, we studied the case when there were multiple CLs for a data instance. We duplicated the data instance and assigned them with another practical label from the annotators. The results of this experiment were sunmarized in Table 6
For CLCIFARIO, we observe that the model achieved better learning performance when trained on data instances with more CLs. However, the issue of overfitting persists even with the increased number of labels. In the case of CLCIFAR20, we found that without employing early stopping techniques, it is challenging to achieve improved results as the number of labels increased. Furthermore, the overfitting problem becomes more pronounced with the increased nunber of labels. Overall, these findings shed light on the challenges posed by multiple CLs and the persistence of overfitting.
A.2 Benchmarks with synthetic noise
we investigated another avenue of research: the generalization capabilities of methods when transitioning from synthetically labeled datasets with uniform noise practical datasets. To obtain a general synthetic dataset with minimum assumption, introduced CLCIFAR-N. This synthetic dataset contains unifrom CL and uniform real world noise from CLCIIARR dataset. The complementary labels of CT.CIFAR-N are i.i.d. sampled from Teym where the diagonal entries are set to be 3.93% 11 (for generating CL for CIFAR10) or 2.8%/20 (for generating CL for C2F) The non-diagonal entries are uniformly distributed. This construction allows us to generate a synthetic dataset that mimics real-world scenarios more closely with minimum knowledge.
Generation process of CLCIFAR-N
Inspired by the conclusions drawn in Section 5.3
Benchmark results We ran the benchmark experiments with the identical settings as in Section 5.1 and present the results in Table 7 The performance difference between sythotic noise and practical noise are illustrated in the diff columns. A smaller difference indicates better generalization capability of the models. Interestingly, the robust loss methods exhibit superiority the synthetic CLCIFARIO-N dataset but struggle to generalize well on real-world datasets. This finding suggests the existence of fundamental differences between synthetic noise and practical noise, Further investigation into these differences is left as an avenue for future research.
A.3 Results of the robust loss methods
The original design of the robust loss aims to obtain the optimal risk minimizer even the presence of corrupted labels. However, their methods do not generalized well on practical datasets. The results are provided in Table In other words, solely considering synthetic noisy CLs does not guarantee performance real-worle datasets. These results once again underscore the importance of the CLCIFAR dataset.
16

---

Published in Transactions on Machine Learning Research (06/2025)
Table 6: Learning with Multiple CL: The figure shows the classification accuracy of each task with carly stopping indicated in brackets. The highest accuracy in each column is bolded for ease of comparison.
CLCIFARIO
CLCIFAR20
num CL
3
FWD-U
34.09(36.88)
41 (3)
42.88(45. 18)
(.47())27)
8.28(8.78)
8. 8,15(10)27)
FWD-R
28. (8.88(38.9)
37.03:47.07)
37.84:49.76)
16.14(20.31)
16.99(23.41)
15.54/24.19)
TRE-GA-U
(3659))
45.71 (44.85)
(47.7(47.97)
7.59(10.06)
8.42(11.52)
8.53(12.76)
URE-GA-R
28.7(30.84)
42.73(43.34)
44.73(47.36)
5.24(5.46)
6.77(6.92)
5.0(6.55)
SCL-NL
33.8(37.81)
(1.67(12.58)
43.39(45.2)
7.58(8.53)
6.77(6.92)
5.0(5.55)
SCL-EXP
34.59(36.96)
40.89(12.90)
44.4(47.9)
7.55(8.11)
7.42(8.39)
8.0(9:31)
L-W
28,04(34.55)
34..6641.83)
39.05(47.46)
7.08(8.74)
8,06(8.78)
8, 8,03(10.18)
L-UW
30.63(35.13)
38. (3).5)
(9..99)5
7.36(..71)
7.03(8.55)
7.86(10.11)
PC-sigmoid
21.38(35.88)
25.63(39.82)
33.89(43.75)
9.27(14.26)
11.91(16.07)
17.68
Table 7: Benchmark results on CLCIFAR-N datasets. The classification accuracy difference calculated by subtracting the practical CLCIFAR datasct from the performance on the synthetic CLCIFAR-N datasct.
CLCIFARIO-N diff(.)
CLCIFAR2O-N
diff(J)
FWD-U
37.1
7.58
0.11
FWD-R
URE-GA-U
URE-GA-R
SCL-NL
37.79
2.06
7.75
0.16
SCL-EXP
35.86
3.19
-0.59
LWW
30.1
2.06
6.16
-0.91
L-UW
32.69
2.05
6.80
-0.47
PC-sigmoid
19.64
-4.73
6.54
-2.72
CCE
32.34
13.45
5.71
0.71
MAE
41.34
23.09
6.83
1.83
WMAE
37.62
22.26
6.36
1.08
GCE
35.00
18.71
1.7
12.29
1.05
A.4 Result analysis of CLCIFAR20 and MicrolmageNet20
In this section, we further investigate the complementary labels collected from the CLCIFAR20 and Microlm- ageNet20 datasets. We followed similar observation and analyzed in the Section Our observation and analysis are described as below:
Observation 1: noise rate compared to ordinary label collection We observed that the noise rates for the complementary labels collected from the CLCIFAR20 and MierolmageNet20 datasets are 2.80% and 3.21%, respectively. This finding is consistent with the observations discussed in Section 4 The lower noise rate in the CLCIFAR20 dataset compared to MicrolmageNet20 can be attributed to the greater difficulty in labeling the MicrolnageNel20 dataset.
Observation 2: imbalanced complementary label annotation Next, we analyzed the distribution the collected complementary labols. The frequencics of these labels for the CLCIFAR20 and CLMicrolmageNet220 (CLMIN20) datasets are shown in Figure 8 The figure reveals that annotators exhibit specific biases towards certain labels. For example, in CLCIFAR20, annotators show a preference for labels such as "fish", "flowers", "people", "trees", "food container", and "transportation vehicles". In CLMIN20 [ they favor "iPod" and "tractor". In CLCIFAR20, the bias tends towards labels with shorter, more concrete, and understandable names. Conversely, in CLMIN20, the preference is for easily recognizable items as "iPod", and "tractor", while less familiar items such as "bannister", "american lobste", "snorkel", and "gazelle" are less favored.
Observation biased transition matrix Finally, we visualized the empirical transition matrix using the collected complementary labels, as shown Figure g Our observations indicate that the transition matrix
TThe mapping between class numbers and labels for CLCIFARIO and CLMIN20 provided in Appendix
17

---

Published in Transactions on Machine Learning Research (06/2025)
Table 8: Standard benchmark results on CLCIFAR and miform-CIFAR datasots for the robust loss method. Mean accuracy (= standard deviation) on the testing dataset. from four trials with different random seeds. Highest accuracy in each column is highlighted in bold.
CIFFAROO
CLCIFAR10
uniform- CIFAR20
CLCIFAR20
methods
valid
valid are (ES)
valid
valid_ acc (FS)
valid
valid _are__aae___ (ES)
valid are
valid_ arc (ES)
CCE
46.5721.75
49.51
16.1842.97
20.18:3.39
12.54=0.40
1:20
5.0710005
5.41=0.30
MAE
67:3710048
98..0.9997
16.30.2.27
19.44.1441
16.72-155
1.663
5.1110.11
5.87_0.26
WMAE
13.0111.89
15.5110.75
5.3110027
6.65_.065
GCE
1.51
59.4442.30
14.31#1.44
18.97:2.16
15.86=1-98
17.09+1.18
5.21+:0.29
5.76=0.32
SL
42.6440.11
16.45:2..0
19.28:3.16
13.60=0.55
15.70=1.23
5.441:0.9
6.59=0-48
is biased. Specifically, we discovered that the bias in the complementary labels dependent on the true labels, depicted in Figure g In CLCIFAR20, there more annotations for labels with shorter, more concrete, and understandable names, such as "fish", "flowers", "people", and "transportation vehicles". This results in a distribution that is more biased towards these labels. A similar pattern of bias is observed in CLMIN20, where annotators lavored easily recognizable items like "iPod" and "tractor", while less familiar items received fewer annotations.
10000
2000
9000
Number of CL Collected
1800
8000
1600
of
7000
1400
6000
1200
5000
1000
800
4000
18
17
10
12
28
10
11
16
Complementary Labels
Complementary Labels
(a) CLCIFAR20
(b) CLMierolmageNet220
Figure 8: The label distribution of CLCIFAR20 and CIMMccolmageeee120 datasets. The full label names are
provided in Appendix
A.5 MicrolmageNet dataset generation
To generate the MicrolmageNet10 and MicrolmageNe120 datasets, began by randomly selecting 10 classes from the 200 available in MicrolmageNet to create MicrolmageNNt100. Similarly, randomly selected 20 classes to form MicrolmageNet200. The selected classes are listed in Table II of Appendix E Each class in the Tin22mageNet200 dataset contains multiple labels. To ensure reproducibility and facilitate human annotation, we chose the first. label to represent the primary label of each class, as detailed in Appendix E Each class in the MicrolmageNet10/ 10/20 datasets comprises 500 images for the training set and 50 images for the validation set. To collect complementary labels for the MicrolmageNet10// datasets, we followed a protocol similar the one described in Section 3.2
A.6 Result analysis of different neural network architectures
We chose begin benchmarking with simpler models due to the known issue of overfitting in CLL. CChou et al. 2020). Simpler models are typically less prone to overfitting, making them suitable for initial benchmarking We conducted ablation study comparing different neural network architectures, including 18sNet18, ResNet34, ResNet50, and DenseNet121, to determine the most suitable architecture for our complementary
18

---

Published in Transactions on Machine Learning Research (06/2025)
SU0
GAA
C40 921
Oralinrry Labels
006
-0000
883
10
10
12
73
25-
16 -0:0
18
5
7
9
31
12
14
15
16
37
38
19
Complementary Labels
Complementary Labels
(a) CT.CIFAR20
(b) Ne0i
Figure 9: The empirical transition matrices of CLCIIFA200 and CLMicrolmageNe120. The label names of CLCIFAR20 and (0MierolmageNet20 are abbreviated as indexes to save space. The full label names are provided in Appendix
dataset. Results shown in Table g indicate that ResNet18 achieved the best performance. Additionally, ResNet18 closely aligns with ResNet architectures commonly used in CLL studies (ee et al. 2024 Xu et al. 2020 Thus, we selected ResNet18 for benchmarking purposes.
Table 9: Performance of various neural network architectures using SCL-NL and FWD-R algorithms on our real-worle complementary datasets. The highest accuracy in each column is highlighted in bold.
OICIAARI
CEMINIO
CTAINNS)
HncNet18
Drzedvitz2
Bondetts
BowNwe31
Redeett0
DeterNitt21
MteNents
Resheeti
DeseeNet221
BressNetizi
FWD-R
14.36
16:00
0.00
B An overview of the complementary-lbel learning algorithms
In this section, we review the algorithms benchmarked in Section
B.1 T-informed CLL algorithms
Some of them take the transition matrix T as inputs, which we call T-informed methods, including
Two versions of forward correction method Yu et al. 2018 FWD-U and FWD-R. They utilize a uniform transition matrix T2 and an empirical transition matrix T. as input, respectively.
Two versions of unbiased risk estimator with gradient ascent IIhida et al. 2019 URE GA-U with uniform transition matrix T, and URE-GA-R with an empirical transition matrix Te.
Robust loss methods (Ishiguro et al. 2022 for learning from noisy CL, including CCE, MAE, WMAE, GCE, and SI We applied the gradient ascent technique (Ishida al.) 2019) recom- mended in the original paper.
Due to space limitations, only provided the results of MAE, The remaining results and discussions related to the robust loss methods can be found Appendix A.3
19

---

Published in Transactions on Machine Learning Research (06/2025)
In practice, the empirical transition matrix T. is not accessible to the learning algorithm, but we assume that the correct Tg is given to FWD-R, URE-GA-R and the robust loss methods for simplicity.
T-informed CLL algorithms are those that has the transition matrix as inputs, includes but not limited Forward loss correction (FWD) and Unbiased risk estimate (URE). They are expected utilize the information of the transition matrix provide better performance when the complementary labels are not generated uniformly. The transition matrix, however, may not be accessible in practice. In this case, uniform Iransition matrix T. is lypically provided to the algorithis default choice. In the benchmark in Section 5 we considered both scenarios in which the empirical transition matrix Te or the uniform transition matrix Tu was provided.
FWD Forward loss correction utilizes the information of a transition matrix in its loss function as Eq. Yu ct al. 2018). Esscntially, this method trains model f by minimizing the following loss function.
N R(g) = N
Σ e(T softmax(g(z;)), 9:)
(3)
where is the transition matrix provided to the method. We use FWD-U and FWD-R to indicate the cases that T equals T, and Te, respectively.
URE-GA [Ishida al. 2017 proposed an unbiasod risk estimator (URE) for Icarning from complementary label. The loss of the URE is defined follows,
R(g)
c (T (((g())))
(4)
URE, however, can go below zero during the optimization procedure, leading to overfitting of the model. To address this issue, (Ishida et al. 2019) proposed two tricks, non-negative risk estimator (NN) and gradient aCA)nt(GA). The former zeros out the gradient when the mini-batch loss goes below zero while the latter
reverse the mini-batch gradient when the loss from any of the complementary class goes below zero. We replace the transition matrix in the risk estimator with T, and T. for URE-GA-U and URE-GA-R.
B.2 T-agnostic CLL algorithms
T-agnostic CLL algorithms are those that do not take the information of the transition matrix, includes but not limited to Surrogate complementary loss (SCL) and Discriminative modeling (I-W/I-UW).
SCL (Chou et al. 2020 proposed to use the surrogate complementary loss (SCL) to address the overfitting tendency in URE. The loss function defined as follows,
R(g) = N Σ g(r:))
(5)
where (6.)) is a surrogate loss for 0 0-1 1 loss. For instance, SCL-NL uses the negative log loss ø(g, g(x))
=
- llog(1 - Ppy) and SCL-EXP uses the exponential loss ((ū, (()) exp(py).
I- (Gao & Zhang 2021 proposod use discriminative modeling to directly model the distribu- tion of complementary labels. To do so, they proposed the following loss functions,
1 N
R(g)
Σ
log(soflmaxx1 soflmax(((=))))
(6)
They also proposed weighting function to further improve the performance. The unweighted version is denoted L-UW and the weighted version is denoted as L-W.
20

---

Published in Transactions on Machine Learning Research (06/2025)
B.3 Robust loss methods
[[shiguro et al. 2022) studied two conditions on loss functions: weighted symmetric condition and relaxation of weighted symmetric condition. Five loss functions that can be robust against the estimation error of the transition matrix were proposed. Their results can be further generalized to noisy complementary label learning. More experiment details for reproduction can be found in their paper.
C Additional charts for CLCIFAR dataset with data cleaning
We remove 0%,, 25%, 50%, 75%, 100% of the noisy data in CLCIFAR10 and CLCIFAR20 datasets. We discover that by removing the noisy data in the practical dataset, the practical performance gaps vanish for all the CLL algorithms. Therefore, can conclude that the main obstacle to the practicality of CLL is label noise.
70
URE-GA-U
URE-GA-U
URE-GA-UIES)
URE-GA-VIES)
60
URE-GA-R
60-
URE-GA-R
R(CS)
Accuracy
Accuracy
30
30-
20
20
3.93% (0%)
2.94%
1.96% (50%)
0.96%
3.93%
2.94%
1.96% (50%)
0.90% (75%)
0%
(75%)
(200%)
(25%)
(100%)
Noise Rate
Noise Rate
(% of removed noisy data)
(% of removed noisy data)
(a) URE-GA-(U/R) on CLCIFAR10
(b) URE-GA-(U/R) on CLCIFAR20
70
L-WIES)
L-WESI
60
L-UW
60
L-UW
LUW!ES)
50
Accuracy
Accuracy
90
30
20
20
3.93% (0%)
2.94%
1.96%
0.96%
3.93%
2.94%
1.96% (50%)
0.90%
0%
(50%)
(75%)
(100%)
(25%)
(75%)
(100%)
Noise Rate
Noise Rate
(% of removed noisy data)
(% of removed noisy data)
(a) T-(W/UW) on CLCIFAR10
(b) T-(WUUW) on CLCIFAR220
21

---

Published in Transactions on Machine Learning Research (06/2025)
70
si-igmdid sigimoii
PC-igmeii
PC-sigmoietCS)
60
Accuracy
Accuracy
40-
40
20
20
0.05
0.0375
0.025 (50%)
0.0125
0.05 (0%)
0.0375 (25%)
0.025 (50%)
0.0125
(0%)
(25%)
(75%)
(100%)
(75%)
(100%)
Noise Rate
Noise Rate
(% of removed noisy data)
(% of removed noisy data)
(a) PC-sigmoid on CLCIFARI0
(b) PC-sigmoid on CLCIFAR2.
D Analysis between multiple label collection trials
We carried out the same protocol for three independent trials to ensure the consistency of our results. The noise rates of CLCIFARIO are 0.0398, 0.03882, and 0.03928 for three trials respectively. On the other hand, the noise rales of CLCIFAR20 are 0.02322, 0.02902, and 0.03196. These results show that the obtained noise rates are reliable and consistent. Besides, we also analyzed the distribution of complementary label within three trials reported in Figure 13 The consistent distribution of complementary labols reveals the empirical human annolating biasedness within our protocol. Both analyses show that our protocol and discovery are solid and stable.
3000
CL Caleeded
4000
2260
8000
2000
2000
Labele
Compkmentary Labels
(a) CLCIFAR10
(b) CLCIFAR20
Figure 13: The complementary label distribution of three independent trials of CLCIFAR10 dataset (Left)
and CLCIFAR20 dataset. (Right). The full label names of CLCIFAR20 provided in Appendix E
22

---

Published in Transactions on Machine Learning Research (06/2025)
E
Label names of CLCIFAR20 and CLMicrolmageNet20
Table 10:
The correspondence between index and label names of CLCIFAR20 and CLMicrolmageNet200
datasets.
Index
CLCIFAR20 Label Name
CIMicrolnageNe1200 Label Name
0
aquatic mammals fish
tailed frog scorpion
1
2
flowers food containers
snail
3
american lobster tabby
4
fruit, vegetables and mushrooms
5
household electrical devices
persian cat gazelle chimpanzee
6
household furniture insects
7
large carnivores and bear 8
bannister
9
large man-made outdoor things large natural outdoor scenes large omnivores and herbivores
barrel
10
christmas stocking
11
gasmask
12
medium-sized mammals
hourglass
13
non-insect invertebrates
iPod
14
people
scoreboard
15
reptiles
snorkel
16
small mammals trees
suspension bridge
17
torch
18
transportation vehicles
Tractor
19
non-transportation vehicles
triumphal arch
Table 11: The selected classes/ Tolderss for MicrolmageNet110 (MIN10) and MicrolmageNNe120 (MIN20) are drawn from the TinylmageNet2000 dataset. The labels provided in the table represent the first ordinary label for these classes.
Index MINIO Folder
MINIO Label Name
Index
MIN20 Folder
MIN20 Label Name
102281406
mulphur-butterff
0
n01644900
tailed frog scorpion snail american lobster
n02769748
backpack
1
n01770393
2
n02963159
cardigan
2
n01944390
n0361748 7480
kimono
3
n01983481
4
n03706229
magnetic-compass
4
n02123045
tabby
5
n03838899
oboe
n02123394 5
persian cat
n04133789
scandal
n02423022 6
gazelle
7
n044561 15
torch
7
n02481823
chimpanzee
8
n07873807
pizza
8
n02788 148
bannister
199193705
alp
9
n02795 169
barrel
10
n03026506
christmas stocking
11
n03424325
gasmask
12
n03544143
hourglass
13
n03584254
iPod
14
n04149813
scoreboard
15
n04251 144
snorkel
16
n04366367
suspension bridge
17
n04456115
torch
18
n04465501
tractor
19
n04486054
triumphal arch
23

---

Published in Transactions on Machine Learning Research (06/2025)
F
AutoAugment
In addition the standard data augmentation, RandomCrop and RandomHHorizontllFiin, also considered more advanced one, AutoAugment (Cubuk et al.) 2019). The benchmark results using AutoAugment are provided in Table 12 We observe that AutoAugment can improve the performance in almost all of the secenarios with a cost of around double running time compared to standard data augmentation. Also, the overfitting tendency of the provious algorithms remains unsolved although we observe that carly-stopping can still deliver better performance when using AutoAugment.
Table 12: Comparison of performance using Autment on CLCIFAR and unifrr--CIFAR datasets in relation to tabxexp-1. The accuracy changes are shown in subscript, with enhanced accuracy values being highlighted in bold.
CLCIFARIO
CLCIFAR20
methods
valid_ace
valid (ES)
valid_ace
valid
(ES)
valid
valid_ (ES)
valid
valid (ES)
FWD-U
75.72+6.53
77.02:7.23
12.46
13.52
26.8
26.93+6.31
7.38
8.76+0.49
FWD-R
75.53+5.79 5.79
66.06
10.37
43.1
26.74:6.74
26.98
20.71 4.57
24.77
URE-GA-U
80.24-5.02
59.9+-4.9
37.78 3.19
38.4842.09
1..0
18.59+2.0
8.88 +.88
9.7-0.36
URE-GA-R
58.36-5.06
59.4 49.442+2.0
31.98-
33.08+2.14
18.2-3.54
19.72+2.59
10.85-5.01
9.89+44.48
SCL-NL
76.83
43.22
26,62
8.31-0.11
SCL-EXP
75.9-11.04
75.75+10.95
40.95
41.63+44.7
24.96+5.56
26.64+5.01
7.21-0.8
8.47+0.36
LWW
67.2-10.99
71.07+11889
33.89-5.85
38.1643.61
22.28+7.98
23.19+-4.08
7.58+0.5
8.64-0.1
L-UW
12.39-11.81
13.26-10088
34.61-5.00
40.3+8.17
23.31+7.3
24.41+4.99
7.47-+0.11
8.96+0.25
PC-sigmoid
45.72-17.62
46.53+7.24
33.24-8.86
40.72+4.84
12.81+3.00
13.84-2611
14.15-4.88
17.06+28
MAE
61.26+3.e9
21.71
21.79:4.16
5.18+00.0
6.68
G Datasheets for Datasets
We refer to the template and guiding questions provided in 'Datasheets for Datasets' by (Gebru et al. 2021
G.1 Motivation
For what purpose was the dataset created? Was there a specific task in mind? Was there a specifie gop that needed to be filled? Please provide a description.
The dataset was created to enable research on complementary label learning gain insights into the real- world performance of CLL algorithms, developed protocol to collect complementary labels from human annotators.
Who created the dataset (e.g., which team, research group) and on behalf of which entity (e.g., company, institution, organization)?
The datasets were created by: Computational Learning Lab, Dept. Computer Science and Information Engineering, National Taiwan University.
Who funded the creation of the dataset? If there is associated grant, please provide the name of the gruntor und the grunt name and number.
Funding was provided from those distinct sources: the National Science and Technology Council in Taiwan NSTC 113-2634-F-002-008, NSTC
via NSTC for High-performand Computing (NCHC) of National Applied Research Laboratories (NARLabs) in Taiwan for providing computational and storage resources.
and National Conter
Any other comments?
None.
24

---

Published in Transactions on Machine Learning Research (06/2025)
G.2 Composition
What do the instances that comprise the datasct represent (e.g., documents, photos, people, countries)? Are lhere mulliple types of instances (e.g., movies, users, and ralings; people and interactions between them; nodes and edges)? Please provide a description.
The instances are the images which are derived the published datasets including CIFAR1O, CIFAR100, TinylmageNet.
How many instances are there in total (of each type, if appropriate)?
The CLCIFAR10 and CLCIFAR20 datasets each contain 50,000 training instances and 10,000 testing instances. For the CIMierolmageNet datasets, ma has 5,000 training instances and 500 tosting instances, whereas CLMicrolmageNot220 includes 10,000 training instances and 1,000 testing instances.
Does the dataset contain all possible instances or is it a sample (not necessarily random) of instances from larger set? If the dataset is a sample, then what is the larger set? Is the sample representative of the larger set (e.g., geographic coverage)? so, please describe how this representativeness was mulidaled/veriipe more diverse range of instances, because instances were withheld or unavailable).
IJ il is not represenlative of the larger sel, please describe why not (e.g., lo cover
For details regarding the CLCIFAR10 and CLCIFAR20 datasets, please refer to Section 3.1 The CLMicrolm- ageNet10 and CI.VicrolmageNe121 datasets are described in Appendix A.5
What data does each instance consist of? "Raw" data (e.g., unprocessed text or images)or features? In either case, please provide description.
Each instance consists of an image associated with three complementary labels. The images in the CLCI- FARI0 and CLCIFAR20 datasets have dimensions of 32x32 pixels, while those in CLMicrolmageNee10 and CLMicrolmageNet200 have dimensions 64x64 pixels.
Is there label or target associated with each instance? If so, please provide a description.
The label is the negative labels of picture, called complementary label. The complementary label derived from other labels, which an instance does not belong.
Is any information missing from individual instances? If so, please provide description, explaining why this information is missing (e.g., because il was unavoilable). This does not include intentionally removed information, but might include, e.g., redacted text.
Everything included. No data is missing.
Are relationships between individual instances made explicit (e.g.,users' movie ratings, social network links)? If so, please describe how these relationships are made explicit.
None explicitly.
Arc there recommended data splits (c.g., training, development/valilatiio,, testing)? If so, please provide a description of these splils, explaining the ralionale behind them.
The datasets are included the testing set. Results are measured in classification accuracy.
Are there any errors, sources of noise, redundancics in the datasct? If so, please provide descriplion.
Please refer to Section 4 and Appendix A.4 for detailed information.
Is the dataset self-contained, or does it link to or otherwise rely on external resources (e.g., websites, tweets, other datasets)? If links or relies on external resources, a) are there guarantees that they will erist, and remain constant, over time; b) are there official archival versions of the complete dataset (i.e., including the external resources as they eristed at the time the dataset created); e) are there any restrictions (e.g., licenses, fees) associated with any of the external resources that might apply to dataset
25

---

Published in Transactions on Machine Learning Research (06/2025)
consumer? Please provide descriptions of all external resources and any restrictions associated with them, as well as links or other access points, as appropriate.
The dataset entirely self-contained.
Does the dataset contain data that might be considered confidential (e.g., data that is protected by legal privilege by doctor-patient confidentiality, data that includes the content of individuals' nonpublic communications): If so, please provide description.
All are image which contents vehicles, animals, etc. It is not considered confidential.
Does the dataset contain data that, if viewed directly, might be offensive, insulting, threatening, or might otherwise cause anxiety? If s0, please describe why. No.
Does the dataset identify any subpopulations (e.g., by age, gender)? If so, please describe how these subpopulations are identified and provide a description of their respective distributions within the dataset.
No.
Is possible to identify individuals (i.e., one or more natural persons), either directly or indirectly (i.c., in combination with other data) from the dataset? If so, please describe how.
No.
Does the dataset contain data that might be considered sensitive in any way (e.g., data that reveals race or ethnic origins, sexual orientations, religious beliefs, political opinions or union memberships, or locations; financial or health data; biometric or genetic data; forms government identification, such as social security numbers; criminal history)? If so, please provide a description.
No.
Any other comments?
None.
G.3 Collection Process
How was the data associated with each instance acquired? Was the data directly observable (e.g., raw text, movie ratings), reported by subjects (e.g., survey responses), or indirectly inferred derived from other data (e-g,, part-of-speech tags, model-based guesses for age language)? TJ the data was reported by subjects or indirectly inferred/derivel from other data, the data vulidated/veriiied.. If so, please describe how.
infereed/eerived
The data was mostly observable as raw image. The data was collected by downloading the link at: https: //www.cs. toronto. www. html http://cs23In.c stw.ford...o..o. odd/tiny--imaenet-
What mechanisms or procedures were used to collect the data (e.g., hardware apparatuses or sensors, manual human curation, software programs, software APIs)? How were these mechanisms procedures validated?
Please refer to Section 3.2 for detailed information.
If the datasct a sample from a larger set, what was the sampling strategy (c.g., deterministic, probabilistic with specific sampling probabilities)?
Please refer Section 3.1 and Appendix A.5 for detailed information.
Who was involved in the data collection process (e.g., students, crowdworkers, contractors) and how were they compensated (e.g., how much were crowdworkers paid)?
26

---

Published in Transactions on Machine Learning Research (06/2025)
The labeling tasks were deployed on Amazon MTurk by dividing the overall dataset into manageable Human Intelligence Tasks (HITs). Specifically, to construct the CT.CIFAR and CaMeicoommageNet datasets, we first partitioned the total of 50,000 images into five batches, cach containing 10,000 images. Each batch was then further divided into 1,000 HITs, with each HIT containing 10 images. Each HIT was assigned to three annotators, who received a reward of 0.03 dollar per HIT (10 images). The decision set the reward 0.03 dollar per HIT was based on the understanding that assigning complementary labels requires less effort and lower expertise compared to assigning true labels. We conducted prelininary research on typical reward ranges on Amazon MTurk and determined that this amount appropriately compensates annotators at approximately 6 dollar per hour, reflecting a fair balance between annotator effort, data quality, and cost-cffectivenees.
Over what timeframe was the data collected? Does this timeframe match the creation timeframe of the data associated with the instances (e.g., recent crawl of old news articles)? If not, please describe the timeframe in which the data associated with the instances
created.
The CL.CIFAR datasets have been collected in 2023 and CTMicrolmageNet has been collected in 2024 to expand our complementary datasets.
Were any ethical review processes conducted (e.g., by an institutional review board)? If so, please provide a description of these review processes, including the outcomes, as well as a link or other access point any supporting documentation. N/A.
Did you collect the data from the individuals in question directly, or obtain it via third partics or other sources (e.g., websites)?
All datasets are labeled by human annotators on Amazon Mechanical Turk (MTurk).
Were the individuals in question notified about the data collection? If so, please describe (or show with screenshols or other information) how notice was provided, and provide link or other access point to, otherwise reproduce, the ezact language of the notification itself.
No. All data have been asked the same question "What is the incorrect label of the picture?" and following by four multiple choices.
Did the individuals in question consent to the collection and use of their data? If so, please describe (or show with screenshots or other information) how consent was requested and provided, and provide link or other access point to, or otherwise reproduce, the exact language to which the individuals consented. N/A.
If consent was obtained, were the consenting individuals provided with mechanism to revoke their consent in the future or for certain uses? If so, please provide a description, as well as a link or other access point to the mechanism (if appropriate).
N/A.
Has analysis of the potential impact of the dataset and its use data subjects (c.g., data protection impact analysis) been conducted? If so, please provide description of this analysis, including the outcomes, well as link or other access point to any supporting documentation.
N/A.
Any other comments?
None.
G.4 Prepocessing/daaning//bbieng
Was any preprocssingg/eeannn///bbee of the data done (e.g., discretization bucketing, tokenization, part-of-speech tagging, SIFT feature extraction, removal of instances, processing
27

---

Published in Transactions on Machine Learning Research (06/2025)
of missing values)? If so, please provide description. If not, you may skip the remaining questions in this section.
None.
Was the "raw" data saved in addition to the preprocessed/ cleaned//abedt data (e-g., to support unanticipated future uses)? If s0, please prouide link other access point to the "raw" data.
Is the software that was used to preprocess/clean//alee the data available? If so, please provide link or other access point
Any other comments?
None.
G.5 Uses
Has the dataset been used for any tasks already? If so, please provide a description.
This datasets have been derived from public Matasets-CIFATRE CTFAR100, TinyImageNet200- which are popular datasets from classification learning in Computer Vision domain.
Is there repository that links to any all papers systems that use the dataset? If so, please provide a link or other access point.
For detail information, please refer our rrepository
What (other) tasks could the dataset be used for?
The dataset could be used for anything related to modeling or understanding of how model learning from inexact, incorrect data (complementary label learning).
Is there anything about the composition of the datasct or the way it was collected and preprocessed /aapassdd/lllaane cleaned/labees labeled that might impact future uses? For ezample, is there anything that dataset consumer might need to know to avoid uses that could result in unfair treatment of individuals or groups (e.g., stereotyping, quality of service issues) or other risks or harms (e.g., legal risks, financial harms)? If so, please provide a description. Is there anything dotaset consumer could do to mitigate these risks or harms?
None.
Are there tasks for which the dataset should not be used? If so, please provide description.
The datasets are collected specifically for complementary label lcarning, where models are trained using weaker labeling information rather than exact true labels. Consequently, predictions about true labels are inferred indirectly. Due this indirect labeling approach, there is a potential increased risk of privacy leakage if applied to sensitive personally identifiable image data. Thus, the datasets should not be used in contexts where the protection of user privacy is critical, where indirect inferences might inadvertently compromise sensitive personal information.
Any other comments?
None.
G.6 Distribution
Will the datasct be distributed to third partics outside of the entity (c.g., company, institution, organization) on behalf of which the dataset was created? If so, please provide a description.
Yes, the dataset publicly available on the internet.
How will the dataset will be distributed (e.g., tarball website, API, GitHub)? Does the dataset have digital object identifier (DO1)?
28

---

Published in Transactions on Machine Learning Research (06/2025)
The dataset will be hosted on our GitHub to ensure accessibility to the community, For the official DOI, please refer the official publication on TMLR.
When will the dataset be distributed?
The original datasets were first released in 2012 for CIFAR and 2015 for TinylmageNet. Our complementary dataset is released via this link]
Will the dataset be distributed under copyright or other intellectual property (IP) license, and/or under applicable terms of use (ToU)? If so, please describe this license and/or ToU, and provide a link or other access point to, or otherwise reproduce, any relevant licensing terms or ToU, as well as any fees associated with these restrictions.
The crawled data copyright belongs to the authors of the reviews unless otherwise stated. There is no license, but there is request to cite the corresponding paper if the dataset is used: Learning mulliple layers of features from tiny images, Alex Krizhevsky, University of Toronto, 05 2012, and Tiny imagenet visual recognition challenge, Ya Le and Xuan S. Yang, 2015. The CL.Image datasets and accompanying code are available under the MIT License. For further information, please refer our GitHub
Have any third parties imposed IP-based or other restrictions on the data associated with the instances? If so, please describe these restrictions, and provide a link or other access point to, or otherwise reproduce, any relevant licensing terms, as well as any fees associated with these restrictions. No.
Do any export controls or other regulatory restrictions apply to the dataset or to individual instances? If so, please describe these restrictions, and provide a link or other access poinl to, or otherwise reproduce, any supporting documentation.
These datasets have been driven from CIFARIO, CIFAR100, TinyImageNet200, which are known as the public datasets.
Any other comments?
None.
G.7 Maintenance
Who will be
the dataset?
Computational Learning Lab, Dept. Computer Science and Information Engineering, National Taiwan University.
How can the owner/curaaoor/naagee of the dataset be contacted (e.g., email address)?
Prof. Hsuan-Tien Lin, htlin@csie wew.@esiie.tt.edaeeeee nww..uu..... tw.
Is there an erratum? If so, please provide a link or other access point.
Currently, this dataset just has one version.
Will the dataset be updated (e.g., correct labeling errors, add new instances, delete instances)? If so, please describe how often, by whom, and how updates will be communicated to dataset consumers (c.g., mailing list, GitHub)?
All updates and changes related to the CLimage dataset will be reflected in this repository
If the dataset relates to people, are there applicable limits on the retention of the data associated with the instances (e.g., were the individuals in question told that their data would be retained for fixed period of time and then deleted)? If so, please describe these limits and explain how they will be enforced.
N N.A.
29

---

Published in Transactions on Machine Learning Research (06/2025)
Will older versions of the dataset continue to be supported/hosted maintained? If so, please describe how. If not, please describe how ils obsolescence will be commanicated to dalaset consumers.
This dataset has been hosted and maintained via our repository
If others want to extend/ auggeet//////////ee// /uild on onccontribute to the dataset, is there a mechanism for them to do so? If so, please provide description. Will these contributions be aalidated/verifieeee If so, please describe how. If not, why not? Is there process for http///niiaiiigiiisriibiiie these contributions to dalasel consumers? IJ so, please provide descriplion.
Others may do so and should contact the original authors about incorporating fixes/cttensions
Any other comments?
None.
30


Reviews:
[{"review_id": "pNEpLiRZfu", "reviewer": "Reviewer_rAqJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThe paper proposes new datasets that are more challenging than existing ones due to their practical label noise and complementary class imbalance:\n - The paper provides the general description of each dataset.\n - The paper also presents the benchmarking of current CLL methods on the two datasets, demonstrating their challenging nature to encourage the community to investigate CLL in a more practical setting.\n\n### Weaknesses\nThere are a few minor relating to the writing, such as:\n- The two subfigures in Figure 1 are uneven. Please re-make them be in the same size. In addition, it is not helpful to set the y limit starting from 0. It is more helpful if ymin is set to 10,000 for Fig. 1(a) and 1,000 for Fig. 1(b).\n- The display of the double quotes in the paragraph \"Observation 2\" on page 5 is not standard. In LaTEX, it can be done by: ``<something>''. In addition, the comma should be placed outside the double quotes. For example: \"automobile,\" should be \"automobile\",\n\nBeside that I do not see any major issues (I am not familiar to CLL in general).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes new human-annotated datasets for complementary label learning (CLL). The motivation for the creation of such datasets is to relax the assumption of class-dependent instance-independent nature in current CLL datasets to the more general setting that not only depends on each instance, but also includes real-world label noise. The paper presents a detailed analysis on the characteristics of each dataset, including class imbalance and noise rate through transition matrices. Standard benchmarking on the newly-created datasets show a significant drop in terms of performance. In general, the newly-created datasets may provide a new benchmarking for CLL, linking towards a setting closer to the one in pratice.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please make the approriate changes specified in the weaknesses.", "broader_impact_concerns": "I do not have any comment on the broader impact statement of the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ex3o1F2jDJ", "reviewer": "Reviewer_eRfs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Below, I list the *strengths* and *weaknesses* according to their importance, starting with the most important one and ending with the least important one.\n\n**Strengths:**\n- At the core of this paper, the authors contribute four *datasets with real-world complementary labels*, which is a key requirement for a realistic evaluation of CLL approaches. Moreover, the authors do not only restrict this contribution to rather low complex images of the CIFAR datasets but also include more complex images of the TinyImageNet dataset. Further, different numbers of classes as an important factor in CLL are covered.\n- The realistic *evaluation of CLL approaches* on these novel datasets is well-structured. This means that instead of only reporting the results for these new datasets, the authors additionally compare these results to the existing procedure of simulating complementary labels and identify the label noise of the crowdworkers as major reasons for the performance drops of the CLL approaches.\n- A simple *data collection protocol* allows an easy extension of this data collection by performing similar crowdworking studies for new datasets.\n- The writing and presentation is mostly clear throughout the paper. As a result, and together with the extended literature overview of CLL approaches in the appendix as supplementary material, readers can easily understand the major takeaways of this paper.\n\n**Weaknesses**:\n- Since the publication of the collected complementary labels corresponds to new variants of existing benchmark datasets, I would expect a datasheet [1] detailing the dataset's documentation and usage. Such a sheet has also been recommended by data-centric venues such as the Journal on *Data-centric Machine Learning Research* (DMLR) [2] and the *NeurIPS: Datasets and Benchmarks Tracks* in 2024 [3]. \n- The hosting platform of the data and the publication of the associated code for the evaluation is unclear. I'm aware that there is no link due to the double-blind requirement, yet brief information regarding these two aspects will be helpful for my assessment as a reviewer. Moreover, the code available during review, e.g., as supplementary material, would be helpful to assess its reproducibility and its future usage benefit for other researchers.\n- The labeling evaluation protocol needs further motivation and reasoning. For example, the specification of the concrete number of four potential classes in the prefiltering step for selecting the complementary labels is unclear. This is in particular questionable for numerous classes.\n- I understand that ResNet18 is still a common architecture for training on the CIFAR datasets and subsets of TinyImageNet. Yet, readers could question the choice of this architecture and also expect results with more modern neural network architectures.\n\n**References**:\n- [1] Gebru, Timnit, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumé Iii, and Kate Crawford. \"Datasheets for datasets.\" Communications of the ACM 64, no. 12 (2021): 86-92.\n- [2] DMLR: https://data.mlr.press/submissions.html\n- [3] NeurIPS: https://neurips.cc/Conferences/2024/CallForDatasetsBenchmarks", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors of this paper address the problem of **complementary label learning** (CLL), where a set of complementary labels is assigned per instance. In contrast to ordinary multi-class classification, such a set indicates the classes to which the respective instance does not belong. The authors of this paper identify a lack of real-world datasets with complementary labels to evaluate the practical applicability of CLL approaches. Hence, providing such human-annotated datasets would be a major advancement compared to relying on datasets with synthetic (simulated) complementary labels. For this purpose, the authors make the following key **contributions**:\n\n- The author collect and publish (in the case of acceptance) four datasets, named CLCIFAR10, CLCIFAR20, CLMicroImageNet10, and\nCLMicroImageNet20 as CLL variants of well-known image benchmark datasets.\n- The authors present a data collection protocol for creating future datasets with complementary labels.\n- The authors demonstrate in an extensive empirical analysis the shortcomings of existing CLL approaches and identify concrete reasons for these shortcomings by comparing the performance gap between their real-world CLL datasets with the commonly used synthetic ones.\n\n**In summary**, these contributions lay out the foundations for future advancements and more realistic empirical evaluations in the research area of CLL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Requested Changes:** I would appreciate it if the authors could address the aforementioned *weaknesses* and clarify the following *questions*, *minor remarks*, and the *broader impact concerns* raised below. If I have misunderstood or overlooked any aspect, I am willing to reconsider my perspective on these issues. Looking forward to a constructive discussion!\n\n**Questions:**\n- Will anonymized identifiers of the crowdworkers / annotators be published? This could be helpful to understand the worker-dependent component (e.g., different noise levels) when acquiring complementary labels.\n- Does user refer to the identity of the crowdworkers / annotators in the following statement as part of your *Broader Impact Statement*:\n> The privacy of the users may be easier to compromised as a result.\n- Will the code for labeling interface on Amazon Mechanical Turk be published to ease future crowdworking studies?\n\n**Minor Remarks**:\n- In my opinion, the appendices must not be part of the supplementary material but can follow after the references in the main paper. This will ease the access to the appendices.\n- Section 1:\n> Moreover, through ~thorough~ analysis we confirmed that ... \n- I would propose to use \\cite instead of \\citep when using the reference as a direct part of the sentence, such that the authors names are not in round brackets. For example, this would correspond to the following change in Section 2.3:\n> The pioneering work by ~(Ishida et al., 2017)~ Ishida et al. (2017) studied\n- Appendix A.1: \n> ... and described the process how MicroImageNet10 and MicroImageNet20 datasets ~generation~ were generated ...\n- Figure 1 and 7 contain graphs with ticks of rather small font sizes on their x-axes. These should be increase, if possible. Moreover, when zooming in, the font is quite blurry. Maybe you can use PDFs to avoid such things. Feel free to check these comments also for the other figures to improve the overall presentation of your paper.\n- The notation of the *softmax* function is inconsistent when comparing Eq. (2) in the main paper with Eq. (3) in the appendices.\n- By changing the column order in Table 1, a direct comparison between uniform-CIFAR10 and CLCIFAR10 will be easier.", "broader_impact_concerns": "Complementary labels were collected using crowdworkers on Amazon Mechanical Turk. It is essential to ensure that these workers receive fair compensation. Therefore, in addition to stating the payment provided, a detailed explanation of the rationale behind the payment structure would be valuable. Such a rationale will be also required when including the aforementioned datasheet.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Dxvt7MuOnV", "reviewer": "Reviewer_1Ytp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written, and it's easy to follow.\n- The motivation for the need for human-annotated datasets for CLL is well described.\n- 4 datasets are suggested to show the consistency of their protocol in building the CLL dataset.\n- Enough ablation studies have been conducted.\n\nWeaknesses:\n- When annotating the image, the authors asked annotators to select a \"wrong\" label. This is why there's a biased transition matrix with irrelevant classes between true labels and complementary labels in Figure 2. What I think is more natural is to ask annotators to select \"the best\" label among the given four labels without including the true label. The reason I said natural is that people tend to wrongly label when it's difficult to distinguish between true class and wrongly annotated class (e.g. \"river\" instead of \"pond\" when the image is about a satellite pond image). This thought is somewhat similar to [A] which suggests image-dependent noisy annotation in the partial label learning.\n\n[A] Instance-Dependent Multilabel Noise Generation for Multilabel Remote Sensing Image Classification, IEEE JSTARS.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The task the paper focuses on is the Complementary-label learning (CLL). While the previous methods on CLL were built upon the synthetic dataset with certain assumptions about the generation of complementary labels, the authors claim that this assumption is far from the human behavior, brining a distribution gap. The authors develop a protocol to collect complementary labels from human annotators based on CIFAR10, CIFAR100, and TinyImageNet200, suggesting 4 datasets: CLCIFAR10, CLCIFAR20, CLMicroImageNet10, CLMicroImageNet20. The study reveals that annotation noise is the most influential factor, and the gap in the annotation distribution between the synthetic dataset and their human-labeled dataset is attributed to a huge performance gap when using state-of-the-art methods for CLL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to hear about the authors' thoughts on the weaknesses mentioned above.", "broader_impact_concerns": "The broader impact is somewhat described.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers' scores were accept, accept, and leaning accept. All reviewers are satisfied with the rebuttal and the updated paper, and appreciate the realistic benchmark and analysis for complementary labels. 

Although I recommend "Accept as is", it would be helpful if the paper incorporated the following suggestions:

- Cite Gebru et al. 2021 and note that their template/questions were used for Appendix H.
- In the Broader Impact Statement, the sentences "While our CLImage datasets do not belong to those. We suggest practitioners exercise caution when studying such applications." should be merged into a single sentence.
- The precise instructions that are provided to the annotators are missing from the paper. From the demo (mp4 file) in the anonymous github repository, I see the instruction `Choose any one "incorrect" label for this image`. It also appears that five example images are shown next to each of the four class options. It's possible I missed it, but these two pieces of information should be included in the paper in addition to the github readme.
- The answer to the question "Will the dataset be distributed under a copyright or other intellectual property (IP) license, and/or under applicable terms of use (ToU)?" in the Appendix only provided information about the original dataset. My understanding is that this question is asking the license about your new dataset (or labels). Please state the license for your neew dataset as well.
- Reference: "Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. Report of CS231N: Deep Learning for Computer Vision Course, 2015. Standford University." Correct imagenet to ImageNet and Standford to Stanford.
- Reference: "Learning multiple layers of features from tiny images" is a single-authored paper according to https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf
- Abstract: Regarding "Secondly, their evaluation has been limited to synthetic datasets.", I'm wondering if it would be more precise to say "synthetically labeled datasets" because a "synthetic dataset" sounds like the inputs/features are also synthetic, e.g., Gaussian distributions, two moons.
Decision: Accept (poster)