# Complementary-Label Learning for Arbitrary Losses and Models

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2018.

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

- [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)
- [Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2110.12911/) (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)
- [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)
- [Rethinking Precision of Pseudo Label: Test-Time Adaptation via Complementary Learning](https://mlsanity.com/paper/2301.06013/) (2023)
- [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)
- [Learning with Proper Partial Labels](https://mlsanity.com/paper/2112.12303/) (2021)
- [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)
- [RDA: Reciprocal Distribution Alignment for Robust Semi-supervised Learning](https://mlsanity.com/paper/2208.04619/) (2022)
- [Weakly Supervised Regression with Interval Targets](https://mlsanity.com/paper/2306.10458/) (2023)
- [Weakly-Supervised Temporal Action Localization by Progressive Complementary Learning](https://mlsanity.com/paper/2206.11011/) (2022)
- [Boosting Semi-Supervised Learning with Contrastive Complementary Labeling](https://mlsanity.com/paper/2212.06643/) (2022)
- [Unified Risk Analysis for Weakly Supervised Learning](https://mlsanity.com/paper/2309.08216/) (2023)
- [Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation](https://mlsanity.com/paper/2312.16478/) (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)
- [Partial-Label Regression](https://mlsanity.com/paper/2306.08968/) (2023)
- [Partial-Label Learning with a Reject Option](https://mlsanity.com/paper/2402.00592/) (2024)
- [Labels, Information, and Computation: Efficient Learning Using Sufficient Labels](https://mlsanity.com/paper/2104.09015/) (2021)
- [An Exploration into why Output Regularization Mitigates Label Noise](https://mlsanity.com/paper/2104.12477/) (2021)
- [Partial-Label Learning with Conformal Candidate Cleaning](https://mlsanity.com/paper/2502.07661/) (2025)
- [Intra-Cluster Mixup: An Effective Data Augmentation Technique for Complementary-Label Learning](https://mlsanity.com/paper/2509.17971/) (2025)

## Abstract (arXiv)

In contrast to the standard classification paradigm where the true class is given to each training pattern, complementary-label learning only uses training patterns each equipped with a complementary label, which only specifies one of the classes that the pattern does not belong to. The goal of this paper is to derive a novel framework of complementary-label learning with an unbiased estimator of the classification risk, for arbitrary losses and models---all existing methods have failed to achieve this goal. Not only is this beneficial for the learning stage, it also makes model/hyper-parameter selection (through cross-validation) possible without the need of any ordinarily labeled validation data, while using any linear/non-linear models or convex/non-convex loss functions. We further improve the risk estimator by a non-negative correction and gradient ascent trick, and demonstrate its superiority through experiments.