PaperlayerView exact revision on arXiv

Source-linked AI summary

Comparing Corrupted Constrained Learning Problems

Laura Iacovissi, Rabanus Derr, Robert C. Williamson

arXiv:2608.25745v1cs.LGmath.STstat.ML

TL;DR

The paper asks whether the classical data processing inequality remains valid for constrained machine-learning problems. It gives a counterexample, formulates a generalized inequality for joint distributions with fixed losses and model classes, and characterizes validity through superprediction-set containment. The resulting framework yields sufficient conditions for the generalized inequality, while its treatment of continuous-space bistochastic corruptions remains outside scope.

  • Problem

    The classical data processing inequality may not apply to machine-learning settings where the effective hypothesis class is constrained rather than unconstrained.

  • Method

    The paper studies constrained Bayes risk over joint distributions and uses constrained superprediction sets to characterize the generalized data processing inequality.

  • Results

    A simple counterexample shows that the classical data processing inequality can fail for constrained Bayes risk, while the generalized inequality is equivalent to a superprediction-set containment condition.

  • Takeaways & Limitations

    The framework provides sufficient conditions for comparing constrained learning problems under distribution corruptions through their loss and model classes.

  • Takeaways & Limitations

    Generalizations of the theorem for bistochastic corruptions on continuous spaces are left as an open problem outside the paper’s scope.

Abstract

from arXiv · show

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. It states that the Bayes risk of a statistical experiment obtained by stochastically modifying another experiment cannot be lower than the Bayes risk of the original experiment, regardless of the loss function or prior chosen. In machine learning, this result underlies applications such as the information bottleneck principle and some feature learning techniques. However, machine learning problems are constrained learning problems: the model class used does not include all measurable functions. We present a simple counterexample 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 hypothesis class) to lower bound the constrained Bayes risk on the stochastically modified 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 derive sufficient conditions for this containment.

1 Introduction

The classical data processing inequality says stochastic modification cannot reduce Bayes risk, but this guarantee can fail for constrained machine-learning model classes. The paper proposes a generalized inequality centered on joint distributions, fixed losses, and model classes, and characterizes it using superprediction sets.

  • Classical data processing inequality: The classical data processing inequality states that randomizing a statistical experiment cannot lower its Bayes risk for any loss function or prior.This result supports applications in information theory, economics, feature learning, and the information bottleneck principle.
  • Data processing in machine learning: Pre-trained representations expose a tension: the classical inequality predicts no improvement from a representation when an optimized task-specific head is used, yet empirical evidence seemingly contradicts this.The tension arises because representations are non-bijective transformations followed by constrained predictive models.
  • A generalized DPI: The generalized DPI replaces priors and experiments with joint distributions and evaluates constrained Bayes risk for a fixed loss and model class.Its informal form requires BRℓ◦H(ϕ) ≤ BRℓ◦H(ϕ′) for all probability distributions ϕ under the relevant corruption.
  • Data processing in machine learning: Machine-learning problems differ from classical statistical experiments because effective model classes are constrained by hypotheses, optimization, initialization, and data presentation.Even large models may be effectively restricted by the learning algorithm and training dynamics.
  • A generalized DPI: The classical inequality can fail under constrained Bayes risk because the integration–infimum interchange used in DeGroot’s proof breaks when the model class is not well-specified.A simple counterexample demonstrates that the constrained inequality need not hold.
  • A generalized DPI: The paper uses constrained superprediction sets to characterize the generalized inequality and derive sufficient conditions for it to hold.The framework shifts emphasis toward practitioner-specified losses and model classes, which encode domain knowledge and needs.

2 Statistical Learning Problems with Markov Kernels

The paper formalizes statistical learning problems with measurable spaces, probability distributions, model classes, loss functions, and Markov kernels. It then introduces constrained superprediction sets and connects their support functions to constrained Bayes risk.

  • Markov kernels: Markov kernels provide the formal framework for stochastic transformations between measurable spaces, including statistical experiments and corruptions.They require measurable dependence on the input and countably additive measures over output sets; Markov kernels are those inducing probability distributions.
  • Markov kernel actions: The framework represents kernels through associated transitions and operators that act on probability measures and sets of functions.Kernel actions preserve countably additive measures and probability distributions, and measurable functions can induce deterministic kernels.
  • Markov kernels: Deterministic kernels are exactly the extreme points of the set of Markov kernels, linking measurable functions with the extreme-point structure of stochastic transformations.The identity and degenerate kernels provide important special cases of deterministic and non-informative transformations.
  • Decision-theoretic setup: An experiment is a Markov kernel from a finite label space to an attribute space, while combining it with a label prior yields a joint data distribution.The product composition πY × E is called the Bayes decomposition.
  • Constrained superprediction sets: The constrained superprediction set collects loss values induced by a fixed loss function and model class, and its support function equals constrained Bayes risk.This extends superprediction-set theory to hypothesis constraints and supplies the geometric tool used to characterize the generalized data processing inequality.

