# Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 71 references that are in the map.
- First posted on arXiv 27 Nov 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels](https://mlsanity.com/paper/1805.07836/) (2018)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [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)
- [Learning with Biased Complementary Labels](https://mlsanity.com/paper/1711.09535/) (2017)
- [Provably Consistent Partial-Label Learning](https://mlsanity.com/paper/2007.08929/) (2020)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Classification with Asymmetric Label Noise: Consistency and Maximal Denoising](https://mlsanity.com/paper/1303.1208/) (2013)
- [Mixture Proportion Estimation via Kernel Embedding of Distributions](https://mlsanity.com/paper/1603.02501/) (2016)
- [Leveraged Weighted Loss for Partial Label Learning](https://mlsanity.com/paper/2106.05731/) (2021)
- [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)
- [Mixture Proportion Estimation and PU Learning: A Modern Approach](https://mlsanity.com/paper/2111.00980/) (2021)
- [Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning](https://mlsanity.com/paper/1603.03130/) (2016)
- [Mitigating Memorization of Noisy Labels by Clipping the Model Prediction](https://mlsanity.com/paper/2212.04055/) (2022)
- [Dist-PU: Positive-Unlabeled Learning from a Label Distribution Perspective](https://mlsanity.com/paper/2212.02801/) (2022)
- [Mitigating Overfitting in Supervised Classification from Two Unlabeled Datasets: A Consistent Risk Correction Approach](https://mlsanity.com/paper/1910.08974/) (2019)
- [Unbiased Risk Estimators Can Mislead: A Case Study of Learning with Complementary Labels](https://mlsanity.com/paper/2007.02235/) (2020)
- [Active Learning with Partial Feedback](https://mlsanity.com/paper/1802.07427/) (2018)
- [Progressive Purification for Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2206.00830/) (2022)
- [Learning from Similarity-Confidence Data](https://mlsanity.com/paper/2102.06879/) (2021)
- [Rethinking Class-Prior Estimation for Positive-Unlabeled Learning](https://mlsanity.com/paper/2002.03673/) (2020)
- [Rethinking Precision of Pseudo Label: Test-Time Adaptation via Complementary Learning](https://mlsanity.com/paper/2301.06013/) (2023)

## Built on by (most cited first, 10 of 10)

- [Realistic Evaluation of Deep Partial-Label Learning Algorithms](https://mlsanity.com/paper/2502.10184/) (2025)
- [Rethinking Consistent Multi-Label Classification Under Inexact Supervision](https://mlsanity.com/paper/2510.04091/) (2025)
- [Intra-Cluster Mixup: An Effective Data Augmentation Technique for Complementary-Label Learning](https://mlsanity.com/paper/2509.17971/) (2025)
- [Learning from True-False Labels via Multi-modal Prompt Retrieving](https://mlsanity.com/paper/2405.15228/) (2024)
- [libcll: an Extendable Python Toolkit for Complementary-Label Learning](https://mlsanity.com/paper/2411.12276/) (2024)
- [Learning from Complementary Features](https://mlsanity.com/paper/2408.14788/) (2024)
- [Exploiting the Potential Supervision Information of Clean Samples in Partial Label Learning](https://mlsanity.com/paper/2505.09354/) (2025)
- [Towards Scalable Oversight via Partitioned Human Supervision](https://mlsanity.com/paper/2510.22500/) (2025)
- [Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes](https://mlsanity.com/paper/2605.15586/) (2026)
- [Recent advances in weakly supervised learning: New supervision paradigms, assumption relaxations, and practical solutions](https://mlsanity.com/paper/2608.06896/) (2026)

## Abstract (arXiv)

Complementary-label learning is a weakly supervised learning problem in which each training example is associated with one or multiple complementary labels indicating the classes to which it does not belong. Existing consistent approaches have relied on the uniform distribution assumption to model the generation of complementary labels, or on an ordinary-label training set to estimate the transition matrix in non-uniform cases. However, either condition may not be satisfied in real-world scenarios. In this paper, we propose a novel consistent approach that does not rely on these conditions. Inspired by the positive-unlabeled (PU) learning literature, we propose an unbiased risk estimator based on the Selected-Completely-at-Random assumption for complementary-label learning. We then introduce a risk-correction approach to address overfitting problems. Furthermore, we find that complementary-label learning can be expressed as a set of negative-unlabeled binary classification problems when using the one-versus-rest strategy. Extensive experimental results on both synthetic and real-world benchmark datasets validate the superiority of our proposed approach over state-of-the-art methods.