Intra-Cluster Mixup: An Effective Data Augmentation Technique for Complementary-Label Learning
Authors: Tan-Ha Mai
Hsuan-Tien Lin
Venue: Accepted by TMLR ()

Abstract: In this paper, we investigate the challenges of complementary-label learning (CLL), a specialized form of weakly-supervised learning (WSL) where models are trained with labels indicating classes to which instances do not belong, rather than standard ordinary labels. This alternative supervision is appealing because collecting complementary labels is generally cheaper and less labor-intensive.
Although most existing research in CLL emphasizes the development of novel loss functions, the potential of data augmentation in this domain remains largely underexplored. In this work, we uncover that the widely-used Mixup data augmentation technique is ineffective when directly applied to CLL. Through in-depth analysis, we identify that the complementary-label noise generated by Mixup negatively impacts the performance of CLL models. We then propose an improved technique called Intra-Cluster Mixup (ICM), which only synthesizes augmented data from nearby examples, to mitigate the noise effect. ICM carries the benefits of encouraging complementary label sharing of nearby examples, and leads to substantial performance improvements across synthetic and real-world labeled datasets. In particular, our wide spectrum of experimental results on both balanced and imbalanced CLL settings justifies the potential of ICM in allying with state-of-the-art CLL algorithms, achieving significant accuracy increases of 30% and 10% on MNIST and CIFAR datasets, respectively.

Published in Transactions on Machine Learning Research (01/2026)
Intra-Clusted Mixup: An Effective Data Augmentation Tech- nique for Complementary-Label Learning
Tan-Ha Mai Department of Computer Science and Information Engineering, National Taiwan University
di d10922024 @csie.nttccs......... edu.
Hsuan-Tion Lin'
hilin@tcsic.ntuu edu.
Deportment of Computer Science and Information Engineering, Artificial Intelligence Center of Research Ezcellence, National Taiwan University
Reviewed on OpenReview: https: openreview. net/ forum? id=
Abstract
In this paper, we investigate the challenges of complemenntary-label learning (CLL), a spe- cialized form of weakly-superoised learning (WSL) where models are trained with labels indicating classes which instances do not belong, rather than standard ordinary labels. This alternative supervision is appealing because collecting complementary labels is gener- ally cheaper and less labor-intensive. Although most existing rescarch in CLL emphasizes the development of novel loss functions, the potential of data augmentation in this do- main remains largely underexplored. In this work, we uncover that the widely-used Mixup data augmentation technique is ineffective when directly applied to CLL. Through in-depth analysis, we identify that the complementary-label noise generated by Mixup negatively impacts the performance of CLL models. We then propose an improved technique called Intra- Cluster Micup (ICM), which only synthesizes augmented data from nearby examples, to mitigate the noise effect. ICM carries the benefits of encouraging complementary label sharing of nearby examples, and leads to substantial performance improvements across syn- thetic and real-world labeled datasets. In particular, our wide spectrum of experimental results on both balanced and imbalanced CLL settings justifies the potential of ICM in al- lying with saate-of-theaars CLL algorithms, achieving significant accuracy increases of 30% and 10% on MNIST and CIFAR datasets, respectively.
1 Introduction
Obtaining high-quality labels is often expensive, time-consuming, and sometimes impossible in real-world applications. To address this challenge, weakly-supervised learning (WSL) has been extensively studied in recent years. WSL aims to train proper classifier with inaccurate, incomplete, or inexact supervision (Zhou, 2017). Contemporary WSL studies have significantly expanded our understanding machine learning capabilities, encompassing areas such as learning from complementary labels (Ishida et al., 2017), learning from multiple complementary labels (Feng et al., 2020), learning from partial labels (Jin & Ghahramani, 2002), or mixture of ordinary and complementary labels (Ishida el al., 2017).
This paper focuses complementary--abel learning (CLL) (Ishida et al., 2017), WSL problem where complementary label designates class to which specific instance does not belong. The CLL problem assumes that. the learner only has access to complementary labels during training while still expecting the learner to predict the ordinary labels correctly during testing. Complementary labels serve as a viable alternative when it is difficult or costly to acquire ordinary labels (Ishida et al., 2017). For instance, collecting
*Corresoodingg author.

---

Published in Transactions on Machine Learning Research (01/2026)
ordinary labels numerous classes not only demands annotators with excellent knowledge for selecting the correct labels but also requires more time for accurate labeling. CLL models can extend the horizon of machine learning and make multi-class classification potentially more realistic when ordinary labels cannot be casily obtained (Ishida et al., 2017).
Existing CL.. studies have primarily focused on designing loss functions that are converted from well-known ordinary classification losses (Ishida et al., 2017; 2018), often under the assumption that complementary labels are uniformly generated (Cao et al., 2022; Feng et al., 2020). Building on this line of work, (Wang et al., 2024) recently proposed novel data generation assumption inspired by positive-unlabeldd learning, offering fresh perspective on how complementary labels may be distributed. Collectively, these bossffunction-based approaches address the CLL problem from an algorithmic perspective and significantly contribute to our understanding of the design space for CLL models. Despite this focus, the potential of data augmentation in CLL remains largely unexplored. This notable gap in the literature motivates our study on developing and assessing data augmentation techniques to improve the efficacy of CLL models.
Data augmentation techniques are known to be powerful "add-ons" " to machine learning models for en- hancing their performance by improving generalization, robustness to noise, and invariance to transforma- tions (Mikolajczyk & Grochowski, 2018; Rebuffi et al., 2021). Across range of classification scenarios (Chou et al., 2020a), successful data augmentation ion techniques exhibit seamless integration with algorithmic ap- proaches to boost their performance. Some data augmentation techniques create pseudo examples that are variations of the original examples, without re-labeling them (Shorten & Khoshgoftaar, 2019; Jiang et al., 2021). Other techniques construct synthetic examples with modified labels (Lin & Lin, 2023). Motivated by recent studies on multiple complementary-label learning (Cao et al., 2022; Feng al., 2020), we conjecture that utilizing multiple complementary labels through label sharing has the potential to improve existing CLL models, and thus resort to et al., 2018) because of its natural potential in encouraging complementary--abee sharing. While Mixup is well-known for its simplicity and effectiveness (Li & Jia, 2025; Navarro & Segarra, 2023; Xie ct al., 2023), the application of Mixup for CLL remains unexplored prior lo our work.
techniques. Among such techniques, we choose Mixup (Zhang
With a wide spectrum of experiments across balanced and imbalanced CLL settings, we confirm that applying Mixup on the complementary labels has the potential to improve various state-of-the-art CLL models by encouraging label sharing, which helps the machine identify the ordinary label more efficiently (Lin & Lin, 2023; Chou et al., 2020b; Yu et al., 2018). But the potential comes with serious side effect. In particular, sometimes the complementary labels on which Mixup manipulates contains an ordinary label of one of the examples, which introduces noise to the label sharing process. The noise significantly deteriorates the performance of the CLL. model because of overfitting. The side effect suggests that original Mixup does not work off- off-the-shelf for CLL.
To mitigate the side effect, we design novel data angmentation technique called Intra- Caiua-Custtr Mirup (ICM). ICM clusters the examples before applying Mixup within each cluster. The clustering design reduces the noise introduced by Mixup while keeping its potential benefits. Our empirical experiments demonstrato that ICM consistently enhances the CLL performance across a variety of state-of-the-art CLL models and a broad spectrum of settings, ranging from balanced to imbalanced classification. Furthermore, we expand our empirical comparison from 4 common benchmark datascts in cxisting studics to 7, including both synthetic and real-world labeled datasets. Our efforts significantly broaden the scope of benchmarks in the field. Our unique contributions can be summarized follows:
To the best of our knowledge, we are the first to introduce a novel data augmentation technique specifically designed for CLL contexts. We identify two critical insights: (i) the original Mixup fails in CLL settings due to noise introduced during the label sharing process, and (ii) mixing samples within the same class proves to be a more effective strategy.
We propose ICM, a tailored data augmentation technique that addresses the unique challenges of CL.. and consistently enhances the performance across various CLL models.
2

---

Published in Transactions on Machine Learning Research (01/2026)
We conduct extensive benchmarking on large CLL datasets, covering range from synthetic real- world labeled datasets. Our studies span a diverse spectrum of settings, from balanced to imbalanced CLL, justifying the effectiveness of our framework.
2 Problem Setup
2.1
Complementary-Label Learning
In CLL, we are given a dataset D = {(x, U:)] where each instance x, E R' represents an input image, and Mi E R is a complementary label. The complementary label Di indicates class that the image x; does not belong. The dataset consists of N samples, and the goal of CLL to use this complementary label information to train classifier. In this context, the complementary label satisfies the condition Vi [K] (..) where y/ is the ordinary label of x,, K denotes the total number of classes in the dataset, with K > 2. The set [K] = (1, 21. K) represents the set of all possible class labels. This implies that is one of the incorrect classes for the instance x, The training set D is denoted as = X x Y, where X contains the input images and Y contains the corresponding complementary labels. In contrast to traditional multi-class classification, where the ordinary label y is used to train a classifier, the CL.L setup trains the model using the complementary label Dr- However, the objective CLL remains the same: to train a classifier g that accurately predicts the ordinary label yi for unseen instances. Generally, the classifier g is realized through decision function g: Rd + RK with the classification determined by taking the argmax on h. For example, g(x) (x)) where h(x); represents the score or confidence that the instance x belongs to class k. The classifier selects the class with the highest score.
.......
2.2 Recent Approaches of Complementary-Label Learning
Recent approaches to CLL share a common characteristic: they apply various surrogate loss functions to the standard classifier. For instance, (Ishida et al., 2017; 2019) developed an unbiased risk estimator (URE) for arbitrary losses on the standard classifier when employing a uniform transition matrix. When the risk is defined as the classification error, the URE serves as a surrogate metric for performance evaluation. How- ever, UREs are prone to severe negative empirical risks during training, which is indicative of overfitting. To mitigate such overfitting in algorithm design, (Chou et al., 2020b) proposed the surrogate complementary loss (SCL), which is based on minimizing the likelihood associated with complementary label. They justified this approach by showing that. SCL constitutes upper bound to constant multiple of the standard classi- fication error when the transition matrix is uniform. Another study by (Yu et al., 2018) examined scenarios where the complementary label are not uniformly generated. (Yu et al., 2018) introduced a framework called forwurd correction (FWD) that adapts techniques from noisy label learning (Patrini al., 2017) to adjust the softmax cross-entropy loss. This achieved by adding a transition layer to the output of the model: g(x) T gxx), and then utilizing the cross-entropy loss between g(x) and the complementary labels y. Other rescarch efforts have explored advanced applications beyond single complementary label, including learning from multiple complementary labels (Cao et al., 2022; Feng et al., 2020), and integrating learning from both ordinary and complementary labels (Katsura & Uchida, 2020).
3 Proposed Method
In this section, we propose ICM, novel data-augmentation technique for CLL. First, we evaluate the performance of the standard Mixup method under varions experimental conditions to identify the factors that undermine its effectiveness. Next, we develop enhanced augmentation algorithms that explicitly address these limitations. Finally, we derive and introduce surrogate complementary-label loss function that seamlessly integrates ICM into the training process.
3.1 Why Mixup does not work?
Applying Mixup naively in the CLL setting results in substantial complementory-labe noise. This noise arises when the ordinary label appears in the synthetic data generated via original Mixup, thereby violating
3

