# Learning with Multiple Complementary Labels

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2019.

## Built on by (most cited first, 30 of 53)

- [Provably End-to-end Label-Noise Learning without Anchor Points](https://mlsanity.com/paper/2102.02400/) (2021)
- [Leveraged Weighted Loss for Partial Label Learning](https://mlsanity.com/paper/2106.05731/) (2021)
- [SoLar: Sinkhorn Label Refinery for Imbalanced Partial-Label Learning](https://mlsanity.com/paper/2209.10365/) (2022)
- [Progressive Purification for Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2206.00830/) (2022)
- [PiCO+: Contrastive Label Disambiguation for Robust Partial Label Learning](https://mlsanity.com/paper/2201.08984/) (2022)
- [Learning from Similarity-Confidence Data](https://mlsanity.com/paper/2102.06879/) (2021)
- [Learning from Multiple Noisy Partial Labelers](https://mlsanity.com/paper/2106.04530/) (2021)
- [Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification](https://mlsanity.com/paper/2102.00678/) (2021)
- [Realistic Evaluation of Deep Partial-Label Learning Algorithms](https://mlsanity.com/paper/2502.10184/) (2025)
- [Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical](https://mlsanity.com/paper/2311.15502/) (2023)
- [Imprecise Label Learning: A Unified Framework for Learning with Various Imprecise Label Configurations](https://mlsanity.com/paper/2305.12715/) (2023)
- [Learning with Proper Partial Labels](https://mlsanity.com/paper/2112.12303/) (2021)
- [Bidirectional Uncertainty-Based Active Learning for Open Set Annotation](https://mlsanity.com/paper/2402.15198/) (2024)
- [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)
- [A General Framework for Learning from Weak Supervision](https://mlsanity.com/paper/2402.01922/) (2024)
- [An Empirical Study and Analysis on Open-Set Semi-Supervised Learning](https://mlsanity.com/paper/2101.08237/) (2021)
- [Weakly-Supervised Temporal Action Localization by Progressive Complementary Learning](https://mlsanity.com/paper/2206.11011/) (2022)
- [Deep Partial Multi-Label Learning with Graph Disambiguation](https://mlsanity.com/paper/2305.05882/) (2023)
- [Unified Risk Analysis for Weakly Supervised Learning](https://mlsanity.com/paper/2309.08216/) (2023)
- [Adversarial Training with Complementary Labels: On the Benefit of Gradually Informative Attacks](https://mlsanity.com/paper/2211.00269/) (2022)
- [Multi-Class Classification from Single-Class Data with Confidences](https://mlsanity.com/paper/2106.08864/) (2021)
- [IRNet: Iterative Refinement Network for Noisy Partial Label Learning](https://mlsanity.com/paper/2211.04774/) (2022)
- [Complementary Classifier Induced Partial Label Learning](https://mlsanity.com/paper/2305.09897/) (2023)
- [Labels, Information, and Computation: Efficient Learning Using Sufficient Labels](https://mlsanity.com/paper/2104.09015/) (2021)
- [NEV-NCD: Negative Learning, Entropy, and Variance regularization based novel action categories discovery](https://mlsanity.com/paper/2304.07354/) (2023)
- [Intra-Cluster Mixup: An Effective Data Augmentation Technique for Complementary-Label Learning](https://mlsanity.com/paper/2509.17971/) (2025)
- [Invariance Learning based on Label Hierarchy](https://mlsanity.com/paper/2203.15549/) (2022)
- [Complementary to Multiple Labels: A Correlation-Aware Correction Approach](https://mlsanity.com/paper/2302.12987/) (2023)

## Abstract (arXiv)

A complementary label (CL) simply indicates an incorrect class of an example, but learning with CLs results in multi-class classifiers that can predict the correct class. Unfortunately, the problem setting only allows a single CL for each example, which notably limits its potential since our labelers may easily identify multiple CLs (MCLs) to one example. In this paper, we propose a novel problem setting to allow MCLs for each example and two ways for learning with MCLs. In the first way, we design two wrappers that decompose MCLs into many single CLs, so that we could use any method for learning with CLs. However, the supervision information that MCLs hold is conceptually diluted after decomposition. Thus, in the second way, we derive an unbiased risk estimator; minimizing it processes each set of MCLs as a whole and possesses an estimation error bound. We further improve the second way into minimizing properly chosen upper bounds. Experiments show that the former way works well for learning with MCLs but the latter is even better.