Research map / Label-efficient and robust learning / Recognition and long-tail

Corruptions of Supervised Learning Problems: Typology and Mitigations

NeurIPS 2026 · Label-efficient and robust learning › Recognition and long-tail · approach: Group-robust classification

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Develops a Markov-kernel-based taxonomy of data corruptions in supervised learning, proves its exhaustiveness, relates Bayes risks of clean and corrupted problems, and derives loss-correction formulas for attribute, label and joint corruptions.

Problem

Corruption in data collection (distribution shift, noisy labels, attribute noise, etc.) is studied in isolated settings with inconsistent naming and no exhaustive unified view of corruption types or their mitigation.

Approach

Model any corruption of a supervised learning problem (loss, model class, distribution) as a Markov kernel acting on data; classify one-step Markovian corruptions by the X/Y dependence of their kernels, prove exhaustiveness via coupling, and derive Bayes-risk equalities and generalized loss corrections that extend classical class-conditional-noise correction to dependent and joint corruptions.

Key results

• Shows the one-step Markovian corruption taxonomy (partial corruptions combined via superposition) is complete and, with non-factorized corruptions, exhaustive for all probabilistic corruptions.
• Proves that mutually contaminated distributions and selection bias (Radon-Nikodym definition) are not Markovian in their original form, while a Markovian representation exists.
• Derives Bayes risk equalities and loss-correction formulas for attribute, label and joint corruption types, summarized in a table.

Surprising findings

• Mutually contaminated distributions cannot be seen as a generalization of class-conditional noise; the two are non-comparable in their original definitions.
• Selection bias defined via Radon-Nikodym derivative cannot be represented as a Markov kernel acting on probabilities.

Limitations

• Results are qualitative; no quantitative complexity or algorithm-performance analysis is provided.
• Non-one-step and non-Markovian corruptions are only partially characterized.
• Assumes the corruption kernel is known for the analysis.

Experimental setup

Builds on: class-conditional noise loss correction information processing equalities mutually contaminated distributions

Closest papers by meaning

• An Analysis of Concept Bottleneck Models: Measuring, Understanding, and Mitigating the Impact of Noisy Annotations (NeurIPS 2025 · similarity 0.84)
• Slight Corruption in Pre-training Data Makes Better Diffusion Models (NeurIPS 2024 · similarity 0.84)
• Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification (NeurIPS 2024 · similarity 0.83)
• Naive Bayes Classifiers over Missing Data: Decision and Poisoning (ICML 2024 · similarity 0.83)
• Regretful Decisions under Label Noise (ICLR 2025 · similarity 0.83)
• HYBOOD: A Hybrid Generative Model for Out-of-Distribution Detection with Corruption Estimation (AAAI 2025 · similarity 0.83)