Complementary-label learning (CLL) trains a classifier from labels that name a class an instance does not belong to. Such labels are cheap to collect from crowdworkers or vision-language models (VLMs), making them attractive for large-scale annotation. However, both sources can mistakenly assign the true class as the complementary label. Such annotation errors are particularly harmful in CLL because the model is explicitly trained to suppress the correct answer. Optimal transport (OT) data valuation identifies harmful samples by comparing training data with a clean validation set, but transferring it directly to CLL creates a semantic mismatch: label c means not class c in the training but class c in the validation. We show that this makes the OT label groups noisy mixtures whose behavior depends on the noise rate. The transferred score is informative only at sufficiently high noise, becomes uninformative at the crossover rate 1/M for M classes, and reverses below it, where practical CLL annotation typically operates. We propose CAVA, which introduces a complementary label cost and a label margin that isolates the contribution of each complementary label to the transport potential. The margin keeps a consistent direction across noise rates, detects diagonal noise with a parameter-free threshold of closed-form precision, and allows detected samples to be recycled as ordinary-label supervision. On synthetic and human-annotated benchmarks, CAVA separates diagonal noise almost perfectly where directly transferred OT valuation performs worse than random. With only a fraction of the clean validation data, it also improves every CLL objective we evaluate, showing that OT-based valuation becomes reliable once the semantics of complementary supervision are modeled explicitly.
Figures & tables
Figure 1: Overview of CAVA. The pool is split into tasks, and each task is matched to a clean validation set by entropic OT with the complementary label cost. Each sample is scored by its label margin; samples with a negative margin are flagged as diagonal noise and then removed or recycled.
Figure 2: From TW-LAVA to CAVA. Left : TW-LAVA compares noisy label groups with clean classes, so its label weight λyα(η) changes sign at η=1/M and the noise switches sides (Theorem 1 ). Right : CAVA compares clean classes only, so the sign of its margin is fixed: negative exactly when the given label is the most likely class under the transport posterior (Theorem 2 ). Scores are measured on CIFAR-10 ( η=25% , top) and CLCIFAR-10 (bottom).
Figure 3: The label margin. The image looks like class A, so it is cheap to transport under label A and costly under B or C. The bars show fi(c) , and the margin si compares the given label (solid bar) with the cheapest other label. Given A, si<0 and the sample is flagged as diagonal noise; given B, si>0 and the label is valid.
Synthetic ( η=25% )
Real-world
Method
Selection
MNIST
CIFAR-10
CIFAR-20
CLCIFAR-10
CLCIFAR-20
CLMIN-10
CLMIN-20
(a) Selection only: SCL-NL on the retained pool, Eq. ( 3.13 )
No pruning
–
0.14 ± 0.09
1.19 ± 0.02
0.49 ± 0.10
42.36 ± 0.91
7.71 ± 0.08
14.89 ± 1.02
4.55 ± 1.18
TW-LAVA
Fixed p
98.21 ± 0.29
76.04 ± 0.25
14.43 ± 1.00
47.46 ± 0.17
6.90 ± 0.11
12.56 ± 0.84
4.28 ± 0.35
CAVA (ours)
Fixed p
99.20 ± 0.10
79.26 ± 0.25
17.70 ± 1.38
79.63 ± 0.33
10.78 ± 1.25
27.44 ± 2.69
10.39 ± 0.67
CAVA (ours)
Adaptive cut
99.47 ± 0.04
79.12 ± 0.13
12.54 ± 2.68
80.00 ± 0.59
10.27 ± 1.15
27.44 ± 1.84
9.56 ± 1.13
Table 1: Main results: test accuracy (%) with AutoAugment. All methods score the pool against the same 2,000 validation images ( 20 per class on CLMIN), and accuracy is measured after the final epoch on the remaining test images. The fixed cut removes p=25% of each task on the synthetic datasets and 5% ( 3% on CLCIFAR-20) on the human-labeled ones; the adaptive cut removes every sample with si≤0 and needs no ratio. Mean ± std over three seeds; best per column and block in bold .
Method
Valuation scope
Label cost
Score
LAVA [ 16 ]
full set ( ≤ 20K)
noisy-group
calibrated
TW-LAVA
task-wise, all data
noisy-group
calibrated
CAVA (ours)
task-wise, all data
complementary
label margin
Table 2: The three OT valuation methods compared in this paper. TW-LAVA differs from LAVA only in the task-wise decomposition; CAVA differs from TW-LAVA only in the label cost and the score.
Figure 4: Real-world complementary labels. (a) Score distributions: under TW-LAVA (top), annotation errors overlap with valid labels and sit on the wrong side; under CAVA (bottom), they separate on the low side. (b) Test accuracy of TW-LAVA and CAVA at the fixed cut of Table 1 ( 5% on CLCIFAR-10, 3% on CLCIFAR-20) and of CAVA with the adaptive cut, mean of three seeds; all use the same 2,000 validation images.
Figure 5: Scale and the value of clean labels. (a) CIFAR-10-1M ( η=25% , SCL-NL): test accuracy after every epoch against time (valuation plus training, measured on one dedicated GPU), each method at its best cut (CAVA p=25% , TW-LAVA p=35% ), for the 20-epoch and the 200-epoch schedule. Shaded: the valuation of TW-LAVA, so its training starts only after 2.5 hours (dashed line); CAVA needs about 4 minutes. All cuts are in Table 23 . (b) Supervised CE trained from scratch on n clean labels (three seeds) against CAVA, which uses 2,000 clean labels only as its validation set ( η=25% ); CAVA uses the supervised embedder of the main tables, and results on other fixed representations are in Table 21 .
Figure 6: Small noise ratios. Final-epoch test accuracy (held-out test images) of SCL-NL on the retained pool against the pruning ratio p , on CIFAR-10 with small diagonal-noise ratios η ; CAVA, TW-LAVA, and no pruning are means over three seeds, the other baselines single runs (seed 1126); same validation set for all methods; TW-LAVA keeps its original OT settings here (Appendix C.2 ). Each baseline is used as published, keeping its highest-valued or lowest-loss samples. The dashed line trains on the full pool.
Figure 7: Beyond CIFAR. Test accuracy with recycling (CE+SCL-NL) on FOOD15 (Food-101 [ 1 ] ), RESISC45-20 (NWPU-RESISC45 [ 2 ] ), and Places365-10 (Places365 [ 41 ] ) with synthetic diagonal noise; protocol of Table 1 , fixed cut p=η , seed 1126. All rows, including selection only, are in Table 18 .
Appendix figures & tables34 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 8: Complementary-label noise in CLL. When the complementary label coincides with the true label, i.e., yˉi=yi , the empirical transition matrix contains diagonal mass, creating contradictory exclusion constraints.
Symbol
Meaning
X,Y={1,…,M}
Input space and label space of M classes
Dˉ={(xi,yˉi)}i=1N , yi
Pool with given labels, and the unobserved true labels
N={i:yˉi=yi} , η=P(yˉ=y)
Diagonal-noise set and noise rate
Dv={(xjv,yjv)}j=1Nv
Clean validation set with ordinary labels
It , T
Task t (a subset of the pool) and the number of tasks
ϕ , Cfeat
Fixed feature extractor and feature cost (Eq. ( 3.2 ))
Appendix
Table 3: Notation.
Figure 9: The direction flip, measured. Detector AUC against η on CIFAR-10; both scores use the same features, εOT=0.01 , λy=1 , and the same Nv=2,000 validation images. An AUC of 0.5 is chance. The noisy-group label cost is at chance exactly at the blind spot η=1/M (orange) predicted by Theorem 1 , and below chance for smaller η , where it ranks the noise in the wrong direction. The complementary label cost stays at the top for every η . Stars: human-labeled CLCIFAR-10 ( 3.98% errors).
Metric
Definition
What it measures
CE Precision
∣Irec∩Inoise∣/∣Irec∣
recycled labels that are correct ordinary labels
CE Recall
∣Irec∩Inoise∣/∣Inoise∣
diagonal noise recovered into the CE branch
F1
harmonic mean of the two
balance between precision and recall
CE Contam.
1−CE Precision
wrong ordinary labels in the CE branch
CLL Contam.
∣Ikeep∩Inoise∣/∣Ikeep∣
diagonal noise left in the complementary-label branch
Appendix
Table 4: Branch-quality metrics. Higher is better for precision, recall, and F1; lower is better for the two contamination rates.
Figure 10: Detection of diagonal noise. Detection AUC of each score in its natural direction; the synthetic datasets are shown at η=5% and 15% , around the crossover 1/M ( 10% for CIFAR-10, 5% for CIFAR-20). The gray dashed line marks chance ( 0.5 ): a bar below it ranks the noise above valid data, and bars with an AUC near 0 show their value.
CIFAR-10
CIFAR-20
CLCIFAR-10
CLCIFAR-20
Noise rate η
25%
15%
5%
25%
15%
5%
3.98%
2.32%
KNN-Shapley
0.000
0.000
0.000
0.002
0.003
0.005
0.000
0.004
Data-OOB
0.000
0.001
1.000
0.002
0.006
0.506
0.965
0.869
Small-loss
0.217
0.338
0.614
0.313
0.354
0.509
0.787
0.603
TW-LAVA
0.995
0.906
0.041
0.940
0.852
0.447
0.072
0.156
CAVA (ours)
1.000
1.000
1.000
0.997
0.998
0.999
1.000
0.999
Appendix
Table 5: Detection AUC of diagonal noise in the natural direction of each score (valid samples high; 0.5 is chance, values near 0 rank the noise as the most valuable data). Same pool and tasks for every method (seed 1126 ).
CAVA (ours)
Features
Dataset
AUC
adaptive cut P / R
w=0
TW-LAVA
CLIP
MNIST
0.990
96.7 / 88.5
–
0.771
CIFAR-10
0.994
96.6 / 88.1
0.992
0.773
CIFAR-20
0.971
94.5 / 66.3
0.969
0.711
CLCIFAR-10
0.996
87.1 / 86.4
0.995
0.758
CLCIFAR-20
0.981
75.4 / 59.6
0.976
0.621
Appendix
Table 6: Detection of diagonal noise on two representations that have never seen a label of the pool (seed 1126 , all five tasks). AUC treats valid samples as positive; “adaptive cut” gives the precision and recall of {si≤0} , and “ w=0 ” is the CAVA margin without the validation potential. The supervised embedder of the main tables is shown for reference; “–”: not run.
Noisy-group cost
Complementary cost
Dataset
η
calibrated (TW-LAVA)
margin
calibrated
margin (CAVA)
CIFAR-10
2%
0.342
0.041
0.983
0.995
5%
0.400
0.063
0.981
0.995
10%
0.503
0.508
0.979
0.994
15%
0.610
0.952
0.977
0.994
25%
0.773
0.982
0.974
0.994
Appendix
Table 7: Detection AUC of the four combinations of label cost and score on CLIP features (seed 1126 , Nv=2,000 ) against the noise rate; the crossover is η=1/M . The supervised embedder gives the same pattern (Figure 9 ).
Dataset
e^
η^
η
π^ (%)
measured (%)
recall (%)
MNIST
0.093
0.244
0.250
96.6
96.7
88.5
CIFAR-10
0.107
0.245
0.250
96.1
96.6
88.1
CIFAR-20
0.304
0.234
0.250
93.0
94.5
66.3
CLCIFAR-10
0.104
0.032
0.040
71.7
87.1
86.4
CLCIFAR-20
0.285
0.005
0.023
18.6
75.4
59.6
CLMIN-10
0.248
0.026
0.048
42.4
73.0
70.8
Appendix
Table 8: Estimating the precision of the adaptive cut without true labels (CLIP features, seed 1126 ): leave-one-out error e^ of the posterior classifier, estimated noise rate η^ , and estimated precision π^ (Eq. ( 3.15 )), next to the measured precision and recall.
MNIST
CIFAR-10
CIFAR-20
CLCIFAR-10
CLCIFAR-20
CLMIN-10
CLMIN-20
(a) Selection only: SCL-NL on the retained pool
CLIP
TW-LAVA
Fixed p
26.25 ± 1.31
8.41 ± 1.86
3.10 ± 0.31
42.79 ± 1.79
7.69 ± 0.08
15.22 ± 2.17
4.50 ± 0.17
CLIP
CAVA (ours)
Fixed p
90.59 ± 0.21
74.11 ± 0.32
12.05 ± 1.05
79.06 ± 0.67
10.64 ± 0.89
27.11 ± 1.90
10.66 ± 0.76
CLIP
CAVA (ours)
Adaptive cut
84.58 ± 0.35
64.19 ± 3.36
7.01 ± 1.74
77.94 ± 0.43
8.48 ± 0.11
25.11 ± 4.43
7.83 ± 2.92
validation only
TW-LAVA
Fixed p
97.91 ± 0.10
29.90 ± 2.29
2.71 ± 0.12
43.43 ± 0.72
7.68 ± 0.15
16.22 ± 3.02
4.39 ± 0.59
validation only
CAVA (ours)
Fixed p
98.83 ± 0.06
66.25 ± 0.31
18.57 ± 1.40
73.33 ± 0.08
10.41 ± 1.77
21.56 ± 2.52
12.83 ± 0.67
Appendix
Table 9: Test accuracy (%) of Table 1 on CLIP features and on the validation-only features (mean ± std over seeds 1126, 42, 2023). Best per column, block and representation in bold .
Selection
CIFAR-10
CIFAR-20
CLCIFAR-10
CLCIFAR-20
CLMIN-10
(a) Selection only: SCL-NL on the retained pool
TW-LAVA
Fixed p
8.41 ± 1.86
3.10 ± 0.31
42.79 ± 1.79
7.69 ± 0.08
15.22 ± 2.17
CAVA (ours)
Fixed p
74.11 ± 0.32
12.05 ± 1.05
79.06 ± 0.67
10.64 ± 0.89
27.11 ± 1.90
CAVA (ours)
Adaptive cut
64.19 ± 3.36
7.01 ± 1.74
77.94 ± 0.43
8.48 ± 0.11
25.11 ± 4.43
CAVA, w=0
Fixed p
73.20 ± 0.06
13.98 ± 0.81
78.27 ± 0.37
8.75 ± 0.16
25.44 ± 2.14
CAVA, w=0
Adaptive cut
64.29 ± 0.65
8.77 ± 0.51
76.96 ± 0.88
9.39 ± 1.01
29.00 ± 1.76
Appendix
Table 10: Training on the selections of Table 6 with CLIP features (cuts of Table 1 ; mean ± std over three seeds). “ w=0 ” is the CAVA margin without the validation potential. Best per column and block in bold .
CIFAR-10 ( η=25% )
CLCIFAR-10 ( η=3.98% )
Label cost
Score
SCL-NL
CE+SCL-NL
SCL-NL
CE+SCL-NL
noisy-group
calibrated (TW-LAVA)
8.41 ± 1.86
46.68 ± 0.58
42.79 ± 1.79
28.18 ± 2.10
noisy-group
margin
67.57 ± 1.31
85.46 ± 0.08
41.21 ± 4.00
31.08 ± 1.89
complementary
calibrated
58.79 ± 2.12
80.81 ± 0.32
71.42 ± 0.16
73.26 ± 0.49
complementary
margin (CAVA)
74.11 ± 0.32
87.91 ± 0.55
79.06 ± 0.67
80.59 ± 0.23
Appendix
Table 11: The two components of CAVA in training (CLIP features, fixed cut; mean ± std over three seeds). Table 7 gives the detection AUC of the same four combinations on CIFAR-10. Best per column in bold .
Nv
50
100
200
500
2,000
CAVA (ours)
82.92 ± 0.17
84.36 ± 0.06
85.47 ± 0.10
86.61 ± 0.15
87.91 ± 0.55
CAVA, w=0
82.76 ± 0.21
83.74 ± 0.11
85.37 ± 0.41
86.08 ± 0.34
87.38 ± 0.44
Appendix
Table 12: Training with small validation sets (CLIP features, CIFAR-10, CE+SCL-NL, fixed cut p=25% , mean ± std over three seeds, final-epoch accuracy on the test images outside the validation set). Best per column in bold .
MNIST
CIFAR-10
CIFAR-20
Method
Cut
CE Con.
CLL Con.
Acc.
CE Con.
CLL Con.
Acc.
CE Con.
CLL Con.
Acc.
TW-LAVA
p=0.25
1.24%
0.41%
99.53
9.84%
3.28%
86.34
24.34%
8.11%
64.10
p=0.35
28.73%
0.09%
99.15
30.03%
0.78%
85.31
36.81%
4.44%
63.78
p=0.45
44.54%
0.08%
99.20
44.99%
0.44%
84.13
47.70%
2.66%
61.87
CAVA (ours)
p=0.25
0.70%
0.23%
99.57
0.54%
0.18%
92.45
4.44%
1.48%
76.45
p=0.35
28.57%
0.00%
98.47
28.57%
0.00%
85.18
28.69%
0.06%
70.44
Appendix
Table 13: Detector quality and branch composition across datasets under the identical synthetic protocol ( η=25% , AutoAug, combined CE+SCL-NL loss), for the baseline TW-LAVA and for CAVA with the same feature extractor. The detection AUC is 0.9994 , 0.9833 , 0.9087 for TW-LAVA and 1.0000 , 1.0000 , 0.9971 for CAVA on MNIST, CIFAR-10, CIFAR-20. CE Contam. denotes the fraction of the recycled CE branch that consists of valid complementary samples (yˉi=yi) , which become false-positive ordinary labels when recycled. CLL Contam. denotes the fraction of the retained complementary-label pool that still consists of diagonal-noise samples (yˉi=yi) . Accuracy denotes the CE+SCL-NL test accuracy: a single run (seed 1126) for TW-LAVA, which uses all 10,000 test images as the validation set, and the mean over seeds 1126, 42, and 2023 for CAVA, which uses a fixed validation set of 2,000 test images the selection statistics are from seed 1126. For p>η the CE branch necessarily contains valid samples, so its contamination is at least 1−η/p for any detector.
Table 14: MNIST ablation under the synthetic diagonal-noise protocol with noise ratio η=25% and AutoAug. CLL Contam. denotes the fraction of the retained complementary-label pool that still consists of diagonal-noise samples (yˉi=yi) . CE Contam. denotes the fraction of the recycled CE branch that consists of valid complementary samples (yˉi=yi) , for which treating yˉi as an ordinary label is incorrect. FWD uses the transition matrix computed from the synthetic corruption record, which includes the diagonal. The upper block is the baseline TW-LAVA and the lower block is CAVA with the same feature extractor. Static p denotes the fixed cut. For CAVA, the adaptive cut si≤0 needs no ratio ( ∗ : seed 1126). TW-LAVA entries are single runs (seed 1126) that use all 10,000 test images as the validation set; CAVA entries are means over seeds 1126, 42, and 2023 with a fixed validation set of 2,000 test images (largest standard deviation 7.40, FWD at p=0.35 ; at most 1.20 elsewhere except FWD at p=0.45 , 4.55), and its selection statistics are from seed 1126; the best accuracy in each column is in bold .
Table 15: CIFAR-20 ablation under noise ratio η=25% and AutoAug. Column semantics follow Table 14 . CLL Contam. denotes the fraction of the retained complementary-label pool that still consists of diagonal-noise samples (yˉi=yi) , while CE Contam. denotes the fraction of the recycled CE branch that consists of valid complementary samples (yˉi=yi) . The corruption record is used only for post-hoc evaluation of branch composition and is never used by either method during OT valuation, thresholding, pruning, recycling, or training. The upper block is the baseline TW-LAVA and the lower block is CAVA with the same feature extractor. Static p denotes the fixed cut. For CAVA, the adaptive cut si≤0 needs no ratio ( ∗ : seed 1126). TW-LAVA entries are single runs (seed 1126) that use all 10,000 test images as the validation set; CAVA entries are means over seeds 1126, 42, and 2023 with a fixed validation set of 2,000 test images (largest standard deviation 2.36), and its selection statistics are from seed 1126; the best accuracy in each column is in bold .
Figure 11: OT valuation score distributions for diagonal-noise samples ( yˉi=yi ) and valid complementary samples ( yˉi=yi ) on MNIST, CIFAR-10, and CIFAR-20 under noise ratio η=25% and seed 1126, with the same feature extractor in both rows (validation set: 10,000 test images for TW-LAVA, a fixed subset of 2,000 for CAVA). Top: TW-LAVA, the baseline with the noisy-group label cost. The two groups become less separable as the dataset becomes harder, with AUC decreasing from 0.9994 on MNIST to 0.9833 on CIFAR-10 and 0.9087 on CIFAR-20, which explains the increasing branch contamination reported in Table 13 . Bottom: CAVA with the complementary label cost and the label margin. Diagonal noise stays on the low side and the separation is close to complete on all three datasets (AUC 1.000 , 1.000 , and 0.998 ).
Figure 12: Pruning-induced complementary-label bias (MNIST, η=25% ; pools of the original TW-LAVA protocol). Row-normalized transition matrices P(Yˉ∣Y) of the CLL pool at p=0.25 (left, near-uniform) and p=0.45 (right); × marks near-empty transitions ( <2% row mass). Aggressive pruning empties the transitions of visually confusable pairs, violating the uniform assumption of SCL-NL while the estimated Q of FWD absorbs the bias.
Figure 13: Pruning-induced complementary-label bias on CIFAR-20 ( η=25% ), as in Figure 12 : row-normalized transitions P(Yˉ∣Y) of the CLL pool at p=0.25 (left) and p=0.45 (right); × marks near-empty transitions ( <2% row mass; 5/380 versus 38/380 cells).
Setting
CE branch
CLL pool
Combined
CLL-only
Size
Err. Prec.
Err. Rec.
Size
Contam.
CE+SCL-NL
CE+FWD
SCL-NL
FWD
No pruning (p=0)
–
–
–
50,000
3.98%
–
–
50.68
51.76
TW-LAVA (noisy-group label cost)
Static p=0.03
1,500
32.1%
24.2%
48,500
3.11%
46.78
46.19
53.25
59.38
Static p=0.05
2,500
26.7%
33.5%
47,500
2.79%
46.48
52.44
53.81
63.81
Static p=0.08
4,000
21.7%
43.7%
46,000
2.44%
43.65
46.78
50.68
67.29
Appendix
Table 16: CLCIFAR-10 ablation with real-world human complementary labels under AutoAug, for the baseline TW-LAVA and for CAVA with the same feature extractor. Static p denotes the fixed cut; for CAVA, the adaptive cut si≤0 needs no ratio ( ∗ : seed 1126). TW-LAVA rows use the original TW-LAVA protocol with 10,000 validation images. Err. Prec. is the fraction of the recycled CE branch that consists of true annotation errors (yˉi=yi) , while Err. Rec. is the fraction of all annotation errors captured by the CE branch. CLL Contam. is the fraction of annotation errors remaining in the retained complementary-label pool. The annotation record is used only for post-hoc evaluation of branch composition and, where indicated, to construct known- Q FWD; neither method uses true labels for selection. TW-LAVA entries are single runs (seed 1126) that use all 10,000 test images as the validation set; CAVA entries are means over seeds 1126, 42, and 2023 with a fixed validation set of 2,000 test images (largest standard deviation 2.04), and its selection statistics are from seed 1126; the best accuracy in each column is in bold ; “–”: not applicable.
Setting
CE branch
CLL pool
Combined
CLL-only
Size
Err. Prec.
Err. Rec.
Size
Contam.
CE+SCL-NL
CE+FWD
SCL-NL
FWD
No pruning (p=0)
–
–
–
50,000
2.32%
–
–
8.98
23.73
TW-LAVA (noisy-group label cost)
Static p=0.03
1,500
7.8%
10.1%
48,500
2.15%
9.77
16.75
8.98
25.15
Static p=0.05
2,500
7.2%
15.5%
47,500
2.07%
9.08
14.10
9.08
24.95
Static p=0.08
4,000
7.7%
26.5%
46,000
1.85%
10.30
16.02
9.38
25.44
Appendix
Table 17: CLCIFAR-20 ablation with real-world human complementary labels under AutoAug, for the baseline TW-LAVA and for CAVA with the same feature extractor. Static p denotes the fixed cut; for CAVA, the adaptive cut si≤0 needs no ratio ( ∗ : seed 1126). TW-LAVA rows use the original TW-LAVA protocol with 10,000 validation images. Err. Prec. is the fraction of the recycled CE branch that consists of true annotation errors (yˉi=yi) , while Err. Rec. is the fraction of all annotation errors captured by the CE branch. CLL Contam. is the fraction of annotation errors remaining in the retained complementary-label pool. The annotation record is used only for post-hoc evaluation of branch composition and, where indicated, to construct known- Q FWD; neither method uses true labels for selection. TW-LAVA entries are single runs (seed 1126) that use all 10,000 test images as the validation set; CAVA entries are means over seeds 1126, 42, and 2023 with a fixed validation set of 2,000 test images (largest standard deviation 2.38), and its selection statistics are from seed 1126; the best accuracy in each column is in bold ; “–”: not applicable.
FOOD15
RESISC45-20
Places365-10
Method
Selection
5%
15%
25%
5%
15%
25%
5%
15%
25%
(a) Selection only: SCL-NL on the retained pool
No pruning
–
8.33
3.17
1.90
2.77
0.70
0.17
44.73
3.09
0.84
TW-LAVA
Fixed p
7.60
7.20
13.00
3.23
13.57
24.33
48.39
46.04
56.94
CAVA (ours)
Fixed p
22.50
21.10
18.90
23.17
23.43
24.70
75.08
74.03
73.90
CAVA (ours)
Adaptive cut
18.67
17.57
11.60
25.17
26.23
22.93
71.60
73.86
71.22
Appendix
Table 18: Test accuracy (%) on three further domains with synthetic diagonal noise (Figure 7 ; datasets in Appendix C.1 ). The validation set holds 50 test images per class ( 200 for Places365-10), and the fixed cut is p=η . Seed 1126; best per column and block in bold .
Figure 14: Other noise ratios. CIFAR-10 test accuracy (%) of TW-LAVA and CAVA against the fixed cut p∈{15%,25%,35%,45%} at diagonal-noise ratios η∈{15%,35%,45%} , above the crossover 1/M , with the selection-only objective (SCL-NL solid, FWD dashed). Same feature extractor and validation set for both methods; AutoAugment; single runs (seed 1126) under the protocol of Table 1 , accuracy after the final epoch on the held-out test images. The dotted line marks p=η .
TW-LAVA (noisy-group label cost)
CAVA (ours, complementary label cost)
η
Cut
CE+SCL-NL
CE+FWD
SCL-NL
FWD
CE+SCL-NL
CE+FWD
SCL-NL
FWD
2%
none
–
–
68.53 ± 2.28
69.30
–
–
68.53 ± 2.28
69.30
p=2%
48.38
29.57
67.22 ± 3.19
68.36
84.51
84.41
82.26 ± 0.25
82.16
p=5%
24.57
22.64
62.38 ± 1.80
66.03
77.31
75.89
82.64 ± 0.11
81.58
p=10%
9.95
16.25
46.66 ± 1.27
64.78
56.74
53.64
70.78 ± 1.37
67.61
p=15%
7.70
14.18
11.25 ± 1.30
31.19
42.59
40.69
47.84 ± 9.72
44.61
Appendix
Table 19: CIFAR-10 test accuracy (%) at small noise rates, η≤1/M=10% , where the label cost of TW-LAVA is reversed or blind (Theorem 1 ). Both methods use the same fixed cuts; TW-LAVA keeps its original OT settings here (Appendix C.2 ). SCL-NL and No pruning: mean ± std over three seeds; other objectives: seed 1126. Best per noise rate and objective in bold ; “–”: no recycled branch without pruning.
Figure 15: CAVA as a plug-in selection module across CLL objectives. Test accuracy (%) of six objectives without selection, with TW-LAVA, and with CAVA (selection only, no recycling; AutoAugment; seed 1126; final-epoch accuracy on the held-out test images, protocol of Table 1 ). All objectives use SGD as in the main experiments except OP, which uses Adam with learning rate 10−4 as in its official implementation. On synthetic CIFAR-10 ( η=25% ), CAVA uses the adaptive cut and TW-LAVA, which has no adaptive cut, the fixed cut p=25% ; on human-annotated CLCIFAR-10 ( η=3.98% ), both methods use the fixed cut p=5% . TW-LAVA and CAVA use the same 2,000 validation images.
Figure 16: Data augmentation. CIFAR-10 test accuracy (%) at η=25% of TW-LAVA and CAVA against the fixed cut p∈{25%,35%,45%} , and of CAVA with the adaptive cut si≤0 (stars right of the gray line, with SCL-NL and CE+SCL-NL), under Cutout, AutoAugment, and RandAugment. Row (a) uses the selection-only objective in Eq. ( 3.13 ) with SCL-NL (solid, filled markers) and FWD (dashed, open markers); row (b) the recycling objective in Eq. ( 3.14 ) with CE+SCL-NL and CE+FWD. Same feature extractor, validation set and OT settings for both methods; single runs (seed 1126), accuracy after the final epoch on the held-out test images, protocol of Table 1 .
Setting
CE Precision
CE Recall
F1
∣Irec∣
CE Contam.
CLL Contam.
Test Accuracy
Fixed cut p=25%
95.37%
95.37%
95.37%
12,500
4.63%
1.54%
88.46%
Fixed cut p=35%
71.12%
99.57%
82.97%
17,500
28.88%
0.17%
75.67%
Fixed cut p=45%
55.46%
99.82%
71.30%
22,500
44.54%
0.08%
61.58%
Appendix
Table 20: Branch quality of recycling with TW-LAVA on synthetic CIFAR-10 ( η=25% , CE+SCL-NL, seed 1126). The metrics of Table 4 use the true labels for evaluation only; the last column is the test accuracy.
Representation
Method with 2,000 clean labels
CIFAR-10
CIFAR-20
none
CE from scratch
71.52 ± 0.66
43.08 ± 2.24
supervised embedder
CAVA (ours), recycling
91.57 ± 0.14
75.34 ± 0.17
CLIP ViT-B/32
CAVA (ours), recycling
87.91 ± 0.55
67.37 ± 0.24
validation images only
CAVA (ours), recycling
75.22 ± 0.67
49.21 ± 0.85
Appendix
Table 21: What 2,000 clean labels are worth ( η=25% ; mean ± std over three seeds). CE from scratch trains on these labels alone. CAVA uses them only as its validation set, together with the 50,000 noisy complementary labels (CE+SCL-NL, p=25% ), on three fixed representations.
Dataset
Method
Nv
200
500
1,000
1,500
2,000
CIFAR-10
TW-LAVA
Detector AUC
0.98 ± 0.00
0.99 ± 0.00
0.99 ± 0.00
1.00 ± 0.00
1.00 ± 0.00
CE-branch Prec. (%)
91.52 ± 0.58
92.99 ± 0.29
94.21 ± 0.23
95.27 ± 0.18
95.46 ± 0.09
Accuracy (%)
84.94 ± 0.06
86.29 ± 0.31
87.82 ± 0.25
88.64 ± 0.07
88.75 ± 0.40
CAVA (ours)
Detector AUC
1.00 ± 0.00
1.00 ± 0.00
1.00 ± 0.00
1.00 ± 0.00
1.00 ± 0.00
CE-branch Prec. (%)
99.23 ± 0.11
99.29 ± 0.14
99.32 ± 0.13
99.34 ± 0.14
99.33 ± 0.15
Accuracy (%)
91.47 ± 0.16
91.69 ± 0.17
91.51 ± 0.17
91.69 ± 0.46
91.57 ± 0.14
Appendix
Table 22: Effect of the validation-set size Nv on CIFAR-10 and CIFAR-20 ( η=25% , fixed cut p=25% , CE+SCL-NL). Prec. is the share of true diagonal noise in the recycled branch. Mean ± std over three seeds; best per row in bold , ties broken by the unrounded value.
Training time
Acc. (%), final epoch
Acc. (%), best epoch
Method
p (%)
20 ep.
200 ep.
20 ep.
200 ep.
20 ep.
200 ep.
No pruning
0
3.1 h
31.5 h
0.12
–
2.52
–
TW-LAVA
15
2.7 h
27.4 h
27.79
42.90
27.96
43.66
25
2.4 h
24.2 h
61.01
68.26
61.01
69.64
35
2.1 h
20.7 h
67.76
71.05
67.80
72.40
45
1.8 h
17.7 h
55.95
70.28
56.00
71.14
Appendix
Table 23: Scaling to CIFAR-10-1M ( η=25% , SCL-NL, single run). Training time is the measured time of one epoch on a dedicated NVIDIA RTX A6000, multiplied by 20 or 200; it depends only on the size of the retained pool. Valuation adds about 2.5 hours for TW-LAVA and 4 minutes for CAVA. The CAVA times at p=15% are estimated by a linear fit in the pool size. The best-epoch columns are for reference only; the text uses the final epoch. Best per column in bold ; “–”: not run.
Method
Training Size
Validation Size
Data-Selection Runtime
Remark
LAVA
10K
10K
45 seconds
Full-set OT computation
SAVA
10K
10K
300 seconds
Batch-wise OT computation
TW-LAVA (task-wise)
10K
10K
45 seconds
One task-wise OT selection step
CAVA (ours)
10K
10K
0.2 seconds
OT solve and label margin on precomputed features
Appendix
Table 24: Runtime of one OT-based selection step on CIFAR-10 with 10K training and 10K validation samples. The CAVA time is the mean of three runs on one GPU, with features computed beforehand.
CAVA (ours)
Training set
LAVA
SAVA
TW-LAVA
Nv=2,000
Nv=10,000
10K
21.65 GB
3.00 GB
21.65 GB
0.10 GB
0.35 GB
20K
43.00 GB
3.00 GB
21.65 GB
0.17 GB
0.65 GB
30K
OOM
3.00 GB
21.65 GB
0.23 GB
0.95 GB
40K
OOM
3.00 GB
21.65 GB
0.30 GB
1.25 GB
50K
OOM
3.00 GB
21.65 GB
0.35 GB
1.55 GB
Appendix
Table 25: Peak GPU memory of OT-based selection as the training set grows. LAVA, SAVA, and TW-LAVA run their original pipelines with 10,000 validation images (TW-LAVA with tasks of 10K samples). For CAVA we report its valuation step, without feature extraction, with the 2,000 validation images of the paper and with 10,000 for a direct comparison. OOM: out of memory; “–”: not measured.
Figure 17: Label-margin visualization for randomly drawn samples from CLCIFAR-10 (human complementary labels, 3.98% annotation errors; first task, 2,000 validation images). Columns: image (red border: annotation error), labels of the validation images with the largest transport weight, with the weights (green: true class), label potentials fi(c)−mincfi(c) with the given label in red, margins of all samples in the task (blue: valid, red: annotation error; dashed: adaptive-cut threshold si=0 ) with this sample marked, and the decision of the adaptive cut.
Figure 18: Label-margin visualization for randomly drawn samples from Places365-10, ten scene classes of Places365 [ 41 ] with synthetic diagonal noise ( η=25% ; first task, 2,000 validation images). Columns as in Figure 17 . The fourth row is a failure: an annotation error whose image resembles a forest path is kept.
Complementary-label learning (CLL) is a weakly supervised paradigm where instances are labeled with classes they do not belong to. Despite a decade of research, CLL methods remain competitive mainly on 10-class classification, with scaling to large label spaces continuing to be an enduring bottleneck. This limitation stems from the common assumption of uniform label generation in traditional methods, which fatally dilutes the learning signal in many-class settings. In this paper, we demonstrate that this long-standing barrier can be overcome by deliberately designing a biased (non-uniform) generation process that restricts complementary labels to a subset of classes. This finding motivates us to propose Bias-Induced Constrained Labeling (BICL), a principled framework spanning data collection to training that leverages this bias. BICL enables effective learning on CIFAR-100 and TinyImageNet-200, achieving more than sevenfold accuracy improvements over traditional methods. Our findings establish a new trajectory for making CLL feasible for many classes in real-world applications.
Tan-Ha Mai, Chao-Kai Chiang, Han-Hwa Shih +3
1National Taiwan University · 3RIKEN Center for Advanced Intelligence Project · 2The University of Tokyo
When annotators disagree, that disagreement can reflect epistemic uncertainty rather than simple label noise. We study hard-label delivery as an alternative to the usual choices of collapsing votes to a single label or training directly on the empirical soft-label distribution. We focus on two primary hard-label methods: multipass, which cycles through observed votes while keeping the dataset size fixed, and stochastic label sampling (SLS), which samples one label per example at the start of each epoch. On CIFAR-10H, we find that when only a small number of annotations per example is available, hard-label delivery improves over soft-label training, with larger improvements where the sparse empirical target is farther from the full annotator distribution. When full annotator distributions are available, both hard-label methods match soft-label training. We use deterministic control as an ablation of multipass and shuffled SLS as a control that breaks the example-to-distribution match. We also show that SLS and soft-label cross-entropy optimize the same expected objective. Hard-label delivery also converges to flatter basins, with supporting descriptive evidence from OOD detection on SVHN and CIFAR-100. Overall, these results suggest that multipass is a strong practical default when raw vote counts are available, while SLS offers a lightweight alternative that remains competitive when only a few votes per example are available and matches soft-label training when full annotator distributions are available.
Reliable validation of machine learning models is a crucial step in designing robust and trustworthy systems. Yet validation relies on annotated test sets treated as ground truth, even though annotations can be noisy or ambiguous. In object detection, sources may disagree on object presence, box location, or class label. Standard agreement metrics usually binarize box overlap before computing a summary score, obscuring the degree and structure of disagreement between annotation sets. Here, we study an Optimal Transport (OT)-based metric for measuring agreement between object detection annotations. Instead of binarizing bounding box overlap, this metric assigns graded costs to matched and unmatched labeled boxes. Through theoretical analysis and experiments on real and synthetically perturbed annotations, we show that OT captures graded changes in agreement and distinguishes annotation pairs that thresholded metrics score identically. Our results suggest that OT provides a richer measure of annotation agreement in object detection, especially for domains with many small or ambiguous objects. Such agreement estimates can support more reliable validation when labels are noisy or conflicting.
Kirill Prokhorov, Alexandr A. Kalinin
Openface.io, Vilnius, Lithuania · Broad Institute of MIT and Harvard, Cambridge, MA, USA