---

Published in Transactions on Machine Learning Research (01/2026)
Input Image X, label Y
Cluster
Embedding Vector
A
K-means
Siamese Encoder Network
Clustering
Cluster
Iiput Image X
Cluster 2
Generated Synthetic Data
synthetic sa sample
Not Dog
Not Bird
sample
sämple
Not Cat
Prodictor
Complementary Labels
Intra Cluster Mixup (ICM)
Similantt
Figure 1: Illustration of the Intra- Cluster Micup (ICM) framework. Top: Embedding features are extracted using pretrained SimSiam encoder and clustered using k-means, aiming to group samples with similar ordinary labels. Bottom right: Within each cluster, ICM generates synthetic samples by interpolating features and labels, which are then used to train the classifier.
the core assumption of CLL: Is E [K] measuring the noise ratio introdueed by Mixup in a controlled CLL setting. Although CLL typically operates under the assumption that ordinary labels are unavailable or costly to obtain, adopt proof-of-coneey setup where ordinary labels are accessible soicly for quantifying the noise. Using the SCL-NL loss (Chou et al., 2020b) and a ResNet18 backbone (He et al., 2016) trained on CIFAR10, we observe that Mixup introduce a noise level of 15.81% (as indicated by the green triangle in Figure 2a). Notably, when training is performed under noise-free conditions, model accuracy improved by 7%, indicating high sensitivity to label noise (highlighted by the orange circle Figure 2a). These results highlight that label noise in CLL substantially degrades performance. From these observations, intree mathematical framework for analyzing complementary classification error under Mixup augmentation.
\ ys. To cmpirically verify this claim, we conduct an ablation study
Definition 1 (Complementary classification error). Let {(x,, v:) be the training examples, where E Rd is the input and Yi {1,..., K} is the complementary hard label of the i-th example. Let Rd + [1,...,K} be a classifier and let -(: denote a loss function. For any input x, define the per-class loss vector (g(())) = is an index randomly sampled from the same cluster as i), we construct mixed input & = +1 X)x,. where \ Beta(a, a) and Ji.j denotes the corresponding soft label generated via Mixup. The complementary classification error of g under loss l is defined
[, gxx]] Given two training samples x; and from the same cluster (j
N
Ruclo; 0)
1
Σ
((.), = (xx.))_(( + g(x)]],
(1)
N
For Mixup-generated pairs (Ri,j) Di.s), the complementary classification risk under soft labels is defined as
1 N N
R.il9; E) = Σ (T.3))(()..)) = LE (xx0)> 1v + gXxs,)) + B Ly # g(x;,)l
(2)
Definition 2 (Error generated by label noise). The error generated by label noise for the classifier g is
defined as
(()) = ( I = g(x)],
(3)
that is, E(g) is the probability that g predicts the complementary label itself.
Here, denotes the indicator function: any condition A, [A] if holds and atherwise.

---

Published in Transactions on Machine Learning Research (01/2026)
Proposition (Complementary error with Mixup). For dixxup-generated pairs (R1,) Dr.)). the complemen- tary classification risk under Mixup is
1 R'
(
(4)
N
and admits the decomposition
R'; E) XIE (x.))> li + (xx,))) +11 (x Lūs + g(x15)) + ss; +1 N)8z-
(5)
where and Eg are the local noise errors defined in equation 3, and satisfy e(g) = 1
N Ei=1 6,- Thus, the
Mixup risk Rg; E) consists of two classification-crro terms weighted by À and 11-X), plus the corresponding contributions from the local label-noise errors of the samples participating in the Mixup pair.
Proof. Refer to Appendix A for the proof.
A
A
Original Moxup
Mixup Noise Free
Method
Noise Ratio (%)
15
67.28 87.26%
A
Original Mixup
Extra-Class Mixup NF
MSE
2-
MSE
10
Intra Chass Mixup NF
1-
2-
5-
74.29%
85.46%
0
0
100
200
300
0
100
200
300
Epochs
Epochs
65
70
75
80
85
90
KMNIST
CIFAR10
Accuracy (%)
(a) Relationship between noise ratio and model perfor- mance on CIFAR-10 with the SCL-NL loss and ResNet18 when applying original Mixup, Extra-Class Mixup Noise- Free (NF) and Intra-Class Mixup NF Increasing the noise ratio in original Mixup degrades model performance. Fur- ther ablation study reveals that same class Intra-Class Mixup NI can more beneficial.
(b) Comparison of gradient estimation between original Mixup and Mirup Noise-Free on MNIST and CIFAR1O, using the SCT--NI loss function and ResNet18 architecture. Micup Noise-Free demonstrates lower gra- dient estimation error than the original Mixup on both datasets, attributed to reduced noise interference, which impacts classifier performance CLL contexts.
Figure Analysis of the impact of noise and Mixup Noise-Free (NF) on complementary-label learning performance.
The equation 5 emphasizes that minimizing complementary loss under Mixup requires careful control of the noise rate in the generated data. Specifically, it is critical to minimize instances where y yj Ug y/. such occurrences increase the error term in equation 5.
To further explore this effect, we evaluate gradient estimation error under noisy and noise-free setups. Let f denote the true gradient and c the complementary gradient estimator. The estimation error is defined as E Fxxx..)) - 2) As shown in Figure 2b for MNIST and CTFAR10, the error associated with Mizup Noise- Free is consistently lower than that of original Mixup, reinforcing that label noise compromises optimization effectiveness.
Beyond quantifying noise, investigate whether the original Mixup strategy used in ordinary learning transfers effectively to the CLL setting. In traditional supervised lcarning, original Mixup interpolates inputs and labels from different classes, which encourages smooth decision boundaries. In contrast, CLL imposes constraints that make such cross-class interpolation problematic. We hypothesize that mixing data within the same class, termed Intra- Class Mixup, preserves the CLL constraint D. E [K] yi and reduces noise. To evaluate this, we synthetically generate intra-class and extra-class samples under a noise-free free setup. Results in Figure 2a (highlighted by the blue square and orange cirele) reveal that Intra- Class Micup Noise-
5

---

