# Reduction from Complementary-Label Learning to Probability Estimates

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 20 Sep 2022.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Provably End-to-end Label-Noise Learning without Anchor Points](https://mlsanity.com/paper/2102.02400/) (2021)
- [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)
- [On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data](https://mlsanity.com/paper/1808.10585/) (2018)
- [Unbiased Risk Estimators Can Mislead: A Case Study of Learning with Complementary Labels](https://mlsanity.com/paper/2007.02235/) (2020)
- [Generative-Discriminative Complementary Learning](https://mlsanity.com/paper/1904.01612/) (2019)
- [Bridging Ordinary-Label Learning and Complementary-Label Learning](https://mlsanity.com/paper/2002.02158/) (2020)
- [Learning from a Complementary-label Source Domain: Theory and Algorithms](https://mlsanity.com/paper/2008.01454/) (2020)
- [Multi-Complementary and Unlabeled Learning for Arbitrary Losses and Models](https://mlsanity.com/paper/2001.04243/) (2020)

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

- [Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical](https://mlsanity.com/paper/2311.15502/) (2023)
- [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)
- [Enhancing Label Sharing Efficiency in Complementary-Label Learning with Label Augmentation](https://mlsanity.com/paper/2305.08344/) (2023)
- [Learning from Complementary Features](https://mlsanity.com/paper/2408.14788/) (2024)
- [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 (CLL) is a weakly-supervised learning problem that aims to learn a multi-class classifier from only complementary labels, which indicate a class to which an instance does not belong. Existing approaches mainly adopt the paradigm of reduction to ordinary classification, which applies specific transformations and surrogate losses to connect CLL back to ordinary classification. Those approaches, however, face several limitations, such as the tendency to overfit or be hooked on deep models. In this paper, we sidestep those limitations with a novel perspective--reduction to probability estimates of complementary classes. We prove that accurate probability estimates of complementary labels lead to good classifiers through a simple decoding step. The proof establishes a reduction framework from CLL to probability estimates. The framework offers explanations of several key CLL approaches as its special cases and allows us to design an improved algorithm that is more robust in noisy environments. The framework also suggests a validation procedure based on the quality of probability estimates, leading to an alternative way to validate models with only complementary labels. The flexible framework opens a wide range of unexplored opportunities in using deep and non-deep models for probability estimates to solve the CLL problem. Empirical experiments further verified the framework's efficacy and robustness in various settings.