Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes
This work solves the scaling bottleneck of complementary-label learning to many classes, enabling practical use in real-world applications with large label spaces.
Complementary-label learning (CLL) has been limited to 10-class problems due to uniform label generation diluting the signal in many-class settings. By deliberately designing a biased generation process, the proposed BICL framework achieves over sevenfold accuracy improvements on CIFAR-100 and TinyImageNet-200, making CLL feasible for many classes.
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.