3 A Counterexample to the DPI Holding in the Constrained Case

The classical data processing inequality need not hold for constrained model classes: corruption can reduce constrained Bayes risk. The paper uses a counterexample and motivates a generalized inequality for joint distributions, losses, and constrained hypotheses.

  • Generalized DPI: The generalized DPI compares constrained Bayes risks on a joint distribution and its Markov-kernel randomization rather than relying on the unconstrained classical setting.The proposed formulation is introduced to address constrained machine-learning problems where model classes matter directly.
  • Failure of the classical DPI: In the constrained, potentially misspecified setting, the classical DPI proof fails because integration and infimum cannot generally be swapped.The inequality can therefore fail, and the paper constructs a simple counterexample.
  • Counterexample construction: A singleton model class can have strictly positive original risk when its only hypothesis assigns less than probability one to the correct label.For the specified class and full-support prior, the original constrained risk is positive as shown in Eq. (23).
  • Counterexample construction: Full corruption of the attribute space produces a corrupted distribution whose Bayes risk is half the original task’s Bayes risk.The reduction occurs because randomization increases the chance of sampling an attribute that the restrictive model labels correctly by accident.
  • Implication: The counterexample shows that randomization can improve constrained performance, even though the construction uses an extremely restrictive model class tailored to the scenario.The authors state that the same reasoning extends beyond singleton model classes.

4 Generalized Data Processing Inequality

The generalized data processing inequality (GDPI) compares constrained Bayes risks for a fixed loss and model class across joint distributions and their corruptions. Its validity is characterized by containment relations between convexified superprediction sets, with sufficient conditions developed for several corruption classes.

  • Definition and scope: BRℓ◦H(ϕ) ≤BRℓ◦H(ˇκϕ) requires joint corruption to worsen constrained Bayes risk for every base distribution ϕ.Unlike the classical formulation, the joint corruption may also modify the target marginal πY.
  • Definition and scope: The generalized inequality is more general than the classical data processing inequality, which is recovered with the unrestricted model class H = M(X, Y) and κ ∈M(X, X).
  • Set characterization: co spr F ⊇co spr G if and only if ρF(ϕ) ≤ρG(ϕ) for every probability distribution ϕ, linking set containment to support-function ordering.
  • Consequences: Two hypothesis classes are equally powerful under a fixed loss exactly when their superprediction sets are equal, while restricting the class cannot improve Bayes risk.The regularization remark describes this as a best-case performance degradation at the Bayes-risk level.
  • Set characterization: For a fixed loss and model class, GDPI under corruption holds if and only if co spr(ℓ◦H) contains co spr(ˆκ(ℓ◦H)).This specializes the general equivalence to corrupted attainable prediction losses.
  • Corruption classes: For finite spaces, bistochastic corruptions correspond to doubly stochastic matrices, while the paper leaves continuous-space generalizations open.

5 Sufficient Conditions for the GDPI

The paper derives sufficient conditions for the generalized data processing inequality across label and attribute corruptions, using superprediction-set containment and convex-kernel analysis. These conditions cover dependent and simple corruptions, including bistochastic cases, but are sufficient rather than necessary.

  • Dependent corruptions: Sufficient GDPI conditions are derived for dependent corruptions by requiring relevant Markov-kernel families to lie within K(ℓ◦H).Convexity reduces the analysis to extreme points, simplifying the study of deterministic kernels.
  • Simple corruptions: In the binary setting, degenerate and symmetric bistochastic kernels provide the relevant extreme actions for deriving sufficient Bayes-risk conditions.Degenerate corruptions arise from constant functions, while bistochastic kernels are associated with suitable bijections.
  • Label corruption: Label-transformation closure yields GDPI guarantees for label corruptions, including attribute-dependent corruptions under a strengthened invariance assumption.Bistochastic label corruption is identified as an important special case with sufficient conditions on ℓ and H.
  • Attribute corruption: Analogous sufficient results are established for attribute corruption and illustrated with practically relevant transformations.The results apply to F-attribute corruptions and bistochastic attribute corruptions under stated conditions.
  • Simple corruptions: For simple label corruptions, GDPI is equivalent to a superprediction-set containment condition for every corruption induced by a function class F.The condition is necessary and sufficient for all simple label corruptions in the induced family.
  • Sufficient but not necessary conditions: The sufficient conditions are not necessary: uniform bistochastic label corruption preserves GDPI, whereas both underlying simple permutation noises need not do so.The paper also notes that X-permutation invariance is not necessary for GDPI under attribute corruption.

6 Conclusion

