# Complementary Labels Learning with Augmented Classes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 19 Nov 2022.

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

- [Recent Advances in Open Set Recognition: A Survey](https://mlsanity.com/paper/1811.08581/) (2018)
- [Learning with Biased Complementary Labels](https://mlsanity.com/paper/1711.09535/) (2017)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Mixture Proportion Estimation via Kernel Embedding of Distributions](https://mlsanity.com/paper/1603.02501/) (2016)
- [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)
- [Unbiased Risk Estimators Can Mislead: A Case Study of Learning with Complementary Labels](https://mlsanity.com/paper/2007.02235/) (2020)
- [Dropout Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/1402.3811/) (2014)
- [Learning to Detect Instance-level Salient Objects Using Complementary Image Labels](https://mlsanity.com/paper/2111.10137/) (2021)
- [An Unbiased Risk Estimator for Learning with Augmented Classes](https://mlsanity.com/paper/1910.09388/) (2019)
- [Generative-Discriminative Complementary Learning](https://mlsanity.com/paper/1904.01612/) (2019)
- [Exploratory Machine Learning with Unknown Unknowns](https://mlsanity.com/paper/2002.01605/) (2020)

## Abstract (arXiv)

Complementary Labels Learning (CLL) arises in many real-world tasks such as private questions classification and online learning, which aims to alleviate the annotation cost compared with standard supervised learning. Unfortunately, most previous CLL algorithms were in a stable environment rather than an open and dynamic scenarios, where data collected from unseen augmented classes in the training process might emerge in the testing phase. In this paper, we propose a novel problem setting called Complementary Labels Learning with Augmented Classes (CLLAC), which brings the challenge that classifiers trained by complementary labels should not only be able to classify the instances from observed classes accurately, but also recognize the instance from the Augmented Classes in the testing phase. Specifically, by using unlabeled data, we propose an unbiased estimator of classification risk for CLLAC, which is guaranteed to be provably consistent. Moreover, we provide generalization error bound for proposed method which shows that the optimal parametric convergence rate is achieved for estimation error. Finally, the experimental results on several benchmark datasets verify the effectiveness of the proposed method.