cs.LGAug 26, 2026
SaveComparing Corrupted Constrained Learning Problems
Organizations: Tübingen AI Center, University of Tübingen, Germany
Abstract
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.
Figures & tables
Figure 1: Caption: Visualizing the constrained superprediction set. Given different points in , one can plot the set projected constrained superprediction set for and a model class that does not cover the whole simplex. We assume for and . Alt text: Four panels labeled (a) to (d), each of them containing functions plotted with respect to a Cartesian plane’s axes. The first and second panel plot a subset of the two-dimensional simplex; the second and forth panel represent a function and the area above it, corresponding to a projection of a superprediction set.
Figure 2: Caption: The base distribution . Neighboring quadrants carry different labels and the base distribution is invariant under . A model predicts with , so its decision boundary is the line (dashed); the one drawn, , classifies three atoms correctly and has to sacrifice the fourth (circled). Each atom has mass . No model does better (Lemma A.1 ). Alt text : Four quadrants of a Cartesian plane, labeled Q underscore i, i from 1 to 4. Each of the quadrants contains a point, labeled x underscore i. Two points are drawn as blue dots, two as red squares: the different placeholder indicated the two different types of labels that can assigned to a point. A green dotted line, representing a classifier called w underscore alpha, divides the Cartesian plane in two parts. Because of how the division happens, one red-square point appears to be incorrectly classified , which is indicated with an orange label (which reads “misclassified”) next to said point.
Figure 3: Caption: Corruption breaks the data processing inequality. Every disk is an atom of mass ; its blue fraction is and its red fraction , drawn for and . Left: the clean problem of Figure 2 . Middle: the attribute corruption resamples the first coordinate, which blurs the labels but leaves the constrained Bayes risk at the chance level . Right: the bijection then swaps the two left atoms; now the label depends on alone, and the model with , whose boundary is the dashed line, is optimal even among all measurable models. The composite corruption from over to thus lowers the Bayes risk of logistic regression while raising the Bayes risk of the full class : it destroys information in the classical sense and still helps the constrained learner, contradicting the classical data processing inequality. denotes the binary entropy. Alt text : Three Cartesian planes with their four quadrants; each quadrant contains a point. Each point is depicted using a pie chart, representing the probability of having a label 1 assigned given the value of the attribute x. The first Cartesian plane represents the clean data. The second and third planes represent the effect of two distinct attribute corruptions, changing pie charts. The third plane shows that the classifier w underscore alpha correctly classifies the points after applying two corruptions.
Figure 4: Caption: Visualizing the effect of corruption on the superprediction set for an unconstrained problem (Corollary 4.3 ). We consider a problem composed by: a model class , whose transitions correspond all measurable functions mapping to the relative interior of ; the logarithmic loss ; . We apply some label corruption, \ie , , only acting in the loss as depicted in panel (a). In the asymmetric cases depicted, we can graphically see that the set containment condition, and hence generalized data processing inequality, does not hold . Panel (b) represents the clean superprediction set and the corrupted one, associated to the symmetric, low corruption. In this case we instead see that the set containment holds , since . To better understand visually why set containment implies the GDPI, notice that the Bayes risk associated to the clean problem and is the length of the red line, connecting the origin to the hyperplane (dashed line) and perpendicular to it; a similar observation holds for the corrupted superprediction set. Alt text : Two panels, labeled (a) and (b). Panel (a) depicts different functions with respect the Cartesian plane’s axes. One of this is the clean loss function ell; the other four are corrupted loss functions, using four distinct corruption kernels. Panel (b) depicts the superprediction sets associated to the clear loss ell and on e corrupted loss, as well as one supporting hyperplane of the superprediction set for the clean loss. This supporting hyperplane is identified by its distance vector from the origin (in red), passing through the simplex at the probability pi.
Figure 5: Caption: Visualizing the effect of corruption on one point of the superprediction set. Given a point , we consider the different forms the point can take for different corruption types and properties. Red line : bistochastic corruption; Blue marks : points generated by a degenerate binary kernel that, in its matrix form, has ones only in one row and zeros otherwise; Blue area : corruption outcome for all possible kernels. Alt text: Two panels, labeled (a) and (b). Panel (a) depicts a blue square embedded in a Cartesian plane with its axes. The vertices of the square are: one two-dimensional point representing a loss function computed on a probability pi, once against label 0 and once against label 1; three other two-dimensional points that are corrupted versions of the same evaluated loss. The diagonal of the square is red, and corresponds to points obtained using a bistochastic corruption kernel. Panel (b) represents the same elements as panel (a), but the vertices of the square are: one two-dimensional point representing a loss function computed on a model h, once evaluated at evaluated at x equal 1, once at x equal 2; three other two-dimensional points that are corrupted versions of the same evaluated loss and model. In this case, the label y is left as a free parameter.
| Object | Formula | Reference |
| Superprediction Set | - | |
| Support Function | Theorem 4.2 | |
| Bayes Risk (change of set) | Corollary 6.1 | |
| Bayes Risk (probability corruption) when | Corollary 4.3 | |
| \botrule |
Table 1: Statements equivalent to the Generalized Data Processing Inequality.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Caption: Hierarchy of set containment conditions. The set containment introduced by Theorem 4.2 (bottom) and its equivalents are the weakest conditions, while the inclusion of the simple sets is the strongest (top). The bottom level equivalences hold by definition of convex hull and superprediction set.
| corruption | generating maps | GDPI for | ||
| — (clean ) | — | — | ||
| a) rotation | affine, bijective | ( ) | ( ) | holds |
| b) quadrant swap | bijective, not affine | ( ) | ( ) | fails |
| c) noise on | affine | ( ) | ( ) | holds |
| d) noise, then swap | not affine | ( ) | ( ) | fails |
Table 2: Corruptions in the running example . is the XOR distribution, the noise level and the binary entropy; “ ”, “ ”, “ ” compare the corrupted with the clean Bayes risk. “GDPI” refers to Definition 4.1 for the respective class, i.e. to the inequality holding for all .
Figure 7: Caption: Why convexification matters (Remark A.7 ), drawn for one fixed attribute . A prediction is a point , and we plot the pair of loss values it produces; a superprediction set is then the region up and to the right of the plotted values. The tie-broken zero-one loss produces only three such pairs— when , when , and at the tie—so is the region bounded by the red staircase, which is not convex; its closed convex hull is bounded by the green segment and adds the two orange triangles. The cross-entropy loss traces the blue curve , , and it passes through an orange triangle: at the marked the point lies in but not in , i.e. no single model has zero-one loss below the cross-entropy loss there. A mixture of models does: at this one third of the intercept-shifted classifiers predicts and two thirds predict , which realizes , and is below the blue point in both coordinates. This is the containment of Corollary 6.1 , and it holds only after convexification.
Figure 8: Caption: Constrained superprediction set is not Cartesian product of unconstrained ones. The left panel shows that, no matter what is the model class, the superprediction set of the loss (in this case for logarithmic loss ) will look the same as long as the model class covers the whole simplex, \ie , . However, in the right panel we see that the single components of the elements of the constrained superprediction set, \ie , , take different values for different models. For linear model , with sigmoid function , the induced losses are ; for cubic models, \ie , , the induced losses are . Hence, the corresponding constrained superprediction set will look different for each of these model classes.
More in this topic
Statistical Learning Theory
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
See all 584 papers