The conclusion presents constrained superprediction sets as a systematic framework for comparing loss–model-class pairs under distributional corruptions. It positions the generalized DPI as a complement to classical comparisons of experiments and joint probabilities.

  • Conclusion: The constrained superprediction set characterizes GDPI for constrained learning problems.The framework compares average optimal performance across distributions under Markov-kernel corruptions.
  • Conclusion: The framework compares different choices of loss function and model class without requiring the comparison to center on a particular data distribution.This perspective complements existing approaches based on statistical experiments or joint probabilities.
  • Conclusion: The appendix formalizes the dual-pair machinery used for bounded measurable functions and finitely additive signed measures.These spaces provide the bilinear pairing underlying the stated framework.

A.1 Relevant Topologies and Sets

This appendix defines weak topologies and probability-measure sets used in the paper’s functional-analytic framework. It also states that, for Polish spaces, finitely additive and countably additive probability sets coincide under the relevant weak topology.

  • Weak topologies: The weak topologies σ(Bb, ba) and σ(ba, Bb) make the corresponding duality functionals continuous.They are weaker than the respective norm topologies.
  • Probability-measure sets: ca(Z) denotes countably additive signed measures with bounded total variation, alongside corresponding probability-measure sets.The appendix distinguishes countably additive and finitely additive probabilities.
  • Probability-measure sets: Expectations of bounded measurable functions are defined for probability measures in this dual-pair setting.This expectation notation is used throughout the appendix’s measure-theoretic development.
  • Probability-measure sets: For Polish Z, ∆ca(Z) equals ∆(Z) under the σ(Bb, ba)-topology.The stated proof uses compactness, convex hulls, and the fact that extreme points are Dirac measures.

Appendix B. Remarks on Constrained Conditional Risk

The appendix extends risk and Bayes-risk definitions to finitely additive generating probabilities while retaining standard losses and countably additive Markov-kernel model classes. It notes that familiar conditional-risk decompositions may fail for constrained classes without decomposability.

  • Conditional Bayes risk: Conditional Bayes risk is defined for a measurable loss taking a label distribution and label as inputs.The terminology may refer to conditional or prior risk depending on the probability argument.
  • Constrained conditional risk: For unconstrained models, a conditional-risk representation relies on a data-generating distribution of the form ϕ = πX × F.The associated equality follows from a cited interchange result.
  • Constrained conditional risk: For constrained model classes, the unconstrained conditional-risk theorem may fail unless the class satisfies decomposability.The appendix does not explore conditions ensuring this property.
  • Extended risk: The extended risk definition permits finitely additive generating probabilities while restricting model classes to Markov kernels.This preserves a standard Bayesian inference framework while enabling the dual pairing used in the analysis.
  • Extended risk: The induced kernel operator maps finitely additive probability measures into finitely additive probability measures, a weaker property than the countably additive case.Equality with the full target probability set is not established in this setting.

Appendix D. From Unconstrained Superprediction Set to Constrained Superprediction Set

The constrained superprediction set depends on how the model class jointly assigns predictions across inputs, unlike the unconstrained construction. When the class covers the whole simplex, the logarithmic-loss superprediction set is unchanged across model classes.

  • Constrained superprediction set: The constrained superprediction set restricts loss vectors induced by predictions from the model class.For each input, the construction considers the predictions available at that input and the resulting induced losses.
  • Comparison with the unconstrained set: Figure 5’s left panel shows identical logarithmic-loss superprediction sets whenever the model class covers the whole simplex, ∆ca(Y) = S.In this case, the model class does not restrict the available class-probability predictions.
  • Model-class dependence: Linear and cubic model classes induce different loss components, so their constrained superprediction sets differ.The appendix illustrates this distinction using logarithmic loss and sigmoid-based linear and cubic predictors.
  • Cross-input dependence: The naive Cartesian-product construction can be strictly larger than the constrained set because one model may not independently assign predictions at different inputs.Prediction assignments can interact across inputs when the model class imposes relationships between them.
  • Set representation: The construction uses nonnegative functions above attainable loss vectors, yielding the representation spr(F) = F ⊕ Bb(Z)≥0.The proof writes each dominating function as an attainable loss function plus a nonnegative remainder.

Appendix F. Proof of Proposition 21

The proof establishes that the set of corruptions preserving the generalized data processing condition is convex. It does so by combining corrupted superprediction sets under convex mixtures of Markov kernels.

  • Mixtures of corruptions: For a mixture of kernels, the corrupted superprediction set is contained in the corresponding Minkowski combination of the component corrupted sets.The proof bounds each mixed loss vector using the same hypothesis and decomposes the excess nonnegative component across the two sets.
  • Convexity of K: The set K(ℓ◦H) associated with a loss and model class is convex.For κ = ακ1 + (1 − α)κ2, membership follows from the corresponding containment for κ1 and κ2.
  • Proof conclusion: This containment yields spr(κ̂(ℓ◦H)) ⊆ co spr(ℓ◦H), which is the defining condition needed for membership in K(ℓ◦H).Convexity then follows by applying the containment to convex combinations of admissible kernels.