Published in Transactions on Machine Learning Research (01/2026)
Free² outperforms Extra- Class Mirup Noise-Free" by 11%. This significant margin validates our hypothesis: intra-class mixing is more suitable in the CLIL context and significantly improves performance.
The experimental results indicate that original Mixup can be effective under noise-free conditions, eliminating noise typically requires access to ordinary labels which contradicting the fundamental assumption of CLL. To address this challenge, we propose a dedicated framework for CLI,, referred to as ICM. This framework is specifically designed to reduce synthetic label noise without requiring knowledge of the ordinary label. The following subsection provides detailed explanation of the ICM framework.
3.2
Mixup in CLL
As discussed in above subsection, we introduce a specialized design for CLL called ICM, illustrated in Fig- ure 1. Our proposed methodology, 1CM, comprises two primary components. First, feature representations are extracted from the training data using a sclf-supervised learning model based on SimSiam (Chen & He, 2021). These embeddings are then clustered using k-means to group samples with similar feature character- istics, as shown in the top of Figure 1. This clustering step assigns bluter-bbseed labels to sample and serves as pro-processing phasc. Second, synthetic complementary samples are generated by mixing inputs and labels within the same cluster, as illustrated in the bottom right of Figure 1. These augmented samples are then used to train the classifier. The procedure is defined as:
スソ = Ax; + (1 - A)x;
(6)
J = Xy + (1 - A)Øn
(7)
Integration of ICM into the training process detailed Algorithm After clustering the dataset D, ICM selects pairs within the same cluster generate synthetic complementary samples using equation 6 and equation 7. Here, À is sampled from beta distribution 3(a, a),, and the selected pairs (x,, Bs) and (xz.ū) are drawn uniformly from the training data.
Clustering plays a critical role by reducing label noise during data augmentation. Grouping samples within clusters encourages mixing between instances that are more likely to share the same true label. This increases the likelihood that the complementary label condition y E [[]] yys holds across the cluster, thereby reducing the risk of introducing noise. To further investigate the effect of encoder choice in our method, we conduct an ablation study comparing SimSiam with other self-supervised encoders; detailed results are provided in Appendix D.7.
To evaluate ICM, we conduct an ablation study comparing it with original Mixup. As shown in Figure 3a, ICM significantly reduces the noise ratio. For instance, on MNIST, the ratio drops from 16.24% with Mixup to 0.95% with ICM. The effectiveness of noise reduction correlates with dataset complexity; simpler datasets such as MNIST, KMNIST, and FMNIST exhibit greater improvements than more complex datasets like CIFAR1O and CIFAR20. This reduction in noise ratio is mirrored by substantial performance improvements. As shown in Figure 3b, TCM consistently outperforms the original Mixup across all algorithms, with gains ranging from 13% to 20%. These results validate the benefit of incorporating clustering into original Mixup for reducing label noise in CLL.
Surrogate Complementary Loss with ICM We propose data augmentation for the existing loss- based CLL algorithms. In CLL, to minimize the non-convex (0-1) loss in complementary learning, a common approach in statistical learning is to use a convex surrogate loss to approximate the target loss. In our work, we use to donote the surrogate complementary loss (SCL) loss functions and we combine our proposed data augmentation technique ICM with SCL during the training process. The main idea behind ICM data augmentation for complementary labels is assign new complementary label and incorporate additional information from samples within the same cluster, which share the same ordinary label. This approach euables the model to access not only more complementary labels but also new information about the samples.
Plutra-Class Mixup Free: proof-of-coneept variant we designed prior to our proposed method. In this sctting, Mixup applied only between samples from the same class, so additional label noise introduced. Fxtra- Mixup Noise-Fres Mixup applied between samples cross different. class.
6

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm 1: ICM training with cluster-consistent Mixup. Lines 1-3: extract SimSiam embeddings and assign h clusters. Lines 4-12: synthesize (x, 0) by interpolating pairs within the same cluster using Eq. (6) (7) Lines 13-14: update on the synthetic batch.
Input: Complementary-labbllde dataset D = {x,, 3)) model fa.
Output: Trained parameters 0.
(1) Embedding: 2; + (X,) for i = I,...,NN
1/ Faim: pretrained SimSian encoder (2) Clustering: run k-means on {z:} to obtain cluster labels e, (1,...,k).
(3) Augment data: D - {(x,, Mi, 4)
while not converged do
(4) Sample a minibatch B C D.
(5) For each cluster u E {l...., ,, form B, = BB:c)
(6) Initialize synthetic set B + 0.
foreach u with [B,] 2 2 do
for m to Ma do
10
(a) Draw two distinet pairs (x,, Di, u), (xj, My. u) Bu. // sampling the namples in same cluster. Beta(q, a). (c) Obtain ICM imput & using Eq. (6).
11
(b) Sample
13
(d) Compute label mixing coelficient Ag-
14
(e) Generate ICM label using Eq. (7).
(T) Append (x,0) to B.
16
77) Compute loss: (() 1 Lx (g((x)
B
// training model with new synthetic data.
17
8 Update: 0 + n Vol(O).
SCL-NL
+13.8
15
Nolse Ratio (%)
FWD
14.8
11.90
10.85
15.29
15.27
3.03
+20.4
SCL-EXP
+13.0
MNNIST
KMNIST
FMÑIST Datasets
CIFAR10
CIFAR20
60
65
70
75
80
85
Accuracy (%)
Mixup
ICM (ours)
Baseline
Mixup
ICM (ours)
(a) Noise ratios the Mixup and ICM methods across five datasets.
(b) Test accuracy of Mixup and TCM across different.
algorithms CIFAR10
Figure 3: Comparison of the noise ratio across datascts (Ieft) and the test accuracy of Mixup and ICM for different algorithms on CIFAR10 (right).
Additionally, it helps to reduce the noise that may arise when selecting pairs for data augmentation during training. thereby improving the overall learning process.
In loss based complementary learning algorithms, a loss function [K] x RK + R employed, which takes as input both the complementary label y: and the prediction output the model g(x;). The objective of learning process is to minimize this loss function & over the complementary dataset D. which can be formulated as:
N L(g: = N Σ (F.
(8)

---

Published in Transactions on Machine Learning Research (01/2026)
When incorporating the ICM data augmentation during training, the CLL loss function is updated as follows:
N N
N xe xe((ino(rrss)) + (1- (1-)))((s.
1
()
(9)
N
where [0, 1] 3(a, a) (beta distribution), for E (0, o0), X, in equation 6, Visj in equation 7, is random sampling from the same cluster of i, and N is the size of training dataset. To better distinguish from 0 0-1 based methods, we convex surrogate loss to approximate the target loss, denotes L. In fact, previous research in complementary learning has revealed similar patterns focused on minimizing the predictions of label classes, including approaches such as:
Negative learning loss (SCI.NTL) in (Kim et al., 2019) modified log loss specifically designed for negative learning with complementary labels:
fNI (ū.) = log((1 P5 + 7), where 0 0<7 <.
(10)
Exponential loss (SCL-EXP) (Chou et al., 2020b):
fEx (ū.9(x)) = exp(pg).
(11)
Forward correction (FWD) in (Yu et al., 2018) is method for correcting loss using a forward correction approach based on given transition matrix T:
(FwD(ū. = {(ū, T p). T)p).
(12)
Here, 7 is a constant added to the loss function to prevent the SCL-NL loss from approaching infinity when Pý equals 1, E K-1 represents the probability output of learning model if g passes through a softmax layer, and A K- the K-dimensional simplex.
4 Experiments
In this section, evaluate 1CM synthetic and real-world datasets under both balanced and imbalanced conditions, comparing it with state-of-the-art CLL basclines. Our findings demonstrate that ICM signifi- cantly enhances performance and effectively addresses key CLL challenges.
4.1 Experiment Setup
Datasets. We assess the effectiveness of our proposed 1CM framework across five synthetic labeled datasets: CIFAR1O, CIFAR20, MNIST, KMNIST, and FMNIST. The synthetic labeled datascts consist of CIFAR10 (Krizhevsky et al., 2009) and CIFAR20, each containing 50,000 training samples and 10,000 testing samples. CTFAR10 encompasses 10 classes, whereas CTFAR20 comprises 20 superclasses derived from CIFAR1O0 (Krizhevsky et al., 2009). We do not benchmark on CIFAR100, as existing CLL algorithms have not demonstrated the ability to learn a meaningful classifier on this dataset when given only one com- plementary label per data instance. MNIST (Tecun al., 1998), KMNIST (Clanuwat al., 2018), and FMNIST (Xiao et al., 2017) cach consist of 60,000 training samples and 10,000 testing samples, with all three datasets featuring (en classes.
Additionally, we evaluate our framework on real-world labeled datasets, including CLCIFARIO and CLCI- FAR20 (Wang et al., 2025), which use the images from CIFAR10 and CIFAR20, respectively, with comple- mentary labels annolated by humans. In CLL, MNIST and CIFAR are standard datasets. Researchers have not transitioned to large-scale datasets with numerous classes, such as TinyImageNet (Le & Yang, 2015) and ImageNet (Deng et al., 2009). Preliminary tests reveal that statc-of-the-art CLL. algorithms struggle to produce meaningful classifiers for 100 classes, even with uniformly and noiselessly generated synthetic complementary labels. This is why existing CLL algorithms evaluated datasets with 10, 20 classes.
8

---

Published in Transactions on Machine Learning Research (01/2026)
Table 1: Top-1 validation accuracy (%) on balanced (bal) p = 1 and long-tailed imbalanced (imb) ratio P 10, K cluster = 50 setups. The methods used are SCL-NL (S-NL), FWD-INT (FWD), SCL-EXP (S-EXP), DM losses, and ResNet18. Best performance is highlighted in bold.
Imbalanced (bmb)
Balanced (bal)
Method
CLCIFARIO CLCIFAR20
CLCIFARI0
CLCIFAR20
S-NL.
17.770.20
5. 5.800.03
37.59h.40
8.53p.24
S-NL+
21.28p.51
6.64g.48
42.960.54
9.13p.44
S-NL FIM (ours)
28. 28.440.05
7.55p.08
56.63p.5t
11.26
DM
15.19..18
5.760.06
38.20
8.34p.08
DM+Mix
22.99g.22
6.92g.21
42.61p.48
9.120.32
DM+ICM (ours)
27.880.94
7.10p.02
53.044.40
11.470.18
FWD
12.07
5.980.17
42.98g.36
21.100.23
FWD+ Mix
17.06g.89
6.100.16
42.38o.05
21.48p.19
FWD (ours)
18. 18.23
7.73p.09
58.91 58.970.21
35.94g.38
S-EXP
17.37p.16
5.99g.21
41.42p.68
8.56g.25
S-EXP+Mix
20.38o.40
6.84g.13
43.56p.13
9.04g.21
S-EXP+ICM (ours)
27.52g.06
7.010.08
56.26p.15
11.20p.06
Baseline Methods. Our framework can be applied with different methods, we choose SCL-EXP, SCL- NT. (Chou et al., 2020b), FWD-INT (Yu et al., 2018), DM (Gao & Zhang, 2021) as our cooperators to validate the efficacy of our approach.
Implementation Details. For fair comparison, we choose RestNet18 (He et al., 2016) as our backbone. We train the model with a batch size 512 for 300 epochs and an initial learning rate of 10 10-4, weight decay 10-1, and optimizer Adam (Ye et al., 2024). In the long-tailed imbalance setting (Cui et al., 2019; Cao et al., 2019), the difficulty of a dataset commonly characterized by the class imbalance ratio, defined as P min, n,
ni where n, denotes the number of samples in class i. A dataset is said to exhibit long-tailed émbolance with ratio p when the class sizes follow an exponentially decreasing sequence whose common ratio is p1 across the K classes. This construction ensures that the ratio between the largest (head) class and the smallest (tail) class is exactly All the experiments were run with Tesla V100-SXM2, 32GB memories. The hyper-parameters can be appropriately tuned via the validation process. For each subtask, we run the experiments three times. Other implemented details, including parameer selection through validation process such as a, K cluster, can be found our supplementary matcrials Appendix D. We experiment our proposed method across a wide spectrum of both balanced and imbalanced CLL settings. For imbalanced CLL, follow (Cao al., 2019) to generate long-tailed distribution dataset with different imbalance ratios on ordinary datasets. Details of the different imbalanced setups can be found in the Appendix B.
4.2 Results and Analysis
We compare our results with several baselines, including without Mirup and with Mirup (Miz), to verify the efficacy of our proposed method. Additionally, our method can be integrated with various base algorithms such as SCL-NL, FWD-INT, DM, and SCL-EXP.
The results for the real-world labeled datasets, CLCIFAR10 and CLCIFAR20, both in balanced and im- balanced settings with different loss functions, presented in Table 1. For the synthetic labeled datasets (CIFAR10, CIFAR20, MNIST, KMNIST, and FMNIST) with setup 1, spanning from balanced to various imbalance ratios, detailed results are shown in Tables 2. Additional experimental details for selup and setup 3, with varying imbalanced ratios, can be found in Appendix B. Our proposed method consistently outperforms the basclines across all setups, from balanced to imbalanced scenarios, and achieves significant performance improvements when integrated with different base algorithms. To assess whether the observed improvements statistically significant, compute values the CIFAR-10 and CLCIFAR-110 datasets.
9

---

Published in Transactions on Machine Learning Research (01/2026)
82
p-value: 0,00000230
56
p-value: 0.00000177
81
p-value: 0,00000187
66
p-value: 0.00000354
80
Accuracy (%)
54
Top-1 Accuracy (96)
78
63
52
60
75
Top-1 Accuracy
57
74-
CIFAR10
CLCIFARIO
72
CIFARIO
CLCIFAR10
54
72
46
69
51
70
44
66
48
68
66
42
63
45
Mixup
ICM
Mixup
ICM
Mixup
ICM
Mixup
ICM
(a) S-NL algorithm.
(b) FWD algorithm.
Figure 4: Comparing the p-value of different between Mixup and ICM method on CIFAR1O and CLCIFAR10 with S-NL (right) and FWD (left) algorithms both balanced and imbalanced (p 100) scenarios.
Table 2: Top-1 validation accuracy (%) for p 100 (long-tailed imbalancod) and p = 1 (balanced) sctups across CIFARIO, CIFAR20, MNIST, KMNIST, and FMNIST datasets using ResNet18 and different. loss methods.
CIFARIO
C1EAR20
MNIST
KMNIST
FMNIST
Method
p= 100
p=
100
p=
100
p 100
p=1
100
S-NL
22. 31
65.47o.05
10.65
24.146:33
50.15
97.78p.21
35.17a.7
88.92..14
51.93p.3
85.15p 10
S-NL Mix
31.466.ns
67. 10..11
13.47a.46
26.45p.o7
54.23p.48
96.6 06.644.11
37. 37.250.53
79.04a.16
56.07n.s7
84.35p.as
S-NL ICM
36. 36.21o.19
79. 04
18. 18.11
39. 39.17o.15
85 83.83..19
98 20
63. 63.70p.s4
89.09o.as
87.800.40
25..50.00
FWD
22.20o. an
64.296.33
8.430.29
23.18p.34
50.26g.57
97. 97.496.0s
35.296.37
80.411.36
51.89p.63
84.16p.07
FWD+Mix
29.030.39
64.477..6
14.55p.16
22.79 29.799.00
52.44p.50
94.090.37
37.77a.17
70.83..11
53.24p.48
82.43p.50
FWD+ICM
39.71p.2 29
79.22. 03
21.76
42.20 12.200.09
85.27 85.27
98. 18p, 10
63.50p.47
88.92p.01
67.90..47
84.75
DM
20.91o.18
58, 28.220.24
10.16..os
21.430.09
51.28p..r
05.100.05
32 20.60..2
73.98p.25
49.46p.os
82, 82.68p.s4
+M+
30.52.
65. 65.780.22
13.27
24.95
55.78g 338
95 05.699.1
36.37,,19
78.15g.35
5-1.22p.
$2.770.37
DM+ICM
36.37o.17
78.64g.00
17.420.52
38 18..48..13
85.91 85.91..13
98. g8.677.07
66.98,.17
89.600.52
66.461.19
84.61 84.61..24
S-EXP
22.96 22
65. 65.849.23
10.130.29
24.07 10
50.29p 08
98 68p.21
35 35.62,.05
90.38g.os
51.30p.10
85, 85.23p.on
S-EXP+Mix
31.51o.18
71.72u.29
13.770.17
27.90o:25
53. 53.68p 28
98. 17.277..1
37.52
88.40g.23
53.50g.ss
84. $1.42p.21
S-EXP ICM
36. 36.700.30 30
78.86 16.886..12
16.75o 75..75.
38. 22.991..2
86. 060.37
98 81.881..s
64.46p.a
90.45o
64. 03
85. 739.20
The results show that the p-values are well below 0.001, providing strong evidence that our proposed mothod siguificantly outperforms the original Mixup. These results are summarized in Figure 4 and reported in more detail in Appendix D.5.
Moreover, conduct another analyses demonstrating that our proposed method, ICM, proves to be com- petitive approach for enhancing CLL. This is evidenced by assessment of the enhancing robustness of ICM when combining with various data augmentation techniques, ranging from weak (Flipflop, Cutout (De- Vries & Taylor, 2017)) to strong (AutoAug (Cubuk et al., 2019), RandAug (Cubuk et al., 2020)). The results in Figure 5a illustrate the significant benefits of combining ICM with various data augmentation techniques, for instance, on the CIFAR10 dataset, the combination of ICM with these augmentations achieves accuracy levels approaching 80%, far surpassing the results of their counterparts without ICM. Interestingly, Cutout appears to hurt performance when used together with ICM. A plausible explanation is that applying ICM on top of Cutout may excessively remove informative regions of the input, leading to overly distorted synthetic samples.
Furthermore, we conduct a series of analyses demonstrating that our proposed method, ICM, proves to be a competitive approach for enhancing CLL. This is evidenced by our assessment of the bias and variance of the empirical Gradient Analysis in next section. It is also crucial to highlight that the benefits of sharing new synthetic data extend beyond merely sharing complementary labels in the CLL context. This assertion is supported by an ablation study where we share new data, soft label, and hard label during the model
10

---

Published in Transactions on Machine Learning Research (01/2026)
66.31
79.06
64.79
80
75.36
Top-1 T Accuracy (%)
70.78
70.70
Top-1 Accuracy
61.17
60.57
80.05
70
New
60
With ICM
Soft Label
Without ICM
Hard Label
S-NL
S-NL+Cutout S-NL+Auto S-NL+Rand
S-NL+CCM
FWD+ICM
Methods
Methods
(a) Enhancing robustness by combining ICM with weak and strong data augmentation techniques CIFARIO.
(b) Comparison new, soft, and hard label sharing strategies under S-NL and FWD losses CIFAR1O.
Figure 5: Experimental results on CIFAR-10: (a) robust gains from combining TCM with weak and strong data augmentations; (b) performance comparison of new, soft, and hard label-sharing strategies under S-NL and FWD losses.
S-NL
S-NL+ICM
FWD
FWD+ICM
100
Top-1 Accuracy (%)
90
80
70
60
MNIST
KMNIST
FMNIST
MNIST
KMNIST MLP
FMNIST
MNIST
KMNIST Linear
FMNIST
ResNet18
Figure Comparing different model architocture with ICM mothod on MNIST family dataset under bal- anced selup.
training process. The detailed results presented in Figure 5b, In addition, we investigate methods for mitigating class imbalance CLL. We introduce Multi Intra-Cluster Mirup (MICM), which extends intra- cluster mixing to generate synthetic samples under imbalanced class distributions, thereby encouraging more effective complementary-label sharing for minority classes. Technical details of MICM and additional empirical results are provided in Appendices C and E.
Additionally, evaluate the effectiveness of our proposed method (ICM) across models of varying complex- ity, including linear classifiers, multilayer perceptrons (MLPss), and ResNet18, to examine how architectural capacity interacts with ICM. Our empirical results show that ICM consistently improves performance with ResNet18 on all three datasets (MNIST, KMNIST, and FMNIST). For MLPs and linear models, ICM yields clear gains on MNIST and KMNIST, but leads degraded performance on FMNIST. Detailed results are reported in Figure and Appendix D.6.
Taken together, these analyses motivate broader perspective the practicality of CLL. In recent years, the field has observed that CLL is still not fully practical, especially when moving from synthetic to real-world datasots and incrcasing the number of classes. We found that the current statc-of-tho-an algorithms struggle under these conditions, highlighting the need for further work to make CLL more applicable in practice (Wang et al., 2025; Ye et al., 2024). Our proposed method, ICM, introduces a novel data augmentation approach that aims make CL.L more realistic. Specifically, ICM designed mitigate the effects complementary- label noise associated with synthetic complementary samples. Through rigorous empirical evaluation, ICM demonstrates the effectiveness of encouraging complementary-label sharing among nearby examples, leading
11

---

Published in Transactions on Machine Learning Research (01/2026)
to consistent performance improvements across wide range of experimental setups. Our empirical results further show that ICM substantially improves the performance of learning models across various state-of- the-art algorithms. In particular, when we applied ICM to a real-world dataset, CLCIFARIO, the model performance increased by 10%. We hope that our work helps practitioners develop more accurate and reliable models in real-world scenarios characterized by complemeentary-label learning.
4.3 Gradient Analysis
We further discuss how the ICM framework gives such improvement by arranging the learning process via gradient analysis. This discussion centers on examining loss gradients within the experimental setup, particularly the stochastic gradient (SGD) employed in mini-batch optimization. Specifically, evaluate the bias-variance tradcoff of the gradient estimation error involving complementary gradients with ICM and the Mixup method versus the ordinary gradient. To provide more accurale assessment, utilize the bias- variance decomposition technique. Traditionally used in statistical learning to assess algorithmic complexity, we extend this framework to evaluate the estimation error of the gradient, setting the ordinary gradient as the target. We will show that our proposed framework ICM has a lower mean squared error (MSE) than the original Mixup, caused by its slight variance and bias.
Class Noise Free Intra Cluster Mixup
Mixup
6-
O Intra Class Mbxp Noise Free Intra Cluster Mixup
Original Mbxup
5- Intra Cluster Mixup
Original Moxup
5-
dr Original Mixup
Variance
4-
MSE
3-
3+
2-
2-
2-
1-
1-
0-
04
100
200
300
100
200
300
200
300
Epochs
Epochs
Epochs
(a)
(b) -CIFAROO
(c)
Variance- CIFARIO
Intra Class Mbup Noise Free
2
Intra Class Mixup Noise Free Intra Mixup
Intra Class Mixup Noise Free
Cluster Mixup
Intra Cluster Moxup
Original Mixup
Original Mixup
Original Mixup
3-
Veriance
Blag?
2-
1-0---0 8,8
D-G
0
0-
f 0-g
0
100
200
300
100
200
300
100
200
300
Epochs
Epochs
Epochs
(d) MSE-KMNIST
(e) -MMISST
(I) Variance-KMMNIST
Figure 7: Comparison of gradient estimation errors between original Mixup and Mizup Noise-Pree on MNIST and CIFAR10, using the SCL-NL loss function and ResNet18 architecture. Mivup Noise-Free demonstrates lower gradient estimation error than the original Mixup on both datascts, attributed to reduced noise inter- ference, which impacts classifier performance in CLL contexts.
We represent the gradient step determined by ordinary labeled data (x, y) and ordinary loss as f. The complementary gradient step, considering complementary labeled data (x, 77) and complementary loss or (Ø), is denoted as c. Additionally, denotes the expected gradient step of [K][,), calculated as the average of e across all possible complementary labels. This can be formalized as follows:
vl(v,g(x));
(13)
Vī(ū.g(x));
(14)
12

---

Published in Transactions on Machine Learning Research (01/2026)
b
1 K
Σ ((x)). V'78
(15)
We designate f as the ground truth, representing the target complementary estimator c. We expect the MSE of the gradient estimation to be minimal.
MSE = Ex,,, c)
(16)
We drive the bias decomposition by introducing b and climinating remaining terms:
B [ c) = B[U b-+b++4 ]
(17)
= E b) + El(b c)
(18)
Bias?
Variance
We conduct experiments to assess how well the complementary gradient e approximates the ordinary gradient f and compare it with a baseline method (original Micup). The training process is as follows:
In each epoch, compute three gradients, namely the ordinary gradient f. the current method c, and b. We evaluate the MSE, the square bias term, and the variance term using equation 16 and equation 18. Tn each epoch, we update the model only with f to ensure a fair comparison of gradients. The optimizer used was SGD with a learning rate of 10-4, and the training was conducted for 300 epochs.
The results presented Figure indicate that Mixup exhibits a higher MSE due to elevated levels of variance and bias. Conversely, ICM demonstrates significantly lower variance and bias when compared to Mixup, aligning more closely with the ideal case of Intra Class Mirup Noise Free. This supports our observation that our proposed method outperforms Mixup in CLL context by achieving lower variance and bias.
5 Conclusion
This paper presented novel data augmentation approach, ICM, specifically designs to mitigate the effects of complemenntary-laee! noise associated with synthetic complementary samples by synthesizing augmented data only within the same cluster. Through rigorous empirical evaluations across diverse CLL settings, we have demonstrated the effectiveness of encouraging complementary label sharing of nearby examples, leading to consistent performance improvements across a wide spectrum of experimental sctups, from synthotic real-world labeled datasets, in both balanced and imbalanced CLL settings. Our empirical experiments re- veal that ICM substantially enhances the performance of learning models across variety of state-of-the-an algorithms. Additionally, our investigations highlight the heightened scnsitivity of classifiers trained under CLL conditions to complementary-lan findings underscore the significant contribution of ICM to the field of CLL. By providing a data augmenta- tion strategy that effectively tackles the issue of complementary--atee noise, 1CM empowers practitioners to develop more accurate and reliable models in real-world scenarios characterized by CLL.
noise, which leads to performance degradation of CLL models. These
6 Limitation and Future Works
Despite its contributions, this study has several limitations. First, when applied to simpler models such linear classifiers and multilayer perceptrons (MLPs) on benchmark FMIST datasets, our augmentation technique yields reduced performance. This decline stems from the limited capacity of these models, which struggle to accommodate the added complexity and increased overlap in feature representations introduced by ICM. Second, we have not yet evaluated our approach in scenarios where instances carry multiple comple- mentary labels. Investigating the benefits ICM in a multi-complementary-bba learning setting remains an important direction for future work.
Broader Impact Statement
We used publicly available benchmarks, including MNIST, KMNIST, FMNIST, CIFAR10, CIFAR20, CLCI- FARI0, and CLCCIFAR20, and identified no significant ethical concerns in their use. To tackle the limited
13

---

Published in Transactions on Machine Learning Research (01/2026)
supervision inherent in these datasets, we optimized our learning algorithm to efficiently extract insights from both balanced and imbalanced class distributions. This approach is especially valuable in scientific settings where true labels are sensitive or costly to obtain. Moreover, by relying on complementary labels, we preserve data privacy and reduce annotation costs without sacrificing model accuracy.
Acknowledgement
We thank the anonymous reviewers and members of CLLab for their constructive feedback. This work is partially supported by the National Science and Technology Council in Taiwan via NSTC 113-2634- F-002-008, 114-2211EE-00--002-MM Excellence, and NTU Center for Data Intelligence via NTU-114L.00001. We thank to National Center for pigf-maefo Computing (NCHC) of National Applied Research Laboratories (NARLabs) in Taiwan for providing computational and storage resources. H.-T. Lin is honored to be supported by the Leap Fellowship of the Foundation for the Advancement of Outstanding Scholarship in Taiwan since 2025.
NTU AI Center of Rescarch Excellence within Taiwan Centers of
References
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with babel-listribution-wwarr margin loss. In Advances in neural information processing systems, volume 32, 2019. 9, 18, 20
Yuzhou Cao, Shuqi Liu, and Yitian Xu. Multi-complementary and unlabeled learning for arbitrary losses and models. Pottern Recognition, 124:108447, 2022. 2, 3, 18
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 15750 15758, 2021. 6
Xinlei Chen, Saining Xie, and Kaiming Hc. An empirical study of training self-supervised vision transformers. In IEEE/CVE international conference on computer vision, pp. 9640 9649, 2021. 23
MisinPPing Chou, Shih-Chieh Chang, Jia-Yu Yu Pan, Wei Wei, and Da Da-Cheng Juan. Remix: rebalanced mixup. European Conference on Computer Vision, pp. 95 110, 2020a. 2, 18
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, 2020b. 2, 3, 4, 8,
Tarin Clanuwat, Mikel IrizrrIrizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature, 2018.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoe V Le. Autoangment: Learning augmentation strategics from data. In IEEE/CVF Conference on Computer Vision and Pattern Recogni-
tion, pp. 113 123, 2019. 10
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In IEEE/CVF Conference on Compuler Vision and Pallern Recognition Workshops, pp. 702-703, 2020. 10
Yin Cui, Menglin Jia, Tsung-Yi Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9268 9277, 2019. 9, 18
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 248-25 2009. 8
Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. or Xio preprint 708. 778.04552.. 04552, 2017. 10
14

---

Published in Transactions on Machine Learning Research (01/2026)
Lei Feng, Takuo Kancko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple complementary labels. In International Conference on Machine Learning, 3072-3300 2020. 2, 3, 18
Yi Gao and Min-Ling Zhang. Discriminative complementary-label learning with weighted loss. In Interna- tional Conference Machine Learning, pp. 7587-3597, 2021. 9
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 770-778, 2016. 4, 9
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. In Advances in Neural Information Processing Systems, pp. 5639-5649, 2017. 2,
Takashi Ishida, Gang Niu, and Masashi Sugiyama. Binary classification from positive-confidence data. Tn Advances in Newral Information Processing Systems, volume 31, 2018. 2, 18
Takashi Ishida, Gang Niu, Aditya Menon, and Masashi Sugiyama. Complementary-labbd learning for arbi- trary losses and models. In International Conference on Machine Learning, pp. 2971 2980, 2019. 3
Liming Jiang, Bo Dai, Wayne Wu, and Chen Change Loy. Deceive d: Adaptive pseudo augmentation for gan training with limited data, In Advances in Newral Information Processing Systems, pp. 21655-21667, 2021. 2
Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In Advances in Newral Information Processing Systems, volune 15, 2002.
Yasuhiro Katsura and Masato Uchida. Bridging ordinary-label learning and complementtary-lbell learning. In Asian Conference on Machine Learning, pp. 161-176, 2020. 3
Youngdong Kim, Junho Yim, Juseung Yun, and Jummo Kim. Ninl: Negative learning for noisy labels. In IEEE/CVF International Conference on Computer Vision, pp. 101-110 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Computer Science University of Toronto, Canada, 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. Report of CS231N: Deep Learning for Computer Vision Course, 2015. Stanford University. 8
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86:2278 2324, 1998. 8
Zhixin Li and Yuheng Jia. Conmix: Contrastive mixup representation level for long- long-tailed deep clustering. In The Thirteenth International Conference on Learning Representations, 2025. 2
Wei-T Lin and Hsuan-Tien Lin. Reduction from complementary-label learning to probability estimates. Tn Pacific-Asio Conference Knowledge Discovery and Data Mining, pp. 469 481, 2023. winner of the best paper runner-up award. 2, 18
Agnieszka Mikolajezyk and Michad Grochowski. Data augmentation for improving deep learning in image
classification problem. In International Interdisciplinary PhD Workshop, pp. 117-122, 2018. 2
Madeline Navarro and Santiago Segarra. Graphmad: Graph mixup for data augmentation using data-driven convex clustering. In ICASSP 2023-2023 IEEE Internalional Conference on Acoustics, Speech and Signal Processing (ICASSP), pp- 1-5, 2023. 2
Giorgio Patrini, Alessandro Rozza, Aditya Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: loss correction approach. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1944-1952, 2017. 3
Sylvestro-Alvise Rebuffi, Sven Gowal, Dan Andrei Calian, Florian Stimberg, Olivia Wiles, and Timothy A Mann. Data augmentation can improve robustness, In Advances in Neural Information Processing Systems, pp. 01935-22944 2021. 2
15

---

Published in Transactions on Machine Learning Research (01/2026)
Jiawei Ren, Cunjun Yu, Xiao Ma, Haiyu Zhao, Shuai Yi, al. Balanced meta-softmax for long- oang-ailed visual recognition. In Advances in Neural Information Processing Systems, pp. 1175-4186, 2020. 18
Pierre H Richemond, Jean-Bastien Grill, Florent Altché, Corentin Tallec, Florian Strub, Andrew Brock, Samuel Smith, Soham De, Razvan Pascanu, Bilal Piot, et al. Byol works even without batch statistics. arXiv preprint ar Xr:::2000 10241, 2020. 23
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6:1-48, 2019. 2
Hsiu-Hsuan Wang, Mai Tan Ha, Nai-Xuan Ye, Wei-l Lin, and Hsuan- Tien Lin. CLImage: Human-annotated datasels for complementtar-llbbl learning. Transaclions on Machine Learning Research, 2025. ISSN 2835-8856. 8,
Wei Wang, Takashi Ishida, Yu-Jie Zhang, Gang Niu, and Masashi Sugiyama. Learning with complementary labels revisited: The coppeddoopppeee------eeeeee setting is more practical. In Proceedings of the 41st International Conference on Machine Learning, 2024. 2
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image datasct for benchmarking
machine learning algorithms, 2017. 8
Xiangjin Xie, Li Yangning, Wang Chen, Kai Ouyang, Zuotong Xie, and Hai-Tao Zheng. Global mixup: Eliminating ambiguity with clustering. AAAI Conference on Artificial Intelligence, volume 37, pp. 13798-13806; 2023. 2
Nai-Xuan Ye, Tan-Ha Mai, Aisiu-Hsuan Wang, Wei-l Lin, and Hsuan-Tien Lin. libell: an extendable python
toolkit for complementary--abel learning. arXiv preprint ar 0rXi:2411..2277 2024. 9, 11
Xiyu Yu, Tongliang Lin, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In European Conference on Computer Vision, pp. 68 83, 2018. 2, 3, 8, 9, 18
Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.
Zui-Hua Zhou. A brief introduction to weakly supervised learning. National Science Review, 5:44 53, 08 2017. ISSN 2095-5138. 1
16

---

Published in Transactions on Machine Learning Research (01/2026)
Appendix
A Proof
Proof. By construction, each Mixup sample is given by &,, Ax; +1- Ui.j = AUx +1 A)ū5- where view Vig a convex combination of the one-hot complementary labels ii and Fj (1,..., K}. Under the zero-one loss, ((,,g()) = Ly * g(x)], the complementary classification risk under Mixup can be written as
N
1 Rg: E) ((x,))((3..))
N
N
x + (1 - A) ((:))(()))))
=
N
N
Lii + (xx.)))
+ A)
Σ
Lūs + ((xn))
N
N
We now decompose each indicator using [A B] = 1
[[A B]. For the first sum,
N
1ys + (Xx
1
I - 1y = g(*x,))]
=
N
= =E =x,DD [T # g( ((Ri)))] Ei.
where denotes the local noise error associated with Øi (equation 3). An analogous decomposition holds
for the second sum, yielding the contribution (1 -1- A)E, from the local noise associated with Øy. Substituting these decompositions back into the expression for R' R' E) yields
R'(g; E) = A (x,)) [ * ((x,, + (1 A) (x () lū # g(Rr,)) + de; + (1 - X)ey:
which is exactly the claimed decomposition in equation 5.
B Generating Imbalanced Complementary Labels
In this section, specifically consider three situations as the primary causes of imbalanced complementary labels:
Setup 1: Imbalanced ordinary with a uniform transition matriz
In this configuration, the imbalance the ordinary distribution dataset results a corresponding imbalance in complementary labels. The ratio of imbalance in complemenaary labels significantly decreases compared to the ordinary distribution (e.g., from 100 to around 1.4) when generated using uniform transition matrix. This imbalance generation is visually represented as selup in Figure 8a.
Setup 2: Balanced ordinary with biased transition matrix
Here, a biased transition matrix arises from the imbalance in complementary labels, as depicted in (b) setup 2 Figure 8b, where complementarity probabilities vary across classes. The imbalance in complementary labels aligns with the observed imbalance ratio in the transition matrix (e.g., both being 10). This correlation underscores the direct influence of complementary label distribution the imbalance characteristics of the transition matrix in this setting.
Setup 3: Imbalanced both ordinary and biased transition matria
The imbalance in both ordinary and biased transition matrix compounds the challenge in CLL. This setup intensifics the bias complementary labels compared to the previous sctups. setup particularly chal- lenging for the model find a good classifier g due to the redeeeeeprrssntation of minority classes. Figure 8c illustrates the generation of imbalanced complementary labels in selup 3.
17

