# Binary Classification with Instance and Label Dependent Label Noise

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 6 Jun 2023.

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

- [Co-teaching: Robust Training of Deep Neural Networks with Extremely Noisy Labels](https://mlsanity.com/paper/1804.06872/) (2018)
- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels](https://mlsanity.com/paper/1712.05055/) (2017)
- [How does Disagreement Help Generalization against Label Corruption?](https://mlsanity.com/paper/1901.04215/) (2019)
- [Combating noisy labels by agreement: A joint training method with co-regularization](https://mlsanity.com/paper/2003.02752/) (2020)
- [Decoupling "when to update" from "how to update"](https://mlsanity.com/paper/1706.02613/) (2017)
- [Probabilistic End-to-end Noise Correction for Learning with Noisy Labels](https://mlsanity.com/paper/1903.07788/) (2019)
- [Are Anchor Points Really Indispensable in Label-Noise Learning?](https://mlsanity.com/paper/1906.00189/) (2019)
- [SELF: Learning to Filter Noisy Labels with Self-Ensembling](https://mlsanity.com/paper/1910.01842/) (2019)
- [Learning with Instance-Dependent Label Noise: A Sample Sieve Approach](https://mlsanity.com/paper/2010.02347/) (2020)
- [Peer Loss Functions: Learning from Noisy Labels without Knowing Noise Rates](https://mlsanity.com/paper/1910.03231/) (2019)
- [A Second-Order Approach to Learning with Instance-Dependent Label Noise](https://mlsanity.com/paper/2012.11854/) (2020)
- [Beyond Class-Conditional Assumption: A Primary Attempt to Combat Instance-Dependent Label Noise](https://mlsanity.com/paper/2012.05458/) (2020)
- [Classification with Asymmetric Label Noise: Consistency and Maximal Denoising](https://mlsanity.com/paper/1303.1208/) (2013)
- [Mixture Proportion Estimation via Kernel Embedding of Distributions](https://mlsanity.com/paper/1603.02501/) (2016)
- [Confidence Scores Make Instance-dependent Label-noise Learning Possible](https://mlsanity.com/paper/2001.03772/) (2020)
- [Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization](https://mlsanity.com/paper/2102.02414/) (2021)
- [Learning with Bounded Instance- and Label-dependent Label Noise](https://mlsanity.com/paper/1709.03768/) (2017)
- [Making Risk Minimization Tolerant to Label Noise](https://mlsanity.com/paper/1403.3610/) (2014)
- [Part-dependent Label Noise: Towards Instance-dependent Label Noise](https://mlsanity.com/paper/2006.07836/) (2020)
- [Exponential convergence of testing error for stochastic gradient methods](https://mlsanity.com/paper/1712.04755/) (2017)
- [Classification with unknown class-conditional label noise on non-compact feature spaces](https://mlsanity.com/paper/1902.05627/) (2019)
- [Binary classification with corrupted labels](https://mlsanity.com/paper/2106.09136/) (2021)

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

- [Label Noise: Ignorance Is Bliss](https://mlsanity.com/paper/2411.00079/) (2024)
- [Retraining with Predicted Hard Labels Provably Increases Model Accuracy](https://mlsanity.com/paper/2406.11206/) (2024)

## Abstract (arXiv)

Learning with label dependent label noise has been extensively explored in both theory and practice; however, dealing with instance (i.e., feature) and label dependent label noise continues to be a challenging task. The difficulty arises from the fact that the noise rate varies for each instance, making it challenging to estimate accurately. The question of whether it is possible to learn a reliable model using only noisy samples remains unresolved. We answer this question with a theoretical analysis that provides matching upper and lower bounds. Surprisingly, our results show that, without any additional assumptions, empirical risk minimization achieves the optimal excess risk bound. Specifically, we derive a novel excess risk bound proportional to the noise level, which holds in very general settings, by comparing the empirical risk minimizers obtained from clean samples and noisy samples. Second, we show that the minimax lower bound for the 0-1 loss is a constant proportional to the average noise rate. Our findings suggest that learning solely with noisy samples is impossible without access to clean samples or strong assumptions on the distribution of the data.