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

arXiv: https://arxiv.org/abs/2605.15586 · HTML: https://mlsanity.com/paper/2605.15586/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 46 references that are in the map.
- First posted on arXiv 15 May 2026.

## Builds on (most cited first, 30 of 30)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Visual Instruction Tuning](https://mlsanity.com/paper/2304.08485/) (2023)
- [Exploring Simple Siamese Representation Learning](https://mlsanity.com/paper/2011.10566/) (2020)
- [RandAugment: Practical automated data augmentation with a reduced search space](https://mlsanity.com/paper/1909.13719/) (2019)
- [Improved Regularization of Convolutional Neural Networks with Cutout](https://mlsanity.com/paper/1708.04552/) (2017)
- [An Empirical Study of Training Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.02057/) (2021)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [Learning with Noisy Labels Revisited: A Study Using Real-World Human Annotations](https://mlsanity.com/paper/2110.12088/) (2021)
- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [NLNL: Negative Learning for Noisy Labels](https://mlsanity.com/paper/1908.07387/) (2019)
- [Progressive Identification of True Labels for Partial-Label Learning](https://mlsanity.com/paper/2002.08053/) (2020)
- [BYOL works even without batch statistics](https://mlsanity.com/paper/2010.10241/) (2020)
- [Learning with Biased Complementary Labels](https://mlsanity.com/paper/1711.09535/) (2017)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Complementary-Label Learning for Arbitrary Losses and Models](https://mlsanity.com/paper/1810.04327/) (2018)
- [Learning with Multiple Complementary Labels](https://mlsanity.com/paper/1912.12927/) (2019)
- [Classification from Pairwise Similarity and Unlabeled Data](https://mlsanity.com/paper/1802.04381/) (2018)
- [SoLar: Sinkhorn Label Refinery for Imbalanced Partial-Label Learning](https://mlsanity.com/paper/2209.10365/) (2022)
- [Unbiased Risk Estimators Can Mislead: A Case Study of Learning with Complementary Labels](https://mlsanity.com/paper/2007.02235/) (2020)
- [Learning from Similarity-Confidence Data](https://mlsanity.com/paper/2102.06879/) (2021)
- [Binary Classification with Confidence Difference](https://mlsanity.com/paper/2310.05632/) (2023)
- [Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical](https://mlsanity.com/paper/2311.15502/) (2023)
- [Pairwise Supervision Can Provably Elicit a Decision Boundary](https://mlsanity.com/paper/2006.06207/) (2020)
- [Reduction from Complementary-Label Learning to Probability Estimates](https://mlsanity.com/paper/2209.09500/) (2022)
- [Class-Imbalanced Complementary-Label Learning via Weighted Loss](https://mlsanity.com/paper/2209.14189/) (2022)
- [CLImage: Human-Annotated Datasets for Complementary-Label Learning](https://mlsanity.com/paper/2305.08295/) (2023)
- [Intra-Cluster Mixup: An Effective Data Augmentation Technique for Complementary-Label Learning](https://mlsanity.com/paper/2509.17971/) (2025)

## Abstract (arXiv)

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.