# Comparing Corrupted Constrained Learning Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 62 references that are in the map.
- First posted on arXiv 26 Aug 2026.

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

- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [Understanding Dataset Difficulty with V-Usable Information](https://mlsanity.com/paper/2110.08420/) (2021)
- [A Theory of Usable Information Under Computational Constraints](https://mlsanity.com/paper/2002.10689/) (2020)
- [From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence](https://mlsanity.com/paper/2601.03220/) (2026)
- [Fundamental Limits and Tradeoffs in Invariant Representation Learning](https://mlsanity.com/paper/2012.10713/) (2020)
- [Understanding Visual Feature Reliance through the Lens of Complexity](https://mlsanity.com/paper/2407.06076/) (2024)
- [The Geometry and Calculus of Losses](https://mlsanity.com/paper/2209.00238/) (2022)
- [Information Processing Equalities and the Information-Risk Bridge](https://mlsanity.com/paper/2207.11987/) (2022)
- [The Geometry of Mixability](https://mlsanity.com/paper/2302.11905/) (2023)
- [A Theory of Feature Learning](https://mlsanity.com/paper/1504.00083/) (2015)
- [Minimization Interchange Theorem on Posets](https://mlsanity.com/paper/2107.05903/) (2021)
- [Corruptions of Supervised Learning Problems: Typology and Mitigations](https://mlsanity.com/paper/2307.08643/) (2023)
- [A Unified View of Polarity for Functions](https://mlsanity.com/paper/2410.16773/) (2024)
- [Does the Data Processing Inequality Reflect Practice? On the Utility of Low-Level Tasks](https://mlsanity.com/paper/2512.21315/) (2025)

## Abstract (arXiv)

A key result in statistics is the data processing inequality, originally proved by Blackwell (1951) and later refined by DeGroot (1962) in terms of statistical uncertainty. The latter statement claims that the Bayes risk achieved on raw data always undercuts the Bayes risk on a processed version of the same data. This seemingly contradicts empirical findings in machine learning: pre-training, representation learning, feature learning, data augmentation are techniques used to improve performance of machine learning models. We reconcile both worlds by simply accepting that machine learning problems are constrained learning problems: the model class used does not include all measurable functions. We present counterexamples showing that the classical data processing inequality fails to hold in such a setting. Hence, we formulate a generalized data processing inequality, requiring the constrained Bayes risk of a joint distribution (with respect to a loss function and a constrained model class) to lower bound the constrained Bayes risk on the stochastically modified data distribution, regardless of the choice of distribution. We show this inequality to be equivalent to a set containment condition on a specific function set induced by the loss and model class, called the superprediction set. Finally, we exploit our characterization, derive sufficient conditions for this containment and quantify the inequality-gap.