Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes

*Complementary-label learning* (CLL) is a weakly supervised paradigm for multiclass classification, where each training instance comes with a complementary label indicating a class that the instance does *not* belong to. After nearly a decade of research, CLL still faces a long-standing scalability barrier: as the number of classes grows from the scale of CIFAR-10 to that of TinyImageNet-200, existing methods learn almost nothing meaningful. We show that this barrier is not intrinsic to the problem, but tied to a common modeling choice. Most approaches assume a uniform transition matrix when modeling complementary-label generation, while the potential of assuming or leveraging a biased (non-uniform) transition matrix remains underexplored, despite some empirical successes on real-world data. Through a systematic study, we demonstrate that performance can be significantly improved by deliberately designing a biased transition matrix that restricts complementary labels to a subset of possible classes. Motivated by this finding, we propose *bias-induced constrained labeling* (BICL), a principled and practical framework spanning from data collection to training that properly leverages such bias for solving CLL. Extensive experiments demonstrate that BICL substantially improves CLL performance and, most importantly, breaks this barrier, enabling effective learning on CIFAR-100 and TinyImageNet-200 with more than sevenfold accuracy improvements.