---

Published in Transactions on Machine Learning Research (01/2026)
0-
Unitorm Matrix
Dlased Paarts
Ordinary- Label Law.la Distribution
Complomentary-Loo Distribution
Ordinary- Label Distriutiin
Complementary-Lun Distribution
(a) Setup 1: Imbalanced ordinary with uniform transi- Lion matrix.
(b) Setup 2: Balanced ordinary with a biased transition matrix.
Blaee Hants
Ordinary Label Distribution
Complementary Label Distribution
(c) Setup 3: Imbalanced both ordinary and biased Lran- sition matrix.
Figure 8: Illustration of the generation of imbalanced complementary label settings.
In our proposed setup, we introduce setting of long-tailed imbolance, a concept seen in previous works (Cao et al., 2019; Cui et al., 2019). This setup is designed to generate both an imbalanced ordinary distribution and a biased transition matrix. The degree long-tailed imbalance characterized by the parameter p, which dictates class sizes through an exponentially decreasing sequence. The decreasing constant, represented as pl/K-1, precisely controls the class imbalance ratio of p. To illustrate, consider an example of long- tailetailed ordinary distribution in setup 1, visualized in Figure Sa.
C Imbalanced issue in Complementary-Label Learning
The most prevalent assumption in CLL is uniform generation, positing that complementary labels are gen- erated from ordinary labels with equal probability (Cao et al., 2022; Feng et al., 2020; Lin & Lin, 2023; Ishida et al., 2018). Another rescarch has delved into the non-uniform generation of complementary la- bels (Yu et al., 2018). However, regardless of whether the assumptions are uniform or non-uniform, existing benchmark datasets generally contain roughly balanced portions of complementary labels.
To the best of knowledge, thousands of complementary labels that are highly imbalanced? This gap in the literature motivates study, which aims to explore and develop potential methodologies for addressing the issue of imbalances in CLL datasets. Imbalanced CLL may arise due to an uneven distribution in the ordinary dataset or an imbalanced transition matrix employed for generating complementary labels. In this study, we specifically consider three situations as the primary causes of imbalanced complementary labels: selup Imbalance ordinary with a uniform transition matrix, setup Balancod ordinary with a biased transition matrix, and setup 3: Imbalance in both ordinary and a biased transition matrix. The illustration of setups in detail is depicted in Appendix B.
has explored what strategies should be adopted when dealing with
In the Mixup, the mixing factor X remains the same for synthetic x and J. However, a significant challenge in imbalanced classification is that minority classes are under-represented in the objective function, leading to poor generalization for these classes by the classifier (Cao et al., 2019; Ren et al., 2020). To address this issuc, is crucial to develop methods that enhance model lcarning for minority classes. Inspired by successful Mixup variant that enhances dass-imbalanced learning by making y not uniform (Chou et al., 2020a) and recognizing the essential need for sharing more complementary labels among minority classes.
18

