# Classification with Asymmetric Label Noise: Consistency and Maximal Denoising

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2013.

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

- [To Smooth or Not? When Label Smoothing Meets Noisy Labels](https://mlsanity.com/paper/2106.04149/) (2021)
- [Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization](https://mlsanity.com/paper/2102.02414/) (2021)
- [Instance-Dependent Label-Noise Learning with Manifold-Regularized Transition Matrix Estimation](https://mlsanity.com/paper/2206.02791/) (2022)
- [Ground(less) Truth: A Causal Framework for Proxy Labels in Human-Algorithm Decision-Making](https://mlsanity.com/paper/2302.06503/) (2023)
- [Adaptive conformal classification with noisy labels](https://mlsanity.com/paper/2309.05092/) (2023)
- [Fair Classification with Adversarial Perturbations](https://mlsanity.com/paper/2106.05964/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Spuriosity Didn't Kill the Classifier: Using Invariant Predictions to Harness Spurious Features](https://mlsanity.com/paper/2307.09933/) (2023)
- [Training Subset Selection for Weak Supervision](https://mlsanity.com/paper/2206.02914/) (2022)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [Label-Noise Robust Diffusion Models](https://mlsanity.com/paper/2402.17517/) (2024)
- [Robustness to Label Noise Depends on the Shape of the Noise Distribution in Feature Space](https://mlsanity.com/paper/2206.01106/) (2022)
- [Analysing the Noise Model Error for Realistic Noisy Label Data](https://mlsanity.com/paper/2101.09763/) (2021)
- [Can Less be More? When Increasing-to-Balancing Label Noise Rates Considered Beneficial](https://mlsanity.com/paper/2107.05913/) (2021)
- [InstanT: Semi-supervised Learning with Instance-dependent Thresholds](https://mlsanity.com/paper/2310.18910/) (2023)
- [Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification](https://mlsanity.com/paper/2102.00678/) (2021)
- [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)
- [CCMN: A General Framework for Learning with Class-Conditional Multi-Label Noise](https://mlsanity.com/paper/2105.07338/) (2021)
- [Label Noise: Ignorance Is Bliss](https://mlsanity.com/paper/2411.00079/) (2024)
- [Debiased Recommendation with Noisy Feedback](https://mlsanity.com/paper/2406.17182/) (2024)
- [Positive-Unlabeled Classification under Class-Prior Shift: A Prior-invariant Approach Based on Density Ratio Estimation](https://mlsanity.com/paper/2107.05045/) (2021)
- [Self-paced Resistance Learning against Overfitting on Noisy Labels](https://mlsanity.com/paper/2105.03059/) (2021)
- [New Methods and Datasets for Group Anomaly Detection From Fundamental Physics](https://mlsanity.com/paper/2107.02821/) (2021)
- [Optical Remote Sensing Image Understanding with Weak Supervision: Concepts, Methods, and Perspectives](https://mlsanity.com/paper/2204.09120/) (2022)
- [Distributional Reward Estimation for Effective Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/2210.07636/) (2022)
- [Fairness Improves Learning from Noisily Labeled Long-Tailed Data](https://mlsanity.com/paper/2303.12291/) (2023)
- [Unified Risk Analysis for Weakly Supervised Learning](https://mlsanity.com/paper/2309.08216/) (2023)
- [An Embedding is Worth a Thousand Noisy Labels](https://mlsanity.com/paper/2408.14358/) (2024)
- [Rethinking Noisy Label Models: Labeler-Dependent Noise with Adversarial Awareness](https://mlsanity.com/paper/2105.14083/) (2021)

## Abstract (arXiv)

In many real-world classification problems, the labels of training examples are randomly corrupted. Most previous theoretical work on classification with label noise assumes that the two classes are separable, that the label noise is independent of the true class label, or that the noise proportions for each class are known. In this work, we give conditions that are necessary and sufficient for the true class-conditional distributions to be identifiable. These conditions are weaker than those analyzed previously, and allow for the classes to be nonseparable and the noise levels to be asymmetric and unknown. The conditions essentially state that a majority of the observed labels are correct and that the true class-conditional distributions are "mutually irreducible," a concept we introduce that limits the similarity of the two distributions. For any label noise problem, there is a unique pair of true class-conditional distributions satisfying the proposed conditions, and we argue that this pair corresponds in a certain sense to maximal denoising of the observed distributions. Our results are facilitated by a connection to "mixture proportion estimation," which is the problem of estimating the maximal proportion of one distribution that is present in another. We establish a novel rate of convergence result for mixture proportion estimation, and apply this to obtain consistency of a discrimination rule based on surrogate loss minimization. Experimental results on benchmark data and a nuclear particle classification problem demonstrate the efficacy of our approach.