# Unbiased Risk Estimators Can Mislead: A Case Study of Learning with Complementary Labels

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2020.

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

- [Provably End-to-end Label-Noise Learning without Anchor Points](https://mlsanity.com/paper/2102.02400/) (2021)
- [Learning from Similarity-Confidence Data](https://mlsanity.com/paper/2102.06879/) (2021)
- [Realistic Evaluation of Deep Partial-Label Learning Algorithms](https://mlsanity.com/paper/2502.10184/) (2025)
- [Counterfactual Prediction Under Outcome Measurement Error](https://mlsanity.com/paper/2302.11121/) (2023)
- [Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical](https://mlsanity.com/paper/2311.15502/) (2023)
- [Debiased Recommendation with Noisy Feedback](https://mlsanity.com/paper/2406.17182/) (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)
- [Unbiased Loss Functions for Multilabel Classification with Missing Labels](https://mlsanity.com/paper/2109.11282/) (2021)
- [Weakly-Supervised Temporal Action Localization by Progressive Complementary Learning](https://mlsanity.com/paper/2206.11011/) (2022)
- [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)
- [An Exploration into why Output Regularization Mitigates Label Noise](https://mlsanity.com/paper/2104.12477/) (2021)
- [Learning from Label Proportions with Instance-wise Consistency](https://mlsanity.com/paper/2203.12836/) (2022)
- [Intra-Cluster Mixup: An Effective Data Augmentation Technique for Complementary-Label Learning](https://mlsanity.com/paper/2509.17971/) (2025)
- [Lower-Bounded Proper Losses for Weakly Supervised Classification](https://mlsanity.com/paper/2103.02893/) (2021)
- [Complementary to Multiple Labels: A Correlation-Aware Correction Approach](https://mlsanity.com/paper/2302.12987/) (2023)
- [Deconstructing the Failure of Ideal Noise Correction: A Three-Pillar Diagnosis](https://mlsanity.com/paper/2603.12997/) (2026)
- [Complementary Labels Learning with Augmented Classes](https://mlsanity.com/paper/2211.10701/) (2022)
- [Learning from Stochastic Labels](https://mlsanity.com/paper/2302.00299/) (2023)
- [Enhancing Label Sharing Efficiency in Complementary-Label Learning with Label Augmentation](https://mlsanity.com/paper/2305.08344/) (2023)
- [ESA: Example Sieve Approach for Multi-Positive and Unlabeled Learning](https://mlsanity.com/paper/2412.02240/) (2024)
- [Learning from Uncertain Similarity and Unlabeled Data](https://mlsanity.com/paper/2509.11984/) (2025)
- [Risk-Consistent Multiclass Learning from Random Label-Subset Membership Queries](https://mlsanity.com/paper/2605.07413/) (2026)
- [Focused PU learning from imbalanced data](https://mlsanity.com/paper/2605.14467/) (2026)
- [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)

In weakly supervised learning, unbiased risk estimator(URE) is a powerful tool for training classifiers when training and test data are drawn from different distributions. Nevertheless, UREs lead to overfitting in many problem settings when the models are complex like deep networks. In this paper, we investigate reasons for such overfitting by studying a weakly supervised problem called learning with complementary labels. We argue the quality of gradient estimation matters more in risk minimization. Theoretically, we show that a URE gives an unbiased gradient estimator(UGE). Practically, however, UGEs may suffer from huge variance, which causes empirical gradients to be usually far away from true gradients during minimization. To this end, we propose a novel surrogate complementary loss(SCL) framework that trades zero bias with reduced variance and makes empirical gradients more aligned with true gradients in the direction. Thanks to this characteristic, SCL successfully mitigates the overfitting issue and improves URE-based methods.