---

Published in Transactions on Machine Learning Research (01/2026)
100
1.0
MICM
MNIST
80
0.9
ICM
FMNIST
KMNIST
0.8
60
Accuracy
MICM
0.7
CIFAR1O
40
0.6
CCLCIIAR110
CIFAR20
0.5
20
CLCIFAR20
0.4
20
40
60
80
100
0
1
3
4
6
9
ICM
Class
(a) Effectiveness of ICM vs MICM on different comple- mentary datasets. The figure reveals that MTCM out- performs on complex datasets like CIFAR and CLCI- more efficient on simpler
(b) Comparison of MICM vs ICM in imbalanced CLL on CIFAR10. This ablation study demonstrates that MICM not only achieves better overall performance imbalanced CLL scenarios but also significantly en- hances model learning for minority classes.
FAR, while 1CM proves datasets, such as the MNIST family.
Figure 9: The illustration of ablation study on different setups.
propose Multi Intra- Caart-r Mirup (MICM). MICM extends the mixing of samples within the same cluster when generating new synthetic data, thereby encouraging more complementary label sharing for minorily classes. To verify this hypothesis, we conducted an ablation study comparing the effects of MICM versus ICM on enhancing the learning of minority classes in imbalanced CLL. This study was performed on setup 1, with an imbalance ratio p = 10, utilizing the SCL-NL loss function and the ResNet18 architecture. The results, as shown Figure 9b, confirm that MICM improves the learning model in minority classes, thereby demonstrating its efficacy in imbalanced CL.L. In MICM, we calculate Ag based on Inverse Distance Weighting (IDW). The core concept of IDW involves determining X based on the distances among randomly selected samples in the cluster. For instance, when three samples are randomly chosen within cluster, the new sample will be generated by equation 19, then this one serves an anchor to calculate distances to the other three; the sample closer to the anchor assigned a higher weight than the farther sample. Given three examples indexed by i, j, and k; MICM constructs a mixed feature vector and a mixed label as
ii.j X1 + X2Xj + AgXi:
(19)
Jt.tk İg. Us + Ag.s Uj Ag.k Uk.
(20)
The feature-mixing coefficients (A1, A2, A3) drawn from Dirichlet distribution (A1, A2; da) Dir(a, a, a). so that A, E (0, 1] and Σ A, = 1. contrast, the label-mixing coefficients Xy.s are computed adaptively based on the distances between K. and each of the original samples:
d (Riij,k Xs)
Ag.
SE (i,
(21)
NE(Ws.)) d(xi)...x.)
SC, [1 - xs x5ll2
if | =0, otherwise,
d(Kij,bs
(22)
where d(..-) denotes the Euclidean distance, |1-112 is the lg norm, and C small constant introduced to avoid division by zero. By construction, >g.a [0, 1] and Eve Ag.s
19

---

Published in Transactions on Machine Learning Research (01/2026)
Using Algorithm 1, our proposed MICM method obtains mixed imput based equation 19, mixed labels according to equation 20, and computes Xg using equation 21, equation 22. The hyperparameter C' plays a crucial role; it is introduced to prevent a 0 value and offers flexibility in controlling the weight of Xg. Specif- ically, when is small, the weight of the anchor becomes more substantial, and conversely, when C is large, the weight of the anchor diminishes. The fine-Luning of C spectrum value provided in Paramelerization subsection.
Additional Results of Ablation Study
D.1 Comparing ICM vs. MICM in Imbalanced CLL
For imbalanced CLL, we follow (Cao et al., 2019) to generate long-tailed distribution dataset with different imbalance ratios (10, 100) ordinary datasets for selup 1. For selup use the same method as (Cao et al., 2019) to generate biased transition matrix with imbalance ratios p (3, 5, 10). In setup 3, we combine both long-tailed distributions on ordinary datasets with imbalance ratios (10, 50, 100) and a biased transition matrix with imbalance ratios (5, 10). The details of the experiment on five synthetic labeled datasets with these three setups and two real-world labeled datasets are presented next subsection.
An intriguing observation that while multiple Mixup augmentation may introduce significant noise (cons), its regularization effect (pros) may not be necessary for simpler tasks. This contrast makes the MICM method less effective than ICM on the MNIST family datasets.
However, for the more complex CIFAR datasets, the MICM method becomes preferable, as shown in Fig- ure 9a, which compares the effectiveness of ICM and MICM on different complementary datasets. In imbal- anced CLL scenarios, MICM also demonstrates superiority by more effectively enhancing learning in minority classes and improving overall model performance. Detailed results supporting this finding can be found in Figure 10b.
D.2 Quantifying Model Performance: Mixup within the Same Complementary-Label vs. Intra-Cluster Mixup
To assess the model performance of Mixup within the complementary-label and ICM, conduct experiments five datasets using setup 1. The configurations include long-tailed imbalance ratio p 100, K = 50, utilizing SCL-NL loss function, and the ResNet 18 architecture ure. The results, presented in Figure 10a, clearly demonstrate significant performance improvement with ICM compared to Mixup within the same complementary-lbbe across all five datascts. These findings validate the superiority of our proposed method, ICM, over the Mixup within the same complementarr--lbel approach.
Mixup Within CL
85.83
90
MICM
86.0585
ICM
ICM
67.80
67. 89.7967.80
Accuracy (%)
63.70
Accuracy (%)
64.9563.70
60
50.29
51.68
50-
42.55
36,21
40
39.51
26.21
32.63
30+
14.93
18.11
20
19.56,8.11
10
10
CIFAR10
CIFARZ0
MNIST Datasets
KMNIST
FMNIST
CIFAR10
CIFARZ0
MNIST Datasets
KMNIST
FMNIST
(a) Comparing ICM Mixup within the CL.
(b) Comparing ICM
MICM in iubalanced CLL.
Figure 10: Ablation study comparing proposed ICM method with other Mixup variants using the S-NL method under Setup with imbalance ratio 100 and ResNet18 architecture.
20

---

Published in Transactions on Machine Learning Research (01/2026)
D.3 Extra-Class Mixup Filter Intra-Clas Class-Class Mixup Filter under Imbalanced CLL Setting
In this section, we perform ablation study to compare the performance of models using Intra-Class Mixup Filter and Extra-Class Mixup Filter. This analysis aims to elucidate the advantages of Intra and Extra Mixup under the CLL scenario. We conduct experiments on CIFARIO dataset using setup The configurations include a long-tailed imbalance ratio p = 100, K = 50, SCL-NL loss, and the ResNet18 architecture, The results presented Table 3 demonstrate a significant superiority of Intra-Class Mixup over Extra-Class Mixup in the CLL setting.
100
80
80
S-NL+ICM
FWD+ICM
S-NL+ICM
FWD+ICM
S-NL+ICM
FWD+ICM
Accuracy (9)
Accuracy (96)
70
70
FWD
Accuracy
70
65
65
S-NL
50-
S-NL
FWD
55-
S-NL
60
40
50
55
MNIST
MNIST
MNIST
(a) Resnet18 architecture.
(b) MLP architecture.
(c) Linear architecture.
Comparing different model architectures and algorithms with ICM method on MNIST dataset under a imbalanced ratio p = 100.
Figure 11:
Table 3: Comparison of Extra-Class Mixup filter and Intra-Class Mixup filter in CLL setting with setup 1 a long-tailed imbalance (imb) ratio architecture
100, K = 50, SCL-NL loss, on CIFAR10 dataset, and ResNet18
Noise Ratio
Accuracy
Extra-Clast Mixup Filter Intra- Class Mixup Filter
0%
37. 37.17..30
0%
48.59
D.4 Parameterization
D.4.1 Fine-tuning a Hyper-paramen parameter
We conduct an ablation study to optimize the selection of the a parameter across five datasets: CIFAR10. CIFAR20, MNIST, KMNIST, and FMNIST. The study systematically explores range from 0 to 2.0 to investigate the performance of different values of The optimal values, identified based the outcomes of this study, are summarized in Table 4. Notably, the chosen values for MNIST and KMNIST remain consistent across both the beta and dirichlet distributions, while those for CIFAR10, CIFAR20, and FMNIST varied between the two distributions.
Table 4: Selected for beta distribution B(a, a) and dirichlet distribution Dir(a,a,a)
Dataset
((a.a)
Dir(a,
CIFARI0
0.4
0.2
CIFAR20
0.1
0.4
MNIST
0.1
KMNIST
0.3
0.3
FMNIST
0.1
0.4
21

---

Published in Transactions on Machine Learning Research (01/2026)
D.4.2 Fine-tuning K Cluster Hyper- parameer
Another ablation study aims to oplimize the selection of the K cluster hyper-parameter across the same five datasets. This study focuses on the S-NL+ICM method under setup with an imbalance ratio 100 and ResNet 18 architocture. The exploration spans a range from 30 to 90, and the results, presented in Figure 12, lead to the selection of K 50 for five dalasets. This choice balances performance metrics and computational efficiency, offering reasonable performance and practicality in terms of training time.
D.4.3 Fine-tuning C Constant Value
We conduct ablation study to optimize the selection of the C value across the same five datascts. This study focuses the S-NL+MICM method under selup with an imbalance ralio p 100 and ResNet18 architecture. The exploration covers range from 10 to 50, systematically assessing the performance across various values of C uses for IDW. Detailed results for different C values are presented in Figure 12. We choose for all five datasets based on its overall performance across the datasets.
MNIST
KMNIST
FMNIST
CIFAR10
CIFAR20
100
100
Accuracy (%)
Accuracy (%)
60
60
40
40
0
60
90
10
20
30
Number of Clusters (K)
Value
Figure 12: Ablation study analyzing the relationship between model performance and the number of clusters K (Ieft) and the C' value (right) across multiple datasets, using the S-NL+ICM method under setup 1 with imbalance ratio 100 and ResNet18 architecture.
D.5 Statistical Validation
In this subsection, evaluate the statistical significance of the performance improvements achieved by proposed method (ICM) over the original Mixup. We conduct experiments on CIFAR10, MNIST (synthetic complementary labels) and CLCIFAR10 (real-world complementary labels), rumning each configuration five times across several CLL algorithms, including S-NL, FWD, DM, and S-EXP. All experiments use the same hyperparameters described in the "Implementation Details" section, under both balanced and imbalanced settings. The resulting p-values are consistently well below 0.05 across setups, providing strong evidence that ICM significantly outperforms the original Mixup. The corresponding results shown in Figure 13, Figure 14, and Figure 15.
D.6 Comparison of Model Architectures
We further extend our ablation study to evaluate the effectiveness of ICM under an imbalanced setting. Specifically, we train linear models, MLPs, and ResNet18 on MNIST with an imbalance ratio of p = 100. We observe the same trend in the balanced setting: ICM consistently improves performance across all three architectures. The detailed results illustrated in Figure 11.
22

---

Published in Transactions on Machine Learning Research (01/2026)
Table 5: Effect of different encoders on 1CM under the S-NL+ICM setting on CIFARIO.
Encoders
Method
Dataset
Noise rate
Accuracy
SimSiam
S-NL+ICM
CIFAR10
3.15%
79.13%
MoCov3
S-NL+ICM CIFAR10
15.43%
60.45%
BYOL
S-NL++ICM
CIFAR10
15.96%
61.47%
D.7 Effect of Encoder Choice on ICM Performance
In the CLL setting, ordinary labels are unavailable or costly obtain. As result, the clustering induced by the encoder plays critical role in ICM: it helps reduce label noise during data augmentation. By grouping samples into clusters, encourage mixing between instances that are more likely to share the same true label. This increases the likelihood that the complemeentary-labell condition D; [K] \ holds within each cluster, thereby reducing the risk of introducing additional noise. Intuitively, the better the encoder captures the underlying class structure, the less complementary-labe noise is injected by ICM.
To investigate this, we conducted an ablation study comparing SimSiam with other self-supervised encoders, including MoCov3 (Chen et al., 2021) and BYOL (Richemond et al., 2020). We trained MoCov3 and BYOL with ResNet18 backbone CIFAR10 for 800 epochs, using the same hyperparamcters as for SimSiam, to obtain pretrained encoders. At the representation-leamiii stage (withoul labels), the pretrained models achieve reasonably good performance for all three methods. However, when we plug these encoders into ICM, SimSiam yields substantially better performance than the other two. The results under the S-NL+ICM setting on CIFAR10 are summarized in Table 5.
We further analyzed this phenomenon by explicitly computing the noise rate introduced by TCM under different encoders. The results show that MoCov3 and BYOL induce substantially higher noise rates than SimSiam, which explains their lower accuracy when used within our framework. These findings indicate that ICM is indeed sensitive to the encoder, and that in our current implementation SimSiam provides the most suitable representations for reducing complementary-labe noisc and achieving strong performance.
E
Additional Results of the Experiments
In this section, we conduct additional experiments to cover the remaining datasets CIFAR1O, CIFAR20 of setup and all remaining imbalance types from setup 2 to setup 3. Tables 6 and 7 present the results for setup 2 with imbalance ratios (biased transition matrix) = (3, 5, 10), while Tables and 9 report the results for setup 3, which combines a biased transition matrix = (5, 10) with an ordinary imbalance distribution p = (10, 50, 100). These findings consistently affirm that our proposed method outperforms other approaches, demonstrating superiority with SCL-NL, SCL-EXP, FWD-INT and DM loss functions across various imbalance settings.
Based on these experimental results, we propose utilizing ICM for simpler vision datasets such as MNIST, KMNIST, and FMNIST. For more complex vision datasets, including CIFAR10, CLCIFARIO, CIFAR20, and CLCIFAR20, MICM method is proferable to enhance the performance of the trained classifier.
23

---

Published in Transactions on Machine Learning Research (01/2026)
80
p-value: 0.00000003
p-value: 0.00000032
80
p-value: 0.00000416
p-value: 0.00000012
54
56
78
T0p-1 Accuracy 89
76
P--- Accuracy (%)
52
Accuracy (%)
78
Top-1 Accuracy (%)
54
52
74
50
76
50
72
CIFAR10
48
CLCIFAR10
CIFARIO
CLCIFAR10
74
48
70-
46
68
44
72
44
66
42
42
64
40
40
Mixup
ICM
Mixup
ICM
Mixup
ICM
Mixup
ICM
(a) DM algorithm.
(b) S-EXP algorithm.
Figure 13: Comparing the p-value of different between Mixup and ICM method on CIFARIO and CLCIFARIO with DM (right) and S-EXP (Ieft) algorithms on both balanced and imbalanced (o 100) scenarios.
44
p-value: 0.00001010
p-value: 0.00001889
42
p-value: 0.00015633
42
p-value: 0.00052150
42
Top-1 Accuracy (%)
40
Top-1 Accuracy (%)
Top-1 Accuracy (%)
38
Accuracy
38
38
S-NL
36
FWD
DW
S-EX
36
34
34
32
34
32
30
28
Mixup
Mixup
ICM
Mixup
ICM
Mixup
ICM
Figure 14: Comparing the p-value of different between Mixup and ICM method on CIFAR10 datasel under imbalanced ratio 100 with different algorithms.
100
100
100
p p-value: 0.00006435
95
p-value: 0.00000001
p-value: 0.00003631
96
p-value: 0.00000001
99
90
90
Top-1 Accuracy (%)
Top-1 Accuracy (%)
99
85
98
Top-1 Accuracy
Top-1 Accuracy
80
78
97
BALANCED
75
IMBALANCED
BALANCED
72
IMBALANCED
66
54
94
48
Mixup
ICM
Mixup
ICM
Mixup
ICM
Mixup
ICM
(a) S-NL algorithm.
(b) FWD algorithm.
Figure 15: Comparing the vavalue of different between Mixup and ICM method on MNIST dataset with S-NL (right) and FWD (left) algorithms both balanced and imbalanced (p 100) scenarios.
24

---

Published in Transactions on Machine Learning Research (01/2026)
Table 6: Top-1 validation accuracy (%) setup 2 with biased transition ratio {3,5, K = 50, using
S-NL, FWD, DM, and S-EXP losses on ResNet18 architecture
Dataset
CIFAR10
CIFAR20
Method
p 10
p=
==
10
5
p 3
S-NL
15.49..24
19.08p.27
22.10p.30
6.70p.20
7.090.39
8.16p.26
M-XL++Mix
20.74g.
28.03g.32
33.71p.38
7.24p.36
9.83p.27
10.49b.45
S-NL+ICM
24.68p.42
33.97p.17
40.57g.45
7.36p.31
10.25p.25
10.65p.34
M-NL+MICM
26. 26.16
34.96g.31
42.66g.36
8.73p.27
11.97g.39
14.81g.23
FWD
57.57
58.82p.47
60.80p.40
21.81
21.63g.24
22.12p.29
FWD+
64.10p.39
65.05g.49
64.9/1..s
19.38p.37
22.03g.39
21.211..8
FWD+ICM
78.97
78.74p.47
78.70p.65
35.53p.43
37.34p.51
39.43g.55
MWD+MICM
80.00o.53
80.61g.36
80.70g.63
42.82..6
45.70g.37
45.670.52
DM
15.30
16.04g.33
18.69p.32
6.13p.17
6.32p.34
6.81p.33
DM+Mix
26.15..0
29.89p.28
33.28p.52
6.60p.19
8,171.36
9.78p.35
DM+ICM
29.78p.0a
36.94g.21
39.24g.14
7.06p.12
8.53p.21
10.16p.25
DM4MICM
31.06g.c0
39.470.12
41.40p.21
8.040.16
10.68g.24
13.84..21
EXP
15.52..31
18.51g.2
21.79p.25
6.44p.21
7.00p.23
7.39p.24
S-EXP+Mix
20.99
27.40p.27
31.06p.56
7.94p.43
9.37p.67
11.18p.37
S-EXP+ICM
24.30p.06
33.45p.20
40.36p.22
7.03p.27
10.149.14
10.56p.03
S S-EX+MMIMM
25. 25.34..08
34.35o.1.
41.560.19
8.27o.10
10.68a.12
14.44a.0
Table 7: Top-1 validation accuracy (%) on setup 2 with biased transition imbalance ratio K = 50, using S-NL, FWD, DM, and S-EXP losses with ResNet18 architecture
(3, (3,5,1 10).
Dataset
MNIST
KMNIST
FMNIST
Method
10
5=
10
p=
p 10
p=
S-NL
57. 57.19..se
66.47
28.70p.44
41.41g.36
46.88p.54
67.73p.32
S-NL+MMix
35.77..37
53.30p.35
23.42p.47
31.40p.45
34.95p.u
48.370.36
S-NL+ICM
77.27p.72
97.99
54.84p.42
65.37
50.00p.39
64.06p.62
S-NL+MICM
05.670.50
96.99p.63
63.199.39
64.11p.48
54.98a.57
67 67.28..62
FWD
93.00g.41
94.46g.59
65.67p.54
73.97p.37
80.60p.42
83.51p.58
FWD+Mix
88.70p.37
92.29p.48
63.88p.43
68.30p.39
78.37
80.13p.31
FWD+ICM
98. 18.150.45
98.21 18.21g.35
88.00 $8.099.68
87.75
85.9 85.95
85.80g
FWD+MICM
98.00g.42
98.08g.78
86.87p.37
87,50p.41
85.02p.23
85.48p.57
DM
16.95g.32
70.38p.30
27.84p.41
32.71p.31
43.57o.39
54.030.42
DM+Mix
35.39p.34
50.74p.36
26.06p.52
29.270.58
39.56p.54
45.90p.99
DM+ICM
86.96p.12
97.01o.11
63.65..23
65.46..21
52.42p.18
70.61g.08
DM4MICM
92.99h.14
94.855p.15
58.24p.21
60.43p.17
59.455.11
68. 68.25p.12
EXX
57. 29.25
65.849.24
18.719.41
41.88p.43
46.08p.52
56.65 56.65p.34
SMiP+Mix
27.91..43
36.71 p.45
22.16p.49
32.02p.72
43.95p.m
40.44p.56
S-EXP+ICM
10.11
97.70p.19
54.26p.18
66.80
48.21
63.32p.21
S-EXP+MICN
87. 87.12
97. 97.92..1
62.49,
64.55p.18
56.38
66.47a.15
25

---

Published in Transactions on Machine Learning Research (01/2026)
Table 8: Top-1 validation accuracy (%) on selup 3 combining biased transition ratio Pi = 5 and long-tailed imbalance P2 = (10, 50, 100), K = 50, using S-NL, FWD, DM, S-EXP losses and ResNet18.
Dataset
MNIST
CIFAR10
Method Pr: P2
5, 100
5,50
5, 10
5. 100
5,50
5, 10
S-NL
39.18
41.49
51.760.58
16. 16.16
14.84g.37
12.96g.36
M-NL+-Mix
37.38 37.380.35
37.89o.37
47.900.39
16.00o.48
15.39p.38
17.150.46
S-NL+ICM
89.44o.43
94.55%
97.4 97.41p.42
18.89..49
21.00g.38
19.81o.45
S-NL+MICM
90.08e.46
93.72p.51
96.80p.36
20.98
22.87p.42
32.78p.64
FWD
47.930.34
54.02p.42
64.030.30
22.180.56
23.670.47
23.94o.31
FWD+Mix
46.98o.31
51.230.43
67.42o.48
30.20o.48
29.770.43
38.680.45
FWD+ICM
85.3 85.34p.44
93.91g.41
97.15p.53
37. 37.74g.36
40.340.51
64.060.42
MICM
83.499.41
91.69o.49
95.790.37
40.78g.43
43.71p.39
65.33p.37
DM
36.91
36.25p.51
48.570.39
14.04p.41
14.62
14.40
DM+Mix
34.85p.32
40.68p.29
46.62h.43
18. 18.26n.38
19.36n.54
18.37a.72
DM+ICM
88.13p.12
91.38p.21
96. 75..55
21.177.13
22.430.07
32.550.09
DM+MICM
81.660.23
84.98p.15
92.730.11
22.48p.17
23.95p.16
32.61g.10
S-EXP
40.57
40.46p.35
44.79h.30
15.68p.38
14.45
12.80p.36
S-EXP+Mix
34.52o.41
36.08p.43
42.28o.52
15.5 15.58o.45
14.13p.57
16.58p.51
S-EXP+ICM
80.52p.09
84.18p.13
98.13.11
18.25p.20
19.78p.17
20.30p.16
S-EXP+MICM
$3.170.10
85.11o.21
97.82o.05
19. 19.260.19
20.43o.11
31.32p.29
Table 9: Top-1 validation accuracy (%) on setup 3 combining biased transition ratio /1 10 and long-tailed imbalance P2 = (10, 50, 100), with K 50, using S-NL, FWD, DM, S-EXP losses and ResNet18 architecture
Dataset
MNIST
CIFAR10
Method PL: P2
10, 100
10,50
10, 10
10, 100
10,50
10, 10
S-NL
38.01o.40
41.19p.38
43.52p.42
11.60p.41
11.58p.53
11.82a.32
M-NL+Mix
33. 33..3
31.36p.36
32.22o.51
12.7 12.750.47
13.88
15. 15.680.57
S-NL+ICM
79.74p.73
84.05p.46
97.15p.53
16. 16.11
13.39h.49
14.55n.32
S-NL+MICM
71.070.37
84.150.36
96.630.43
16.85o.49
18.90o.42
16.93p.51
FWD
38.480.34
40.04p.53
62.91o.38
23.36g.27
22.440.54
23.77o.42
Mix
47.35
47.98p.43
60.35g.56
29.63g.a6
31.75g.45
36.85g.52
FWD+ICM
84.13p.
90.95
96.72p.7
37.0 37.01o.s
43. 43.160.64
62.88o.33
FIC+
80.74p.63
87.63p.46
95.45n.46
38.02p.42
46.17p.52
63.81p.45
DM
31.01p.27
32.38o.46
42.98o.29
15.98u.45
13.730.a7
13.02a.22
MM+
26.42p.as
33.11p.35
37.510.43
14.32a.56
14.590.39
13.94g.34
DM+ICM
78.63 78.63p.13
86.05p.11
95.82p.17
17.6 17.62..07
19.45o.18
14.19
DM4MICM
73.32o.09
80.54p.18
90.89h.12
19.35p.07
20.86p.16
17.44b.10
S-EXP
37.830.43
40.84p.52
44.72o.36
11.61p.41
11.899.48
14.55a.37
M-X
33.59h.43
33. 33.12p.34
33.85p.38
12. 12.170.31
12.71
15.82..66
S-EXP+ICM
73.06p.06
76. 76.24p.00
79.23o.10
15.770.15
14.01g.19
17.38a.12
M-CXP+MICM
71.28p.0s
76.1 76.18p.11
79.27o.12
16.71p.09
16.30p.13
20.26
26


Reviews:
[{"review_id": "7QzCvI26NL", "reviewer": "Reviewer_X2Lh", "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": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 present several ideas:\n - analyzing why regular mixup do not work so well on complementary label learning (mostly attributing this to label noise)\n - propose a method to adress shortcomings found, where mixup is only done within feature based clusters \n - show that this method provides improved performance on some tasks, compared to regular mixup (higher top1 accuracy on CLCIFAR 10 and 20)\n- provide evidence that this is due to lower noise. through a gradient analysis", "claims_and_evidence_yn": "No", "claims_explanation": "The basic idea is simple enough; do clustering of the data in feature space, and when training do mixup within each cluster only. Figure 2 conveys this idea well. From basic ideas about label noise (as given in page 4, *\"Specifically, it is critical to minimize instances where $\\bar{y}_i = y_j \\vee \\bar{y}_j = y_i$, as such occurences increase the error term $\\varepsilon$ in equation 4*) this all makes sense. Table 2 shows that this method also provides improved performance. This far, all is good. \n\nThere are a couple of shortcomings, however. Mostly related to the presentation rather than the scientific content. This makes the paper hard to follow in some areas. \n\n1) **Related works**. There are research on clustering methods applied in normal classification learning, and this is not acknowledged in the paper. One quick example I find after 2 minutes of searching online is https://aclanthology.org/2022.coling-1.333.pdf which has ideas very close to yours. This makes it hard to position the findings within the exiting litterature, and understand if this method is particular to complementary label learning, or if any mixup application would benefit from it.\n2) **Undefined quntities**. The 'Noise Ratio' of Figure 1a (called Noisy Ratio in Figure 3) is not clearly defined. The variables $\\varepsilon_i$ in equation (4) are not defined. The Iverson-style bracket notation used in equations 1-4 should be properly defined, since you use normal brackets in equation 15-17. The parameter $\\rho$ that describes class imbalance is not defined. The 'Mixup Noise Free' method referenced in figure 1 and other places is not defined clearly. Was that a previous name for the ICM method?\n3) **Notation**. $f$ is a classifier in section 2.1, and $g$ is a score function. In equation 1-4 it seems $g$ is the classifier. It is called 'model' in Definition 2. On page 6 you tell us that $\\lambda_x = \\lambda_\\bar{y}$ so why use to different symbols if they are the same anyways? In algorithm 1, line 12-14 has roman lowercase numbered steps. Why not use that for line 10, 11 and 15? In equations 7 and 8, $g$ has a subscript $\\theta$ tha is never used elsewhere.\n4) **Unclear findings**. In figure 4a, cutout seems to hurt the performance of ICM. This is interesting and should be commented on somewhere. it was surprising to me. In section 6 you mention how ICM works with linear models and MLPs, but you have not presented any findings on this in the main text.", "audience_yn": "Yes", "audience_explanation": "Several application fields have high costs for aquiring data, such as the medical field. Producing labels is associated with costs, which leads to the idea of complementary label learning. Unfortunately, exactly such areas are also plagued with high costs for aquiring the unlabelled data as well (cases that needs biological samples, rare disease occurring etc), and this leads to need for data augmentation techniques. The authors seem to have made progress on the problem of combining these ideas.\n\nThe ideas of bias-variance decomposition of gradient esstimation is also an interesting idea and to me a novel one. This is also methodologicaly relevant.", "requested_changes": "Critical changes:\n\n1. Ensure that all notation is consistent and that all quantities are defined.\n2. Discuss embedding based selective mixup in general (not only complementary label learning()\n\nNon-critical changes:\n\n3. I think you should work through the whole paper to ensure it is coherent. Ensure notational consistency throughout. Make sure that things are named properly and consistently between body text and figures/tables. Combine section 3.2 and 3.3 into one section so they work together as a whole. Place Figure 2 earlier in the article so the reader has the main message with them while reading the rest. \n4. I think it would be very interesting to add a showcase of ICM on a regular classification problem, not only complementary labels.", "broader_impact_concerns": "I have no concerns of this sort.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bAJq3GcI4y", "reviewer": "Reviewer_eSLP", "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": "", "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": "This paper addresses the problem of data augmentation in Complementary-Label Learning (CLL), a setting where models are trained using labels that specify what a sample is not. The authors first demonstrate that the standard Mixup technique may be detrimental in CLL, as it introduces \"complementary-label noise\" that violates the CLL assumptions. To address this, they propose a two-stage method called Intra-Cluster Mixup (ICM). First, an offline step uses a pretrained self-supervised encoder to generate feature embeddings, which are then grouped using k-means clustering. Second, an online step applies Mixup only to pairs of samples drawn from within the same cluster. This strategy is designed for intra-class mixing, thereby reducing label noise. The empirical results show that ICM consistently improves the performance of several state-of-the-art CLL loss functions on various datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "1. The paper provides an experiment shown in Figure 1 demonstrating motivation clearly: that standard Mixup performs poorly, but an \"oracle\" version, Mixup Noise Free, is beneficial. This supports the claim that the noise introduced by Mixup is the specific cause of the performance degradation.\n2. Empirical results on multiple datasets with both imbalanced and balanced cases show consistent improvement brought by ICM.\n3. Table 2 shows ICM can be incorporated into several loss functions.\n4. Gradient analysis gives further evidence.", "audience_yn": "Yes", "audience_explanation": "It's interesting to introduce data augmentation methods into Complementary-Label Learning.", "requested_changes": "1. I find that an additional method, MICM, is presented in the supplement as a superior method for complex and imbalanced datasets. Please clarify its existence and relationship to ICM in the main paper.\n2. Would the performance of ICM be affected by different encoders? Do you try other encoders rather than SimSiam?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MLTm9h1tWB", "reviewer": "Reviewer_NCsq", "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": "", "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": "In real-world scenarios, collecting high-quality labeled datasets is often difficult or even impossible. This paper introduces Intra-Cluster Mixup (ICM), which applies the Mixup method within samples belonging to the same cluster in the context of Complementary-Label Learning (CLL). As a result, the Mixup-induced label noise is significantly reduced from 16.24% to 0.95%. The authors also propose a Surrogate Complementary Loss (SCL) to minimize the likelihood associated with complementary labels, further improving model performance. Experiments were conducted on two CIFAR datasets, three MNIST variants, and two CLCIFAR datasets. The results show that ICM consistently improves performance across all datasets under both balanced and imbalanced settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Strenghts\n* The paper shows that ICM reduces this noise to 0.95%, verifying the mechanism behind the claimed improvement.\n* Results across five synthetic datasets (CIFAR10, CIFAR20, MNIST, KMNIST, FMNIST) and two human-labeled datasets (CLCIFAR10, CLCIFAR20) consistently show performance gains across multiple complementary loss functions (SCL-NL, FWD, DM, EXP).\n\nWeaknesses\n* The performance improvement is clear, but the statistical significance (such as p-values) is not explicitly reported.\n* The human-labeled datasets (CLCIFAR10 and CLCIFAR20) show relatively low accuracies, which might raise questions about the practical relevance.", "audience_yn": "Yes", "audience_explanation": "The findings are likely to interest researchers in weakly supervised learning, noisy label learning, and data augmentation.\nThis paper explores the reasons why Complementary-Label Learning (CLL) often fails. Although the proposed ICM does not achieve state-of-the-art performance, the authors clearly demonstrate that it improves model performance. These findings provide meaningful insights for addressing related challenges in areas such as semi-supervised learning, noisy-label learning, and class-imbalance learning.", "requested_changes": "1. Add statistical validation for the reported performance improvements. Presenting only the mean and standard deviation values is insufficient to determine whether the improvements are statistically significant.\n2. Some datasets show relatively low accuracies, especially the human-labeled ones. It would be helpful for the authors to discuss how ICM could be applied or scaled to more practical scenarios and real-world settings.\n3. Some tables (e.g., Table 2) are difficult to read due to the small text size. It could be more readable by splitting them into two smaller tables or enlarging the font size.", "broader_impact_concerns": "No concerns.", "additional_comments": "No comments.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)