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 x1,x2∈\cX , one can plot the set projected constrained superprediction set \spr(ℓlog∘\cHx) for ℓlog(ϕ,y):=−log(ϕy),ϕ∈\Prob(\cY) and a model class that does not cover the whole simplex. We assume h^(xi)=(h^(xi)0,h^(xi)1):=(ηi,1−ηi) for η1=0.6 and η2=0.4 . 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 ϕ(1,0,1,0) . Neighboring quadrants carry different labels and the base distribution is invariant under x↦−x . A model hα∈\cH predicts σ(wα(x)) with wα(x)=α1x1+α2x2+α0 , so its decision boundary is the line {wα=0} (dashed); the one drawn, α=(1,1,−0.5) , classifies three atoms correctly and has to sacrifice the fourth (circled). Each atom has mass 41 . 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 41 ; its blue fraction is ηi=ϕ(Y=1∣X=x(i)) and its red fraction 1−ηi , drawn for ε=0.2 and εˉ:=1−ε . Left: the clean problem ϕ(1,0,1,0) of Figure 2 . Middle: the attribute corruption \taε=(1−ε)\taid+ε\taρ resamples the first coordinate, which blurs the labels but leaves the constrained Bayes risk at the chance level log2 . Right: the bijection S then swaps the two left atoms; now the label depends on x2 alone, and the model with α=(0,0,logεεˉ) , whose boundary is the dashed line, is optimal even among all measurable models. The composite corruption from ϕ(1,0,1,0) over ϕ(εˉ,ε,εˉ,ε) to ϕ(εˉ,ε,εˉ,ε) thus lowers the Bayes risk of logistic regression while raising the Bayes risk of the full class \cHall : it destroys information in the classical sense and still helps the constrained learner, contradicting the classical data processing inequality. \Ent 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 \cH , whose transitions \mth correspond all measurable functions mapping to the relative interior of \Prob(\cY) ; the logarithmic loss ℓlog ; ∣\cX∣=1;\cY={0,1} . We apply some label corruption, \ie , \ka=\idx\otm\la , 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 \cspr(\mto\laℓlog∘\cH)⊂\cspr(ℓlog∘\cH) . To better understand visually why set containment implies the GDPI, notice that the Bayes risk associated to the clean problem and π=(0.3,0.7) 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 ℓ∘h∈\spr(ℓ∘\cH) , we consider the different forms the point \mto\ka(ℓ∘h) 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
\cspr(ℓ′∘\cH′)⊆\cspr(ℓ∘\cH)
-
Support Function
ρ\spr(ℓ′∘\cH′)(μ)≥ρ\spr(ℓ∘\cH)(μ)∀μ∈\ba(\XY)
Theorem 4.2
Bayes Risk (change of set)
\brℓ′∘\cH′(ϕ)≥\brℓ∘\cH(ϕ)∀ϕ∈\finProb(\XY)
Corollary 6.1
Bayes Risk (probability corruption) when ℓ′∘\cH′=\mto\ka(ℓ∘\cH)
\brℓ∘\cH(\amto\kaϕ)≥\brℓ∘\cH(ϕ)∀ϕ∈\finProb(\XY)
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
\BRℓlog∘\cH
\BRℓlog∘\cHall
GDPI for \cH
— (clean ϕ(1,0,1,0) )
—
log2
0
—
a) rotation
affine, bijective
log2 ( = )
0 ( = )
holds
b) quadrant swap
bijective, not affine
0 ( < )
0 ( = )
fails
c) noise on x1
affine
log2 ( = )
\Ent(ε) ( > )
holds
d) noise, then swap
not affine
\Ent(ε) ( < )
\Ent(ε) ( > )
fails
Appendix
Table 2: Corruptions in the running example . ϕ(1,0,1,0) is the XOR distribution, ε∈(0,21) the noise level and \Ent 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 x . A prediction is a point π∈\Deltaca(\cY) , and we plot the pair of loss values (ℓ(π,0),ℓ(π,1)) it produces; a superprediction set is then the region up and to the right of the plotted values. The tie-broken zero-one loss ℓ01 produces only three such pairs— (0,1) when π1<21 , (1,0) when π1>21 , and (21,21) at the tie—so \spr(ℓ01) is the region bounded by the red staircase, which is not convex; its closed convex hull is bounded by the green segment ℓ(π,0)+ℓ(π,1)=1 and adds the two orange triangles. The cross-entropy loss traces the blue curve t↦(log(1+et),log(1+e−t)) , t=wα(x) , and it passes through an orange triangle: at the marked t=21 the point lies in co\spr(ℓ01) but not in \spr(ℓ01) , i.e. no single model has zero-one loss below the cross-entropy loss there. A mixture of models does: at this x one third of the intercept-shifted classifiers predicts 0 and two thirds predict 1 , which realizes m=31(0,1)+32(1,0) , and m is below the blue point in both coordinates. This is the containment co\spr(ℓlog∘\cH)⊆co\spr(ℓ01∘\cH) 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 ℓlog ) will look the same as long as the model class covers the whole simplex, \ie , \Prob(\cY)=⋃x∈\cX{\mth(x),h∈\cH} . However, in the right panel we see that the single components of the elements of the constrained superprediction set, \ie , [ℓlog(\mth(x)y,y)]x,y , take different values for different models. For linear model \mthlin(x)0:=σ(x+b) , with sigmoid function σ , the induced losses are (ℓlog∘hlin)(x,y)=[−log(σ(x+b)),−log(1−σ(x+b))] ; for cubic models, \ie , \mthcub(x)0:=σ(x3+b) , the induced losses are (ℓlog∘hcub)(x,y)=[−log(σ(x3+b)),−log(1−σ(x3+b))] . Hence, the corresponding constrained superprediction set will look different for each of these model classes.
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
In this paper we prove some concentration inequalities for two types of error probabilities in the Empirical Risk Principle (ERP) in statistical learning, which provide a lower bound and an upper bound for the minimal risk (in terms of the minimal empirical risk) with non-asymptotic high confidence. The usual boundedness condition of the empirical risk function is relaxed to the Gaussian or exponential integrability condition. The confidence of the lower bound of the minimal risk is shown to be independent of the number of training parameters and the dimension of the input vectors, allowing one to detect the deficiency of a learning machine efficiently; and the confidence of the upper bound of the minimal risk is proved to be high provided that the sample size n is much greater than the box dimension of the parameter set Θ in the Orlicz metric dψ1 associated with the risk functions. Our work is based on Talagrand's concentration inequalities (the sharp versions by Bousquet and Klein-Rio), transport-entropy inequalities and the recent progress in the theory of empirical processes and statistical learning.
Liming Wu, Sen Yang
Laboratoire de Mathématiques Blaise Pascal, CNRS-UMR 6620, Université Clermont Auvergne · IASM, Harbin Institute of Technology
We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this model, an adversary, upon looking at a "clean" i.i.d. dataset, inserts additional "corrupted" points of their choice into the dataset. These added points are constrained to be monotone corruptions, in that they get labeled according to the ground-truth target function. Perhaps surprisingly, we demonstrate that in this setting, all known optimal learning algorithms for binary classification can be made to achieve suboptimal expected error on a new independent test point drawn from the same distribution as the clean dataset. On the other hand, we show that uniform convergence-based algorithms do not degrade in their guarantees. Our results showcase how optimal learning algorithms break down in the face of seemingly helpful monotone corruptions, exposing their overreliance on exchangeability.
Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty
Machine-learning models are commonly developed under an assumption that training and test data are sufficiently complete, balanced, labelled, and drawn from compatible distributions. In practice, one or more of these conditions is often violated. Measurements may be missing or corrupted, rare classes may be poorly represented, supervision may be weak, and the deployment environment may differ from the training environment. These imperfections are usually treated as separate technical problems, although they alter learning through a small number of shared mechanisms: loss of information, biased empirical risk, ambiguous supervision, and unstable representations. This short survey organises representative methods around these mechanisms. It reviews reconstruction and generation, rebalancing and representation calibration, learning with limited supervision, adaptation across domains and modalities, and reliability under distribution change. The discussion highlights the limits of plausible reconstruction, benchmark-specific correction, and adaptation without trustworthy feedback. It concludes with directions for evidence-aware learning, uncertainty-preserving prediction, and evaluation that separates visual plausibility from decision utility.