# Learning from Complementary Labels

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

## Key facts

- Cited by 88 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2017.

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

- [Multi-Label Learning from Single Positive Labels](https://mlsanity.com/paper/2106.09708/) (2021)
- [To Smooth or Not? When Label Smoothing Meets Noisy Labels](https://mlsanity.com/paper/2106.04149/) (2021)
- [Leveraged Weighted Loss for Partial Label Learning](https://mlsanity.com/paper/2106.05731/) (2021)
- [Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization](https://mlsanity.com/paper/2102.02414/) (2021)
- [Domain Adaptive Semantic Segmentation without Source Data](https://mlsanity.com/paper/2110.06484/) (2021)
- [Progressive Purification for Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2206.00830/) (2022)
- [MutexMatch: Semi-Supervised Learning with Mutex-Based Consistency Regularization](https://mlsanity.com/paper/2203.14316/) (2022)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [On the Robustness of Average Losses for Partial-Label Learning](https://mlsanity.com/paper/2106.06152/) (2021)
- [Learning from Similarity-Confidence Data](https://mlsanity.com/paper/2102.06879/) (2021)
- [Two Wrongs Don't Make a Right: Combating Confirmation Bias in Learning with Label Noise](https://mlsanity.com/paper/2112.02960/) (2021)
- [Learning from Ambiguous Labels for Lung Nodule Malignancy Prediction](https://mlsanity.com/paper/2104.11436/) (2021)
- [Learning from Multiple Noisy Partial Labelers](https://mlsanity.com/paper/2106.04530/) (2021)
- [Rethinking Precision of Pseudo Label: Test-Time Adaptation via Complementary Learning](https://mlsanity.com/paper/2301.06013/) (2023)
- [Translation Consistent Semi-supervised Segmentation for 3D Medical Images](https://mlsanity.com/paper/2203.14523/) (2022)
- [Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification](https://mlsanity.com/paper/2102.00678/) (2021)
- [Unsupervised Abstract Reasoning for Raven's Problem Matrices](https://mlsanity.com/paper/2109.10011/) (2021)
- [Realistic Evaluation of Deep Partial-Label Learning Algorithms](https://mlsanity.com/paper/2502.10184/) (2025)
- [An Embarrassingly Simple Approach to Semi-Supervised Few-Shot Learning](https://mlsanity.com/paper/2209.13777/) (2022)
- [Disambiguated Attention Embedding for Multi-Instance Partial-Label Learning](https://mlsanity.com/paper/2305.16912/) (2023)
- [Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical](https://mlsanity.com/paper/2311.15502/) (2023)
- [Latent Class-Conditional Noise Model](https://mlsanity.com/paper/2302.09595/) (2023)
- [Learning with Proper Partial Labels](https://mlsanity.com/paper/2112.12303/) (2021)
- [Semantic Clustering based Deduction Learning for Image Recognition and Classification](https://mlsanity.com/paper/2112.13165/) (2021)
- [ObjFormer: Learning Land-Cover Changes From Paired OSM Data and Optical High-Resolution Imagery via Object-Guided Transformer](https://mlsanity.com/paper/2310.02674/) (2023)
- [Bidirectional Uncertainty-Based Active Learning for Open Set Annotation](https://mlsanity.com/paper/2402.15198/) (2024)
- [Enhancing Vision-Language Few-Shot Adaptation with Negative Learning](https://mlsanity.com/paper/2403.12964/) (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)
- [G2NetPL: Generic Game-Theoretic Network for Partial-Label Image Classification](https://mlsanity.com/paper/2210.11469/) (2022)

## Abstract (arXiv)

Collecting labeled data is costly and thus a critical bottleneck in real-world classification tasks. To mitigate this problem, we propose a novel setting, namely learning from complementary labels for multi-class classification. A complementary label specifies a class that a pattern does not belong to. Collecting complementary labels would be less laborious than collecting ordinary labels, since users do not have to carefully choose the correct class from a long list of candidate classes. However, complementary labels are less informative than ordinary labels and thus a suitable approach is needed to better learn from them. In this paper, we show that an unbiased estimator to the classification risk can be obtained only from complementarily labeled data, if a loss function satisfies a particular symmetric condition. We derive estimation error bounds for the proposed method and prove that the optimal parametric convergence rate is achieved. We further show that learning from complementary labels can be easily combined with learning from ordinary labels (i.e., ordinary supervised learning), providing a highly practical implementation of the proposed method. Finally, we experimentally demonstrate the usefulness of the proposed methods.