Appendix G. Proof of Theorem 16

The proof develops support-function and antipolar machinery for constrained superprediction sets. It converts convex-set containment into inequalities over probability measures and establishes the associated antipolar constructions under closure and nondegeneracy conditions.

  • Set and support-function orderings: Containment between closed convex superprediction sets is equivalent to ordering their support functions.The equivalence follows directly in one direction and from support-function duality in the other.
  • Support-function characterization: The convex closure of a superprediction set can be characterized by support-function inequalities evaluated over probability measures on X × Y.Signed-measure constraints are reduced using homogeneity and the nonnegative-function structure of superprediction sets.
  • Signed-measure reduction: Negative finitely additive measures can be omitted because the support function of the nonnegative extension equals −∞ on that class.Scaled indicator functions drive the relevant infimum arbitrarily low while the original set remains nonempty.
  • Antipolar framework: Antipolar sets and antipolar support functions are introduced through the dual pairing between bounded functions and finitely additive measures.The construction includes antipolar sets, shady sets, and a homogeneous support-function representation.
  • Structural identities: Under the stated closedness, convexity, and nonzero-origin conditions, bipolar and conjugacy results connect superprediction sets with their antipolars and antigauge functions.These identities rely on shady-set structure and upper semicontinuity of the associated concave functions.

H.2 Antipolar GDPI for Bayes Risk

The antipolar framework extends the generalized data processing inequality to stronger risk comparisons. Under nondegeneracy assumptions, set containment, support-function relations, and inflation-coefficient formulations become equivalent.

  • Equivalence conditions: Assuming 0 ∉ co spr(ℓ◦H), the stated containment condition is equivalent to both the GDPI for Bayes risk and its antipolar counterpart.The equivalence uses the shady structure of the convexified constrained superprediction set.
  • Risk interpretation: The inflation coefficient is connected to an infimum over minimal relative risks of functions in the corrupted superprediction set.Minimal relative risk compares a function’s expected value with constrained Bayes risk across distributions.
  • Inflation coefficient: For suitable kernels, the GDPI for Bayes risk is equivalent to the Strong GDPI holding with inflation coefficient αℓ◦H(κ) ≥ 1.The proposition states equivalence between the ordinary inequality and the coefficient-based strong form.

Proof

The proof develops sufficient conditions for constrained strong data processing, while emphasizing that computing the associated coefficients remains difficult.

  • Proof: The proof derives one implication directly from the GDPI for Bayes risk and obtains another using Lemma 66.The displayed proof steps identify the GDPI and Lemma 66 as the relevant ingredients.
  • Proof: The argument bounds expected losses over the convexified generalized superprediction set below by the constrained Bayes risk.The proof first states the bound for every function in the convexified set, then takes its infimum over that set.
  • Proof: The sufficient-condition result assumes 0 is excluded from both the original and transformed generalized superprediction sets.Under these conditions, Corollary 68 provides a sufficient condition for strong GDPI for Bayes risk.
  • Proof: The paper relates strong GDPI coefficients to minimal relative risk and antipolar support functions but does not provide a formula for computing the coefficients.The authors describe coefficient computation as technically demanding and compare the difficulty with contraction coefficients for divergences.

Appendix I. Constrained Information

The appendix defines constrained statistical information through predictive families and shows how it connects to earlier notions of statistical and predictive information.

  • Appendix I. Constrained Information: Constrained information is introduced because constrained conditional risk cannot generally serve as entropy while preserving non-negativity of information differences.The appendix therefore focuses on Bayes risk for joint distributions and a broader class of corruptions.
  • Appendix I. Constrained Information: A predictive family is a model class containing the degenerate kernel associated with every probability in the image of the class through X.The constant predictors in such a class are denoted Hc.
  • Appendix I. Constrained Information: The appendix defines predictive information for a loss, predictive family, and joint distribution, generalizing DeGroot’s statistical information and Xu et al.’s constrained information.The construction uses the predictive family and its constrained Bayes-risk quantities.
  • Appendix I. Constrained Information: When the model class is unconstrained, the construction recovers statistical information through the corresponding constrained Bayes-risk identities.For logarithmic loss, it also recovers predictive H-information and relates the risks to conditional and marginal H-entropy.
  • Appendix I. Constrained Information: The appendix establishes basic properties including zero predictive information when X and Y are independent, and transfers empirical estimation results from prior work.It also defines empirical predictive information from an i.i.d. sample and states an estimation proposition under bounded loss.
Loading 2608.25745v1…